Article

Free access

Expressive and efficient pattern languages for tree-structured data (extended abstract)

Authors:

Thomas SchwentickAuthors Info & Claims

PODS '00: Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

Pages 145 - 156

https://doi.org/10.1145/335168.335217

Published: 01 May 2000 Publication History

Abstract

It would be desirable to have a query language for tree-structured data that is (1) as easily usable as SQL, (2) as expressive as monadic second-order logic (MSO), and (3) efficiently evaluable. The paper develops some ideas in this direction. Towards (1) the specification of sets of vertices of a tree by combining conditions on their induced subtree with conditions on their path to the root is proposed. Existing query languages allow regular expressions (hence MSO logic) in path conditions but are limited in expressing subtree conditions. It is shown that such query languages fall short of capturing all MSO queries. On the other hand, allowing a certain guarded fragment of MSO-logic in the specification of subtree conditions results in a language fulfilling (2), (3) and, anguably, (1).

References

[1]

S. Abiteboul, P. Buneman, and D. Suciu. Data on the Web : From Relations to Semistructured Data and XML. Morgan Kaufmann, 1999.]]

Digital Library

[2]

S. Abiteboul, ~. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.]]

Digital Library

[3]

S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. L. Wiener. The lorel query language for semistructured data. International Journal on Digital Libraries, 1(1):68-88, 1997.]]

[4]

S. Abiteboul and V. Vianu. Regular path queries with constraints. In Proc. PODS Conf., 1997.]]

Digital Library

[5]

N. Alechina and N. Immerman. Efficient fragment of transitive closure logic. Unpublished, 1999.]]

[6]

H. Andr~ka, J. van Benthem, and I. N~meti. Modal languages and bounded fragments of predicate logic. Journal of Philosophical Logic, 27:217-274, 1998.]]

[7]

P. Buneman, S. Davidson, G. G. Hillebrand, and D.Suciu. A query language and optimization techniques for unstructured data. In Proc. SIGMOD Conf., 1996.]]

Digital Library

[8]

P. Buneman, W. Fan, and S. Weinstein. Path constraints on semistructured and structured data. In Proc. PODS Conf., 1998.]]

Digital Library

[9]

D. Calvanese, D. G. Giacomo, M. Lenzerini, and M. Y. Vardi. Rewriting of regular expressions and regular path queries. In Proc. PODS Conf., 1999.]]

Digital Library

[10]

J. Clark. XSL transformations version 1.0. http://www.w3.org/TR/WD-xslt, august 1999.]]

[11]

S. Cluet, C. Delobel, J. Simeon, and K. Smaga. Your mediators need data conversion! In Proc. SIGMOD Conf., 1998.]]

Digital Library

[12]

A. Deutsch, M. Fernandez, D. Florescu, A. Levy, and D. Suciu. XML-QL: a query language for XML. In Proc. WWW8 Conf., 1999.]]

Digital Library

[13]

H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer, 1995.]]

[14]

M. Fernandez, J. Simeon, and P. Wadler, editors. XML Query languages: Experiences and Exemplars, 1999. http://www-db.research.belll abs.com/user/simeon/xquery.html.]]

[15]

M. F. Fernandez, D. Florescu, J. Kang, A. Y. Levy, and D. Suciu. Catching the boat with strudel: Experiences with a web-site management system. In Proc. SIGMOD Conf., 1998.]]

Digital Library

[16]

G. Gottlob, E. Gr~del, and H. Veith. Linear time datalog. Unpublished, 1999.]]

[17]

N. Klarlund. Mona ~ Fido: The logic-automaton connection in practice. In Proc. CSL Conf., 1998.]]

Digital Library

[18]

S. Maneth and F. Neven. A formalization of tree transformations in XSL. In Proc. DBPL Conf., 1999.]]

[19]

A. O. Mendelzon and P. T. Wood. Finding regular simple paths in graph databases. SIAM Journal on Computing, 24(6):1235-1258, 1995.]]

Digital Library

[20]

F. Neven. Design and Analysis of Query Languages for Structured Documents A Formal and Logical Approach. Doctor's thesis, Limburgs Universitair Centrum (LUC), 1999.]]

[21]

F. Neven. Extensions of attribute grammars for structured document queries. In Proc. DBPL Conf., 1999.]]

Digital Library

[22]

F. Neven and T. Schwentick. Query automata. In Proc. PODS Conf., 1999.]]

Digital Library

[23]

F. Neven and J. Van den Bussche. Expressiveness of structured document query languages based on attribute grammars. In Proc. PODS Conf., 1998.]]

Digital Library

[24]

Y. Papakonstantinou and V. Vianu. DTD inference for views of XML data. This proceedings.]]

Digital Library

[25]

A. Potthoff. Logische Klassifizierung regul~rer Baumsprachen. Doctor's thesis, Institut fiir Informatik u. Prakt. Math., Universit~t Kiel, 1994.]]

[26]

J. Robie. The design of XQL. http://www, t excel, no / whit ep ap ers / xql- design, ht ml, 1999.]]

[27]

D. Suciu. Semistructured data and XML. In Proc. FODO Conf., 1998.]]

[28]

W. Thomas. Classifying regular events in symbolic logic. Journal of Computer and System Sciences, 25(3):360-376, 1982.]]

[29]

W. Thomas. Logical aspects in the study of tree languages. In Proc. CAAP Conf., 1984.]]

Digital Library

[30]

W. Thomas. On chain logic, path logic, and first-order logic over infinite trees. In Proc. LICS Conf., 1987.]]

[31]

W. Thomas. Languages, automata, and logic. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 3, chapter 7. Springer, 1997.]]

Digital Library

Cited By

