Satisfiability of Simple XPath Fragments under Duplicate-Free DTDs

• SUZUKI Nobutaka

  Faculty of Library, Information and Media Studies, University of Tsukuba

• FUKUSHIMA Yuji

  Yahoo Japan Corporation

• IKEDA Kosetsu

  Graduate School of Library, Information and Media Studies, University of Tsukuba

抄録

In this paper, we consider the XPath satisfiability problem under restricted DTDs called “duplicate free”. For an XPath expression q and a DTD D, q is satisfiable under D if there exists an XML document t such that t is valid against D and that the answer of q on t is nonempty. Evaluating an unsatisfiable XPath expression is meaningless, since such an expression can always be replaced by an empty set without evaluating it. However, it is shown that the XPath satisfiability problem is intractable for a large number of XPath fragments. In this paper, we consider simple XPath fragments under two restrictions: (i) only a label can be specified as a node test and (ii) operators such as qualifier ([ ]) and path union (∪) are not allowed. We first show that, for some small XPath fragments under the above restrictions, the satisfiability problem is NP-complete under DTDs without any restriction. Then we show that there exist XPath fragments, containing the above small fragments, for which the satisfiability problem is in PTIME under duplicate-free DTDs.

収録刊行物

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E96.D (5), 1029-1042, 2013

  一般社団法人 電子情報通信学会

キーワード

• XML
• XPath
• satisfiability

詳細情報

• CRID: 1390282679356470656
• NII論文ID: 10031193955
• NII論文ID: 130003370867
• NII書誌ID: AA10826272
• DOI: 10.1587/transinf.e96.d.1029
• ISSN: 17451361
• ISSN: 09168532
• HANDLE: 2241/119481
• Web Site: https://tsukuba.repo.nii.ac.jp/records/29198
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E96.D/5/E96.D_1029/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • IRDB
  • Crossref
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可