Containment of pattern-based queries over data trees

ABSTRACT

We study static analysis, in particular the containment problem, for analogs of conjunctive queries over XML documents. The problem has been studied for queries based on arbitrary patterns, not necessarily following the tree structure of documents. However, many applications force the syntactic shape of queries to be tree-like, as they are based on proper tree patterns. This renders previous results, crucially based on having non-tree-like features, inapplicable. Thus, we investigate static analysis of queries based on proper tree patterns. We go beyond simple navigational conjunctive queries in two ways: we look at unions and Boolean combinations of such queries as well and, crucially, all our queries handle data stored in documents, i.e., we deal with containment over data trees.

We start by giving a general Π^p₂ upper bound on the containment of conjunctive queries and Boolean combinations for patterns that involve all types of navigation through documents. We then show matching hardness for conjunctive queries with all navigation, or their Boolean combinations with the simplest form of navigation. After that we look at cases when containment can be witnessed by homomorphisms of analogs of tableaux. These include conjunctive queries and their unions over child and next-sibling axes; however, we show that not all cases of containment can be witnessed by homomorphisms. We look at extending tree patterns used in queries in three possible ways: with wildcard, with schema information, and with data value comparisons. The first one is relatively harmless, the second one tends to increase complexity by an exponential, and the last one quickly leads to undecidability.

References

1. S. Abiteboul, B. Cautis, T. Milo. Reasoning about XML update constraints. In PODS'07, pages 195--204.
2. S. Abiteboul, L. Segoufin, and V. Vianu. Representing and querying XML with incomplete information. ACM TODS, 31(1):208--254, 2006.
3. N. Alon, T. Milo, F. Neven, D. Suciu, V. Vianu. XML with data values: typechecking revisited. JCSS 66(4): 688--727 (2003).
4. S. Amano, L. Libkin, F. Murlak. XML schema mappings. In PODS'09, pages 33--42.
5. S. Amer-Yahia, S. Cho, L. Lakshmanan, D. Srivastava. Tree pattern query minimization. VLDB J. 11(4): 315--331 (2002).
6. M. Arenas, P. Barceló, L. Libkin, F. Murlak. Relational and XML Data Exchange. Morgan & Claypool, 2010.
7. M. Arenas, W. Fan, L. Libkin. On the complexity of verifying consistency of XML specifications. SIAM J. Comput. 38(3): 841--880 (2008).
8. M. Arenas, L. Libkin. XML data exchange: consistency and query answering. J. ACM 55(2): (2008).
9. P. Barceló, L. Libkin, A. Poggi, C. Sirangelo. XML with incomplete information. J. ACM, 58:1 (2010).
10. H. Björklund, W. Martens, T. Schwentick. Optimizing conjunctive queries over trees using schema information. MFCS'08, pages 132--143.
11. H. Björklund, W. Martens, and T. Schwentick. Conjunctive query containment over trees. JCSS 77(3): 450--472 (2011).
12. H. Björklund, W. Martens, T. Schwentick. Validity of tree pattern queries with respect to schema information. Unpublished manuscript.
13. M. Bojanczyk, C. David, A. Muscholl, T. Schwentick, L. Segoufin. Two-variable logic on words with data. In LICS'06, pages 7--16.
14. D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Y. Vardi. Regular XPath: constraints, query containment and view-based answering for XML documents. In LID'08.
15. A. Chandra and P. Merlin. Optimal implementation of conjunctive queries in relational data bases. In STOC 1977, pages 77--90.
16. C. David. Complexity of data tree patterns over XML documents. MFCS'08, pages 278--289.
17. W. Fan, L. Libkin. On XML integrity constraints in the presence of DTDs. J. ACM 49(3): 368--406 (2002).
18. D. Figueira. Satisfiability of downward XPath with data equality tests. PODS'09, 197--206.
19. P. Genevés and N. Layaida. A system for the static analysis of XPath. ACM TOIS 24 (2006), 475--502.
20. A. Gheerbrant, L. Libkin, and T. Tan. On the complexity of query answering over incomplete XML documents. ICDT 2012, 169--181.
21. G. Gottlob, C. Koch, K. Schulz. Conjunctive queries over trees. J. ACM 53 (2006), 238--272.
22. T. J. Green. Containment of conjunctive queries on annotated relations. Theory Comput. Syst. 49(2): 429--459 (2011).
23. A. Halevy. Answering queries using views: A survey. VLDB J. 10(4):270--294 (2001).
24. B. Kimelfeld, Y. Sagiv. Revisiting redundancy and minimization in an XPath fragment. EDBT'08, pages 61--72.
25. A. Klug. On conjunctive queries containing inequalities. J. ACM 35(1): 146--160 (1988).
26. P. Kolaitis, D. Martin, M. Thakur. On the complexity of the containment problem for conjunctive queries with built-in predicates. In PODS 1998, pages 197--204.
27. M. Lenzerini. Data integration: a theoretical perspective. In PODS'02, pages 233--246.
28. L. Libkin, C. Sirangelo. Reasoning about XML with temporal logics and automata. J. Applied Logic, 8:2, 210--232 (2010).
29. W. Martens, F. Neven, T. Schwentick. Simple off the shelf abstractions for XML schema. SIGMOD Record 36(3): 15--22 (2007).
30. S. Maneth, T. Perst, H. Seidl. Exact XML type checking in polynomial time. In ICDT 2007, pages 254--268.
31. G. Miklau and D. Suciu. Containment and equivalence for a fragment of XPath. J. ACM, 51(1): 2--45, 2004.
32. F. Neven. Automata, logic, and XML. In CSL 2002, pages 2--26.
33. F. Neven, T. Schwentick. On the complexity of XPath containment in the presence of disjunction, DTDs, and variables. LMCS, 2(3): (2006).
34. Y. Sagiv, M. Yannakakis. Equivalences among relational expressions with the union and difference operators. J. ACM 27(4): 633--655 (1980).
35. Th. Schwentick. XPath query containment. SIGMOD Record 33(1): 101--109 (2004).
36. J. W. Thatcher. Characterizing derivation trees of context-free grammars through a generalization of finite automata theory. JCSS 1 (1967), 317--322.
37. R. van der Meyden. The complexity of querying indefinite data about linearly ordered domains. JCSS 54(1): 113--135 (1997).
38. V. Vianu. A web Odyssey: from Codd to XML. In PODS'01, pages 1--15.

Index Terms

• Information systems

  • Data management systems

    • Query languages

• Theory of computation

  • Design and analysis of algorithms