Abstract
We study the satisfiability problem for XPath fragments supporting the following-sibling and preceding-sibling axes. Although this problem was recently studied for XPath fragments without sibling axes, little is known about the impact of the sibling axes on the satisfiability analysis. To this end we revisit the satisfiability problem for a variety of XPath fragments with sibling axes, in the presence of DTDs, in the absence of DTDs, and under various restricted DTDs. In these settings we establish complexity bounds ranging from NLOGSPACE to undecidable. Our main conclusion is that in many cases, the presence of sibling axes complicates the satisfiability analysis. Indeed, we show that there are XPath satisfiability problems that are in PTIME and PSPACE in the absence of sibling axes, but that become NP-hard and EXPTIME-hard, respectively, when sibling axes are used instead of the corresponding vertical modalities (e.g., the wildcard and the descendant axis).
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
Amer-Yahia, S., Cho, S., Lakshmanan, L., Srivistava, D.: Minimization of tree pattern queries. In: SIGMOD (2001)
Benedikt, M., Fan, W., Geerts, F.: XPath satisfiability in the presence of DTDs. In: PODS (2005)
Benedikt, M., Fan, W., Kuper, G.M.: Structural properties of XPath fragments. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol. 2572, pp. 79–95. Springer, Heidelberg (2002)
Börger, E., Grädel, E., Gurevich, Y.: The Classical Decision Problem. Springer, Heidelberg (1997)
Bray, T., Paoli, J., Sperberg-McQueen, C.M.: Extensible Markup Language (XML) 1.0. W3C Recommendation (February 1998), http://www.w3.org/TR/REC-xml
Buneman, P., Davidson, S., Fan, W., Hara, C., Tan, W.: Keys for XML. Computer Networks 39(5), 473–487 (2002)
Clark, J., DeRose, S.: XML Path Language (XPath). W3C Recommendation (November 1999)
Deutsch, A., Tannen, V.: Containment for classes of XPath expressions under integrity constraints. In: KRDB (2001)
Deutsch, A., Tannen, V.: Reformulation of XML queries and constraints. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol. 2572, pp. 225–238. Springer, Heidelberg (2002)
Fan, W., Chan, C., Garofalakis, M.: Secure XML querying with security views. In: SIGMOD (2004)
Gottlob, G., Koch, C., Pichler, R.: Efficient algorithms for processing XPath queries. In: VLDB (2002)
Gottlob, G., Koch, C., Schulz, K.: Conjunctive queries over trees. In: PODS (2004)
Hidders, J.: Satisfiability of XPath expressions. In: Lausen, G., Suciu, D. (eds.) DBPL 2003. LNCS, vol. 2921, pp. 21–36. Springer, Heidelberg (2004)
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation, 2nd edn. Addison Wesley, Reading (2000)
Lakshmanan, L., Ramesh, G., Wang, H., Zhao, Z.: On testing satisfiability of tree pattern queries. In: VLDB (2004)
Libkin, L.: Logics over unranked trees: an overview. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 35–50. Springer, Heidelberg (2005)
Marx, M.: XPath with conditional axis relations. In: Bertino, E., Christodoulakis, S., Plexousakis, D., Christophides, V., Koubarakis, M., Böhm, K., Ferrari, E. (eds.) EDBT 2004. LNCS, vol. 2992, pp. 477–494. Springer, Heidelberg (2004)
Marx, M.: First order paths in ordered trees. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol. 3363, pp. 114–128. Springer, Heidelberg (2004)
Miklau, G., Suciu, D.: Containment and equivalence for a fragment of XPath. JACM 51(1), 2–45 (2004)
Murata, M.: Extended path expressions for XML. In: PODS (2001)
Neven, F., Schwentick, T.: Expressive and efficient languages for tree-structured data. In: PODS (2000)
Neven, F., Schwentick, T.: XPath containment in the presence of disjunction, DTDs, and variables. In: ICDT (2003)
Olteanu, D., Meuss, H., Furche, T., Bry, F.: XPath: Looking forward. In: XMLDM (2002)
Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)
Schwentick, T.: Xpath query containment. SIGMOD Rec. 33(1), 101–109 (2004)
Sur, G., Hammer, J., Siméon, J.: An XQuery-based language for processing updates in XML. In: PLAN-X (2004)
Thompson, H., et al.: XML Schema. W3C Recommendation (October 2004), http://www.w3.org/TR/xmlschema1
Wood, P.T.: Minimising simple XPath expressions. In: WebDB (2001)
Wood, P.T.: Containment for XPath fragments under DTD constraints. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol. 2572, pp. 297–311. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Geerts, F., Fan, W. (2005). Satisfiability of XPath Queries with Sibling Axes. In: Bierman, G., Koch, C. (eds) Database Programming Languages. DBPL 2005. Lecture Notes in Computer Science, vol 3774. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11601524_8
Download citation
DOI: https://doi.org/10.1007/11601524_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30951-2
Online ISBN: 978-3-540-31445-5
eBook Packages: Computer ScienceComputer Science (R0)