Article

Flexible queries over semistructured data

Authors:

Yehoshua SagivAuthors Info & Claims

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

Pages 40 - 51

https://doi.org/10.1145/375551.375558

Published: 01 May 2001 Publication History

Abstract

Flexible queries facilitate, in a novel way, easy and concise querying of databases that have varying structures. Two different semantics, flexible and semiflexible, are introduced and investigated. The complexity of evaluating queries under the two semantics is analyzed. Query evaluation is polynomial in the size of the query, the database and the result in the following two cases. First, a semiflexible DAG query and a tree database. Second, a flexible tree query and a database that is any graph. Query containment and equivalence are also investigated. For the flexible semantics, query equivalence is always polynomial. For the semiflexible semantics, query equivalence is polynomial for DAG queries and exponential when the queries have cycles. Under the semiflexible and flexible semantics, two databases could be equivalent even when they are not isomorphic. Database equivalence is formally defined and characterized. The complexity of deciding equivalences among databases is analyzed. The implications of database equivalence on query evaluation are explained.

References

[1]

S. Abiteboul. Querying semi-structured data. In International Conference on Database Theory, volume 1186 of Lecture Notes in Computer Science pages 1-18, Delphi (Greece), Jan. 1997. Springer-Verlag.]]

Digital Library

[2]

S. Abiteboul, P. Buneman, and D. Suciu. Data on the Web. Morgan Kanfmann, 2000.]]

[3]

S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. 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 Proe. 16th Symposium on Principles of Database Systems, pages 122-133, Tucson (Arizona, USA), May 1997. ACM Press.]]

Digital Library

[5]

P. Atzeni, G. Mecca, and P. Merialdo. To weave the Web. In Proe. 23nd International Conference on Very Large Data Bases, pages 206-215, Athens (Greece), Aug. 1997. Morgan Kanfmann Publishers.]]

Digital Library

[6]

Z. Bar-Yossef, Y. Kanza, Y. Kogan, W. Nutt, and Y. Sagiv. Querying semantically tagged documents on the world-wide web. In Proc. 4th International Workshop on Next Generation Information Technologies and Systems, Zichron Yaakov (Israel), July 1999. Springer-Verlag.]]

Digital Library

[7]

C. Baru, A. Gupta, B. Ludacher, R. Marciano, Y. Papakonstantinou, and P. Valikhov. Xml-base information mediation with mix. In SIGMOD System Demonstration, 1999.]]

Digital Library

[8]

T. Bray, J. Paoli, C. M. Sperberg-McQueen, and E. Maler, editors. The World Wide Web Consortium (W3C)'s XML web page. http://www.w3c, org/XXI, 1998.]]

[9]

P. Buneman. Semistructured data. In Proc. 16th Symposium on Principles of Database Systems, pages 117-121, Tucson (Arizona, USA), May 1997. ACM Press.]]

Digital Library

[10]

P. Buneman, S. Davidson, M. Fernandez, and D. Suciu. Adding structure to unstructured data. In International Conference on Database Theory, pages 336-350, Delphi (Greece), Jan. 1997. Springer-Verlag.]]

Digital Library

[11]

P. Buneman, S. Davidson, G. Hillebrand, and D. Suciu. A query language and optimization techniques for unstructured data. In Proc. 1996 ACM SIGMOD International Conference on Management of Data, pages 505-516, Montreal (Canada), June 1996.]]

Digital Library

[12]

P. Buneman, W. Fan, and S. Weinstein. Path constraints in semistructured and structured databases. In Proc. 17th Symposium on Principles of Database Systems, pages 129-138, Seattle (Washington, USA), June 1998. ACM Press.]]

Digital Library

[13]

S. Chawathe, S. Abiteboul, and J. Widom. Representing and querying changes in semistructured data. In Proc. 14th International Conference on Data Engineering, pages 4-13, Orlando (Florida, USA), Feb. 1998. IEEE Computer Society.]]

Digital Library

[14]

I. Cruz, A. Mendelzon, and P. Wood. A graphical query language supporting recursion. In Proc. 1982 International Conference on Management of Data, pages 323-330, Orlando (Florida, USA), June 1982.]]

Digital Library

[15]

A. Deutsch, M. Fernandez, D. Florescu, A. Levi, and D. Suciu. A query language for xml. In Proc. of the World Wide Web Conference, 1999.]]

