Abstract
The paper presents a tractable subclass of DTDs, called DC-DTDs, for XPath satisfiability with sibling axes. A DC-DTD is a DTD such that each content model is in the form of a concatenation of single tag names and Kleene-starred regular expressions. DC-DTDs are a proper subclass of covering DTDs proposed by Montazerian et al., and a proper superclass of disjunction-free DTDs. In this paper, it is shown that tractability by covering DTDs is fragile against sibling axes. Then, tractability of XPath satisfiability with sibling axes under DC-DTDs is demonstrated. Finally, as a limitation of the tractability of DC-DTDs, it is shown that upward axes appearing in qualifiers bring intractability under even disjunction-free DTDs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Lakshmanan, L.V.S., Ramesh, G., Wang, H., Zhao, Z.J.: On testing satisfiability of tree pattern queries. In: Proceedings of the Thirtieth International Conference on Very Large Data Bases, pp. 120–131 (2004)
Benedikt, M., Fan, W., Geerts, F.: XPath satisfiability in the presence of DTDs. In: Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 25–36 (2005)
Benedikt, M., Fan, W., Geerts, F.: XPath satisfiability in the presence of DTDs. Journal of the ACM 55(2) (2008)
Miklau, G., Suciu, D.: Containment and equivalence for a fragment of XPath. Journal of the ACM 51(1), 2–45 (2004)
Geerts, F., Fan, W.: Satisfiability of XPath queries with sibling axes. In: Bierman, G., Koch, C. (eds.) DBPL 2005. LNCS, vol. 3774, pp. 122–137. Springer, Heidelberg (2005)
Genevès, P., Layaïda, N.: A system for the static analysis of XPath. ACM Transactions on Information Systems 24(4), 475–502 (2006)
Genevès, P., Layaïda, N.: Deciding XPath containment with MSO. Data & Knowledge Engineering 63(1), 108–136 (2007)
Genevès, P., Layaïda, N., Schmitt, A.: Efficient static analysis of XML paths and types. In: Proceedings of the ACM SIGPLAN 2007 Conference on Programming Language Design and Implementation, pp. 342–351 (2007)
Murata, M., Lee, D., Mani, M., Kawaguchi, K.: Taxonomy of XML schema languages using formal language theory. ACM Transactions on Internet Technology 5(4), 660–704 (2005)
Montazerian, M., Wood, P.T., Mousavi, S.R.: XPath query satisfiability is in PTIME for real-world DTDs. In: Barbosa, D., Bonifati, A., Bellahsène, Z., Hunt, E., Unland, R. (eds.) XSym 2007. LNCS, vol. 4704, pp. 17–30. Springer, Heidelberg (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ishihara, Y., Morimoto, T., Shimizu, S., Hashimoto, K., Fujiwara, T. (2009). A Tractable Subclass of DTDs for XPath Satisfiability with Sibling Axes. In: Gardner, P., Geerts, F. (eds) Database Programming Languages. DBPL 2009. Lecture Notes in Computer Science, vol 5708. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03793-1_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-03793-1_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03792-4
Online ISBN: 978-3-642-03793-1
eBook Packages: Computer ScienceComputer Science (R0)