skip to main content
10.1145/1055558.1055585acmconferencesArticle/Chapter ViewAbstractPublication PagespodsConference Proceedingsconference-collections
Article

Conjunctive queries over trees

Published: 14 June 2004 Publication History

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]
S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.]]
[2]
R. Baumgartner, S. Flesca, and G. Gottlob. "Visual Web Information Extraction with Lixto". In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB'01), 2001.]]
[3]
M. Benedikt, W. Fan, and G. Kuper. "Structural Properties of XPath Fragments". In Proc. of the 9th International Conference on Database Theory (ICDT'03), 2003.]]
[4]
M. Bodirsky, D. Duchier, J. Niehren, and S. Miele. "A New Algorithm for Normal Dominance Constraints". In Proc. SODA, 2004.]]
[5]
A. K. Chandra and P. M. Merlin. "Optimal Implementation of Conjunctive Queries in Relational Data Bases". In Conference Record of the Ninth Annual ACM Symposium on Theory of Computing (STOC'77), pages 77 90, Boulder, CO USA, May 1977.]]
[6]
C. Chekuri and A. Rajaraman. Conjunctive Query Containment Revisited". In Proc. of the 6th International Conference on Database Theory (ICDT'97), pages 56--70, 1997.]]
[7]
R. Dechter. "Constraint Processing". Morgan Kaufmann, May 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]
A. Deutsch and V. Tannen. "Reformulation of XML Queries and Constraints". In Proc. of the 9th International Conference on Database Theory (ICDT'03), pages 225--241, 2003.]]
[10]
H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer-Verlag, 1999. Second edition.]]
[11]
J. Flum, M. Frick, and M. Grohe. "Query Evaluation via Tree-Decompositions". In J. Van den Bussche and V. Vianu, editors, Proc. of the 8th International Conference on Database Theory (ICDT'01), volume 1973 of Lecture Notes in Computer Science, pages 22--38, London, UK, Jan. 2001. Springer.]]
[12]
G. Gottlob and C. Koch. "Monadic Queries over Tree-Structured Data." In Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science (LICS), pages 189--202, Copenhagen, Denmark, July 2002.]]
[13]
G. Gottlob and C. Koch. "Monadic Datalog and the Expressive Power of Web Information Extraction Languages". Journal of the ACM, 51(1):74--113, 2004.]]
[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]
G. Gottlob, C. Koch, and R. Pichler. "The Complexity of XPath Query Processing". In Proceedings of the 22nd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS'03), 2003.]]
[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]
D. Maier. The Theory of Relational Databases. Computer Science Press, 1983.]]
[19]
M. P. Marcus, D. Hindle, and M. M. Fleck. "D-Theory: Talking about Talking about Trees". In Proc. ACL, pages 129--136, 1983.]]
[20]
H. Meuss and K. U. Schulz. "Complete Answer Aggregates for Tree-like Databases: A Novel Approach to Combine Querying and Navigation" ACM Transactions on Information Systems, 19(2):161--215, 2001.]]
[21]
H. Meuss, K. U. Schulz, and F. Bry. "Towards Aggregated Answers for Semistructured Data". In Proc. of the 8th International Conference on Database Theory (ICDT'01), pages 346--360, 2001.]]
[22]
M. Minoux. "LTUR: A Simplified Linear-Time Unit Resolution Algorithm for Horn Formulae and Computer Implementation". Information Processing Letters, 29(1):1 12, 1988.]]
[23]
D. Olteanu, H. Meuss, T. Furche, and F. Bry. "Symmetry in XPath". In Proc. EDBT Workshop on XML Data Management, 2002.]]
[24]
T. Schaefer. "The Complexity of Satisfiability Problems". In Proc. 10th Ann. ACM Symp. on Theory of Computing (STOC), pages 216--226, 1978.]]
[25]
M. Schmidt-Schauss and K. U. Schulz. "On the Exponent of Periodicity of Minimal Solutions of Context Equations". In Proc. 9th Int. Conf. on Rewriting Techniques and Applications, pages 61--75, 1998.]]
[26]
M. Schmidt-Schauß and J. Stuber. "On the Complexity of Linear and Stratified Context Matching Problems", 2001. Unpublished manuscript.]]
[27]
T. Schwentick. "On Diving in Trees". In Proc. MFCS, pages 660--669, 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.]]

Cited By

View all
  • (2022)Relational and XML Data ExchangeundefinedOnline publication date: 23-Feb-2022
  • (2017)Logic, Languages, and Rules for Web Data Extraction and Reasoning over DataLanguage and Automata Theory and Applications10.1007/978-3-319-53733-7_2(27-47)Online publication date: 16-Feb-2017
  • (2012)Processing and Evaluating Partial Tree Pattern Queries on XML DataIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2011.13724:12(2244-2259)Online publication date: 1-Dec-2012
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODS '04: Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
June 2004
350 pages
ISBN:158113858X
DOI:10.1145/1055558
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2004

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

SIGMOD/PODS04

Acceptance Rates

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 30 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2022)Relational and XML Data ExchangeundefinedOnline publication date: 23-Feb-2022
  • (2017)Logic, Languages, and Rules for Web Data Extraction and Reasoning over DataLanguage and Automata Theory and Applications10.1007/978-3-319-53733-7_2(27-47)Online publication date: 16-Feb-2017
  • (2012)Processing and Evaluating Partial Tree Pattern Queries on XML DataIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2011.13724:12(2244-2259)Online publication date: 1-Dec-2012
  • (2010)Automated interaction in social networks with datalogProceedings of the 19th ACM international conference on Information and knowledge management10.1145/1871437.1871599(1273-1276)Online publication date: 26-Oct-2010
  • (2010)Web and Document DatabasesProceedings of the 2010 IEEE/ACIS 9th International Conference on Computer and Information Science10.1109/ICIS.2010.66(529-534)Online publication date: 18-Aug-2010
  • (2010)Querying Linguistic TreesJournal of Logic, Language and Information10.1007/s10849-009-9086-919:1(53-73)Online publication date: 1-Jan-2010
  • (2010)Scope Underspecification with Tree Descriptions: Theory and PracticeResource-Adaptive Cognitive Processes10.1007/978-3-540-89408-7_15(337-364)Online publication date: 5-Feb-2010
  • (2009)From XQuery to relational logicsACM Transactions on Database Systems10.1145/1620585.162059234:4(1-48)Online publication date: 14-Dec-2009
  • (2009)XPath leashedACM Computing Surveys10.1145/1456650.145665341:1(1-54)Online publication date: 15-Jan-2009
  • (2009)Logical Foundations of XML and XQueryReasoning Web. Semantic Technologies for Information Systems10.1007/978-3-642-03754-2_3(111-157)Online publication date: 1-Sep-2009
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media