Digital Library

[16]

R. Fagin. Degree of acyclicity for hypergraphs and relational database schemas. J. ACM, 7(3):343-360, 1983.]]

Digital Library

[17]

R. Goldman and J. Widom. Dataguides: enabling query formulation and optimization in semistructured databases. In Proc. 23nd International Conference on Very Large Data Bases, Athens (Greece), Aug. 1997. Morgan Kanfmann Publishers.]]

Digital Library

[18]

G. Grahne and L. V. S. Lakshmanan. On the difference between navigating semistructered data and querying it. In 8th International Workshop on Database Programming Languages, Kinloch Rannoch (Scotland), Sept. 1999.]]

Digital Library

[19]

Y. Kanza, W. Nutt, and Y. Sagiv. Queries with incomplete answers over semistructured data. In pods99, pages 227-236, Philadelphia (Pennsylvania, USA), June 1999. ACM Press.]]

Digital Library

[20]

L. Lakshmanan, F. Sadri, and I. Subramanian. A declarative language for querying and restructuring the web. In Proe. 6th International Workshop on Research Issues on Data Engineering - Interoperability of Nontraditional Database Systems, pages 12-21, New Orleans (Louisiana, USA), Feb. 1996. IEEE Computer Society.]]

Digital Library

[21]

D. Maier, Y. Sagiv, and M. Yannakakis. On the complexity of testing implications of functional and join dependencies. J. ACM, 28(4):680-695, 1981.]]

Digital Library

[22]

G. Mecca, P. Atzeni, A. Masci, P. Merialdo, and G. Sindoni. The Araneus web-base management system. In Proe. 1998 ACM SIGMOD International Conference on Management of Data, pages 544-546, Seattle (Vqashington, USA), June 1998. ACM Press.]]

Digital Library

[23]

A. Mendelzon and T. Milo. Formal models of web queries. In Proe. 16th Symposium on Principles of Database Systems, pages 134-143, Tucson (Arizona, USA), May 1997. ACM Press.]]

Digital Library

[24]

A. Mendelzon and P. Wood. Finding regular simple paths in graph databases. SIAM Journal on Computing, 24(5), 1995.]]

Digital Library

[25]

F. Neven and T. Schwentick. Expressive and efficient pattern languages for tree-structured data. In Proc. 19th Symposium on Principles of Database Systems, pages 145-156, Dallas (Texas, USA), May 2000. ACM Press.]]

Digital Library

[26]

Y. Papakonstantinou, H. Garcia-Molina, and J. Widom. Object exchange acroos heterogeneous information sources. In Proc. 11th International Conference on Data Engineering, pages 251-260, Taipei, Mar. 1995. IEEE Computer Society.]]

Digital Library

[27]

A. Rajaraman and J. Ullman. Integrating information by outerjoins and full disjunctions. In Proc. 15th Symposium on Principles of Database Systems, pages 238-248, Montreal (Canada), June 1996. ACM Press.]]

Digital Library

[28]

M. Yannakakis. Algorithms for acyclic database schemes. In Proc. 7th International Conference on Very Large Data Bases, pages 82-94, Cannes (France), Sept. 1981. IEEE Computer Society.]]

Cited By

Swami SAryal SBhowmick SDyreson C(2023)Using a Conceptual Model in Plug-and-Play SQLConceptual Modeling10.1007/978-3-031-47262-6_8(145-161)Online publication date: 6-Nov-2023
https://dl.acm.org/doi/10.1007/978-3-031-47262-6_8
Reznichenko V(2022)60 Years of Databases (part four)PROBLEMS IN PROGRAMMING10.15407/pp2022.02.057(57-95)Online publication date: Jun-2022
https://doi.org/10.15407/pp2022.02.057
Pivert OSmits GThion V(2021)Expression and efficient processing of fuzzy queries in a graph database context2015 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE)10.1109/FUZZ-IEEE.2015.7337849(1-8)Online publication date: 9-Mar-2021
https://dl.acm.org/doi/10.1109/FUZZ-IEEE.2015.7337849
Show More Cited By

Index Terms

Flexible queries over semistructured data
1. Information systems
  1. Data management systems
    1. Database design and models
    2. Query languages
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query languages (principles)

Recommendations

Approximating expressive queries on graph-modeled data

