Abstract
This paper extends the tractability results on XPath satisfiability with sibling axes under DC-DTDs, which were presented by the authors at DBPL 2009, in the following two directions. First, we provide a condition to extend a class of DTDs without spoiling the tractability of XPath satisfiability, provided that only child, descendant-or-self, parent, ancestor-or-self, following-sibling, and preceding-sibling axes, path union, and qualifier are taken into account. By applying the condition to DC-DTDs, we obtain a strictly broader but still tractable class of DTDs, where operators ? (zero or one occurrence) and + (one or more occurrences) are allowed in regular expressions in a restricted manner. Second, we extend the existing method of analyzing the satisfiability under DC-DTDs to a broader class of XPath expressions. Then, we show that the extended satisfiability analysis can be performed efficiently for a new subclass of XPath expressions.
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
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)
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)
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)
Figueira, D.: Satisfiability of downward XPath with data equality tests. In: Proceedings of the 28th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 197–206 (2009)
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)
Suzuki, N., Fukushima, Y.: Satisfiability of simple XPath fragments in the presence of DTD. In: Proceedings of the 11th International Workshop on Web Information and Data Management, pp. 15–22 (2009)
Ishihara, Y., Morimoto, T., Shimizu, S., Hashimoto, K., Fujiwara, T.: A tractable subclass of DTDs for XPath satisfiability with sibling axes. In: Gardner, P., Geerts, F. (eds.) Database Programming Languages. LNCS, vol. 5708, pp. 68–83. Springer, Heidelberg (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ishihara, Y., Shimizu, S., Fujiwara, T. (2010). Extending the Tractability Results on XPath Satisfiability with Sibling Axes. In: Lee, M.L., Yu, J.X., Bellahsène, Z., Unland, R. (eds) Database and XML Technologies. XSym 2010. Lecture Notes in Computer Science, vol 6309. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15684-7_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-15684-7_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15683-0
Online ISBN: 978-3-642-15684-7
eBook Packages: Computer ScienceComputer Science (R0)