Conjunctive queries over trees

ABSTRACT

We study the complexity and expressive power of conjunctive queries over unranked labeled trees, where the tree structure are represented using "axis relations" such as "child", "descendant", and "following" (we consider a superset of the XPath axes) as well as unary relations for node labels. (Cyclic) conjunctive queries over trees occur in a wide range of data management scenarios related to XML, the Web, and computational linguistics. We establish a framework for characterizing structures representing trees for which conjunctive queries can be evaluated efficiently. Then we completely chart the tractability frontier of the problem for our axis relations, i.e., we find all subset maximal sets of axes for which query evaluation is in polynomial time. All polynomial-time results are obtained immediately using the proof techniques from our framework. Finally, we study the expressiveness of conjunctive queries over trees and compare it to the expressive power of fragments of XPath. We show that for each conjunctive query, there is an equivalent acyclic positive query (i.e., a set of acyclic conjunctive queries), but that in general this query is not of polynomial size.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Robert Baumgartner , Sergio Flesca , Georg Gottlob, Visual Web Information Extraction with Lixto, Proceedings of the 27th International Conference on Very Large Data Bases, p.119-128, September 11-14, 2001
• 3: Michael Benedikt , Wenfei Fan , Gabriel M. Kuper, Structural Properties of XPath Fragments, Proceedings of the 9th International Conference on Database Theory, p.79-95, January 08-10, 2003
• 4: Manuel Bodirsky , Denys Duchier , Joachim Niehren , Sebastian Miele, A new algorithm for normal dominance constraints, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 5: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 6: Chandra Chekuri , Anand Rajaraman, Conjunctive Query Containment Revisited, Proceedings of the 6th International Conference on Database Theory, p.56-70, January 08-10, 1997
• 7: Rina Dechter, Constraint Processing, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 8: A. Deutsch and V. Tannen. "MARS: A System for Publishing XML from Mixed and Redundant Storage". In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB'03), pages 201--212, 2003.
• 9: Alin Deutsch , Val Tannen, Reformulation of XML Queries and Constraints, Proceedings of the 9th International Conference on Database Theory, p.225-241, January 08-10, 2003
• 10: H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer-Verlag, 1999. Second edition.
• 11: Jörg Flum , Markus Frick , Martin Grohe, Query Evaluation via Tree-Decompositions, Proceedings of the 8th International Conference on Database Theory, p.22-38, January 04-06, 2001
• 12: Georg Gottlob , Christoph Koch, Monadic Queries over Tree-Structured Data, Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science, p.189-202, July 22-25, 2002
• 13: Georg Gottlob , Christoph Koch, Monadic datalog and the expressive power of languages for Web information extraction, Journal of the ACM (JACM), v.51 n.1, p.74-113, January 2004 [doi>10.1145/962446.962450]
• 14: G. Gottlob, C. Koch, and R. Pichler. "Efficient Algorithms for Processing XPath Queries". In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB'02), Hong Kong, China, 2002.
• 15: Georg Gottlob , Christoph Koch , Reinhard Pichler, The complexity of XPath query evaluation, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.179-190, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773171]
• 16: J. Hidders. "Satisfiability of XPath Expressions". In Proc. DBPL, 2003.
• 17: LDC. "The Penn Treebank Project", 1999. http://www.cis.upenn.edu/~treebank/home.html.
• 18: David Maier, Theory of Relational Databases, Computer Science Pr, 1983
• 19: Mitchell P. Marcus , Donald Hindle , Margaret M. Fleck, D-theory: talking about talking about trees, Proceedings of the 21st annual meeting on Association for Computational Linguistics, June 15-17, 1983, Cambridge, Massachusetts [doi>10.3115/981311.981337]
• 20: Holger Meuss , Klaus U. Schulz, Complete answer aggregates for treelike databases: a novel approach to combine querying and navigation, ACM Transactions on Information Systems (TOIS), v.19 n.2, p.161-215, April 2001 [doi>10.1145/382979.383042]
• 21: Holger Meuss , Klaus U. Schulz , François Bry, Towards Aggregated Answers for Semistructured Data, Proceedings of the 8th International Conference on Database Theory, p.346-360, January 04-06, 2001
• 22: M. Minoux, LTUR: a simplified linear-time unit resolution algorithm for Horn formulae and computer implementation, Information Processing Letters, v.29 n.1, p.1-12, Sept. 15, 1988 [doi>10.1016/0020-0190(88)90124-X]
• 23: D. Olteanu, H. Meuss, T. Furche, and F. Bry. "Symmetry in XPath". In Proc. EDBT Workshop on XML Data Management, 2002.
• 24: Thomas J. Schaefer, The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing, p.216-226, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804350]
• 25: Manfred Schmidt-Schauß , Klaus U. Schulz, On the Exponent of Periodicity of Minimal Solutions of Context Equation, Proceedings of the 9th International Conference on Rewriting Techniques and Applications, p.61-75, March 30-April 01, 1998
• 26: M. Schmidt-Schauß and J. Stuber. "On the Complexity of Linear and Stratified Context Matching Problems", 2001. Unpublished manuscript.
• 27: Thomas Schwentick, On Diving in Trees, Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science, p.660-669, September 01, 2000
• 28: World Wide Web Consortium. XML Path Language (XPath) Recommendation. http://www.w3c.org/TR/xpath/, Nov. 1999.
• 29: M. Yannakakis. "Algorithms for Acyclic Database Schemes". In Proceedings of the 7th International Conference on Very Large Data Bases (VLDB'81), 1981.