Liu XCai ZMiao DLi J(2016)On the Complexity of Extracting Subtree with Keeping DistinguishabilityCombinatorial Optimization and Applications10.1007/978-3-319-48749-6_17(230-240)Online publication date: 31-Oct-2016
https://doi.org/10.1007/978-3-319-48749-6_17
Antonopoulos THovland DMartens WNeven F(2015)Deciding Twig-definability of Node Selecting Tree AutomataTheory of Computing Systems10.1007/s00224-015-9623-757:4(967-1007)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1007/s00224-015-9623-7
Lakshmanan LThomo A(2014)View-Based Tree-Language Rewritings for XMLProceedings of the 8th International Symposium on Foundations of Information and Knowledge Systems - Volume 836710.1007/978-3-319-04939-7_13(270-289)Online publication date: 3-Mar-2014
https://dl.acm.org/doi/10.1007/978-3-319-04939-7_13
Show More Cited By

Index Terms

Expressive and efficient pattern languages for tree-structured data (extended abstract)
1. Information systems
  1. Data management systems
    1. Query languages
2. Theory of computation
  1. Logic
  2. Theory and algorithms for application domains
    1. Database theory
      1. Database query languages (principles)

Recommendations

Expressive power and data complexity of nonrecursive query languages for lists and trees (extended abstract)
PODS '00: Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

We extend the traditional query languages by primitives for handling lists and trees. Our main results characterize the expressive power and data complexity of the following extended languages: (1) relational algebra with lists and trees, (2) ...
On the expressive power of query languages

Two main topics are addressed. First, an algebraic approach is presented to define a general notion of expressive power. Heterogeneous algebras represent information systems and morphisms represent the correspondences between the instances of databases, ...
Expressive Languages for Path Queries over Graph-Structured Data

For many problems arising in the setting of graph querying (such as finding semantic associations in RDF graphs, exact and approximate pattern matching, sequence alignment, etc.), the power of standard languages such as the widely studied conjunctive ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS '00: Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

May 2000

281 pages

ISBN:158113214X

DOI:10.1145/335168

Chairmen:
Victor Vianu
Univ. of California at San Diego, La Jolla
,
Georg Gottlob
Technische Univ. Wien, Vienna, Austria

Copyright © 2000 ACM.

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

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 2000

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS00

Sponsor:

SIGMOD

SIGMOD/PODS00: ACM International Conference on Management of Data and Symposium on Principles of Database Systems

May 15 - 18, 2000

Texas, Dallas, USA

Acceptance Rates

PODS '00 Paper Acceptance Rate 26 of 119 submissions, 22%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

55
Total Citations
View Citations
461
Total Downloads

Downloads (Last 12 months)58
Downloads (Last 6 weeks)8

Reflects downloads up to 29 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu XCai ZMiao DLi J(2016)On the Complexity of Extracting Subtree with Keeping DistinguishabilityCombinatorial Optimization and Applications10.1007/978-3-319-48749-6_17(230-240)Online publication date: 31-Oct-2016
https://doi.org/10.1007/978-3-319-48749-6_17
Antonopoulos THovland DMartens WNeven F(2015)Deciding Twig-definability of Node Selecting Tree AutomataTheory of Computing Systems10.1007/s00224-015-9623-757:4(967-1007)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1007/s00224-015-9623-7
Lakshmanan LThomo A(2014)View-Based Tree-Language Rewritings for XMLProceedings of the 8th International Symposium on Foundations of Information and Knowledge Systems - Volume 836710.1007/978-3-319-04939-7_13(270-289)Online publication date: 3-Mar-2014
https://dl.acm.org/doi/10.1007/978-3-319-04939-7_13
Antonopoulos THovland DMartens WNeven FDeutsch A(2012)Deciding twig-definability of node selecting tree automataProceedings of the 15th International Conference on Database Theory10.1145/2274576.2274584(61-73)Online publication date: 26-Mar-2012
https://dl.acm.org/doi/10.1145/2274576.2274584
Kaneta YArimura HRaman R(2012)Faster bit-parallel algorithms for unordered pseudo-tree matching and tree homeomorphismJournal of Discrete Algorithms10.1016/j.jda.2011.12.01814(119-135)Online publication date: 1-Jul-2012
https://dl.acm.org/doi/10.1016/j.jda.2011.12.018
Liu HMa Y(2011)Web Data Extraction Research Based on Wrapper and XPath TechnologyAdvanced Materials Research10.4028/www.scientific.net/AMR.271-273.706271-273(706-712)Online publication date: Jul-2011
https://doi.org/10.4028/www.scientific.net/AMR.271-273.706
Zhao YWang ZXiao HPing JPu GHe JZhu H(2011)A Unifying Approach to Validating Specification-Oriented XML ConstraintsProceedings of the 2011 IEEE 13th International Symposium on High-Assurance Systems Engineering10.1109/HASE.2011.28(33-40)Online publication date: 10-Nov-2011
https://dl.acm.org/doi/10.1109/HASE.2011.28
Cohen SKimelfeld BSagiv YParedaens JSu J(2009)Running tree automata on probabilistic XMLProceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems10.1145/1559795.1559831(227-236)Online publication date: 29-Jun-2009
https://dl.acm.org/doi/10.1145/1559795.1559831
Kaminski MTan T(2008)Tree automata over infinite alphabetsPillars of computer science10.5555/1805839.1805860(386-423)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.5555/1805839.1805860
Benedikt MFan WGeerts F(2008)XPath satisfiability in the presence of DTDsJournal of the ACM10.1145/1346330.134633355:2(1-79)Online publication date: 15-May-2008
https://dl.acm.org/doi/10.1145/1346330.1346333
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents