DTD存在下における兄弟軸を含むPositive XPathクエリの恒真性判定問題

摘要

In this paper, we discuss the complexity of the validity for positive XPath queries under the presence of DTDs. A given query p is valid under a DTD D if for each XML document conforming to D the answer to p is a nonempty set. Valid XPath queries are useful in XML data mapping settings. We first show that the validity for the XPath class with only child, descendant-or-self and sibling axes, and wildcard is coNP-hard. Moreover, for the class with child and sibling axes, qualifier and wildcard, the validity is in PTIME.%近年，構造化データを記述可能なXMLが盛んに利用されており，XML文書の特定の要素を指定する問合せ言語としてXPathが広く用いられている.XPathは，XML文書を木構造に見立て，その根頂点からの経路を記述することで，XML文書の特定の要素を指定する問合せ言語である.与えられたXPathクエリpに対してDTD Dに従うすべてのXML文書が解をもっとき，pはDのもとで恒真であるという.この恒真性を判定することは，XMLデータマッピング等において有用であることが知られている.本稿では，Positive XPathクエリの恒真性判定問題の計算複雑性について議論する.まず，XPathクエリが子軸，子孫軸，兄弟軸，ワイルドカードのみを含む場合にcoNP困難であることを示す.そして，子軸，兄弟軸，述語にワイルドカードを含めた場合にPTIMEに属することを示す.