We present GeX for the approximate matching of complex queries on graph-modeled data.GeX generalizes existing approaches and allows for querying any graph-based datasets.GeX query language supports queries ranging from keyword-based to complex ones.GeX ...
View-Based Query Answering and Query Containment over Semistructured Data
DBPL '01: Revised Papers from the 8th International Workshop on Database Programming Languages

The basic querying mechanism over semistructured data, namely regular path queries, asks for all pairs of objects that are connected by a path conforming to a regular expression. We consider conjunctive two-way regular path queries (C2RPQ_c's), which ...
Weighted path queries on semistructured databases

Path queries have been extensively used to query semistructured data, such as the Web and XML documents. In this paper we introduce weighted path queries, an extension of path queries enabling several classes of optimization problems (such as the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

May 2001

301 pages

ISBN:1581133618

DOI:10.1145/375551

Chairman:
Peter Buneman
Univ. of Pennsylvania

Copyright © 2001 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 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS01

Sponsor:

SIGMOD

SIGMOD/PODS01: ACM SIGMOD International Conference on Management of Data

California, Santa Barbara, USA

Acceptance Rates

PODS '01 Paper Acceptance Rate 26 of 99 submissions, 26%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

73
Total Citations
View Citations
374
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 23 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Swami SAryal SBhowmick SDyreson C(2023)Using a Conceptual Model in Plug-and-Play SQLConceptual Modeling10.1007/978-3-031-47262-6_8(145-161)Online publication date: 6-Nov-2023
https://dl.acm.org/doi/10.1007/978-3-031-47262-6_8
Reznichenko V(2022)60 Years of Databases (part four)PROBLEMS IN PROGRAMMING10.15407/pp2022.02.057(57-95)Online publication date: Jun-2022
https://doi.org/10.15407/pp2022.02.057
Pivert OSmits GThion V(2021)Expression and efficient processing of fuzzy queries in a graph database context2015 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE)10.1109/FUZZ-IEEE.2015.7337849(1-8)Online publication date: 9-Mar-2021
https://dl.acm.org/doi/10.1109/FUZZ-IEEE.2015.7337849
Fletcher GPoulovassilis ASelmer PWood P(2019)Approximate Querying for the Property Graph Language Cypher2019 IEEE International Conference on Big Data (Big Data)10.1109/BigData47090.2019.9005466(617-622)Online publication date: Dec-2019
https://doi.org/10.1109/BigData47090.2019.9005466
Jamkhedkar PJohnson TKanza YShaikh AShankaranarayanan NShkapenyuk VDas GJermaine CBernstein P(2018)A Graph Database for a Virtualized Network InfrastructureProceedings of the 2018 International Conference on Management of Data10.1145/3183713.3190653(1393-1405)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3183713.3190653
Poulovassilis A(2018)Applications of Flexible Querying to Graph DataGraph Data Management10.1007/978-3-319-96193-4_4(97-142)Online publication date: 1-Nov-2018
https://doi.org/10.1007/978-3-319-96193-4_4
Castelltort ALaurent APivert OSlama OThion V(2018)Fuzzy Preference Queries to NoSQL Graph DatabasesNoSQL Data Models10.1002/9781119528227.ch6(167-201)Online publication date: 6-Aug-2018
https://doi.org/10.1002/9781119528227.ch6
Jamkhedkar PJohnson TKanza YShaikh AShankarnarayanan NShkapenyuk VWoodhull GChirkova RYang JSuciu D(2017)Virtualized Network Service Topology Exploration Using NepalProceedings of the 2017 ACM International Conference on Management of Data10.1145/3035918.3058733(1611-1614)Online publication date: 9-May-2017
https://dl.acm.org/doi/10.1145/3035918.3058733
Liu JZhang XZhang L(2017)Tree pattern matching in heterogeneous fuzzy XML databasesKnowledge-Based Systems10.1016/j.knosys.2017.02.003122:C(119-130)Online publication date: 15-Apr-2017
https://dl.acm.org/doi/10.1016/j.knosys.2017.02.003
Johnson TKanza YLakshmanan LShkapenyuk VArora ARoy SMehta S(2016)NepalProceedings of the 1st ACM SIGMOD Workshop on Network Data Analytics10.1145/2980523.2980530(1-8)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1145/2980523.2980530
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten