### XPath satisfiability in the presence of DTDsXPath satisfiability in the presence of DTDs

Access Restriction
Subscribed

 Author Benedikt, Michael ♦ Fan, Wenfei ♦ Geerts, Floris Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2008 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Containment ♦ DTDs ♦ Satisfiability ♦ XML ♦ XPath Abstract We study the satisfiability problem associated with XPath in the presence of DTDs. This is the problem of determining, given a query $\textit{p}$ in an XPath fragment and a DTD $\textit{D},$ whether or not there exists an XML document $\textit{T}$ such that $\textit{T}$ conforms to $\textit{D}$ and the answer of $\textit{p}$ on $\textit{T}$ is nonempty. We consider a variety of XPath fragments widely used in practice, and investigate the impact of different XPath operators on the satisfiability analysis. We first study the problem for negation-free XPath fragments with and without upward axes, recursion and data-value joins, identifying which factors lead to tractability and which to NP-completeness. We then turn to fragments with negation but without data values, establishing lower and upper bounds in the absence and in the presence of upward modalities and recursion. We show that with negation the complexity ranges from PSPACE to EXPTIME. Moreover, when both data values and negation are in place, we find that the complexity ranges from NEXPTIME to undecidable. Furthermore, we give a finer analysis of the problem for particular classes of DTDs, exploring the impact of various DTD constructs, identifying tractable cases, as well as providing the complexity in the query size alone. Finally, we investigate the problem for XPath fragments with sibling axes, exploring the impact of horizontal modalities on the satisfiability analysis. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2008-05-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 55 Issue Number 2 Page Count 79 Starting Page 1 Ending Page 79

#### Open content in new tab

Source: ACM Digital Library