research-article

Scalable query rewriting: a graph-based approach

Authors:

George Konstantinidis,

José Luis AmbiteAuthors Info & Claims

SIGMOD '11: Proceedings of the 2011 ACM SIGMOD International Conference on Management of data

Pages 97 - 108

https://doi.org/10.1145/1989323.1989335

Published: 12 June 2011 Publication History

Abstract

In this paper we consider the problem of answering queries using views, which is important for data integration, query optimization, and data warehouses. We consider its simplest form, conjunctive queries and views, which already is NP-complete. Our context is data integration, so we search for maximally-contained rewritings. By looking at the problem from a graph perspective we are able to gain a better insight and develop an algorithm which compactly represents common patterns in the source descriptions, and (optionally) pushes some computation offline. This together with other optimizations result in an experimental performance about two orders of magnitude faster than current state-of-the-art algorithms, rewriting queries using over 10000 views within seconds.

References

[1]

S. Abiteboul, R. Hull, and V. Vianu. Foundations of databases. Citeseer, 1995.

Digital Library

[2]

F. Afrati and N. Kiourtis. Query answering using views in the presence of dependencies. New Trends in Information Integration (NTII), pages 8--11, 2008.

[3]

P. Agrawal, A. D. Sarma, J. Ullman, and J. Widom. Foundations of Uncertain-Data Integration. Proceedings of the VLDB Endowment, 3(1):1--24, 2010.

Digital Library

[4]

M. Arenas, J. Pérez, J. Reutter, and C. Riveros. Composition and inversion of schema mappings. ACM SIGMOD Record, 38(3):17, Dec. 2010.

Digital Library

[5]

M. Arenas, J. Pérez, J. L. Reutter, and C. Riveros. Foundations of schema mapping management. In PODS '10: Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems of data, pages 227--238, New York, NY, USA, 2010. ACM.

Digital Library

[6]

P. C. Arocena, A. Fuxman, and R. J. Miller. Composing local-as-view mappings: closure and applications. In Proceedings of the 13th International Conference on Database Theory, pages 209--218. ACM, 2010.

Digital Library

[7]

Y. Arvelo, B. Bonet, and M. E. Vidal. Compilation of query-rewriting problems into tractable fragments of propositional logic. In AAAI'06: Proceedings of the 21st national conference on Artificial intelligence, pages 225--230. AAAI Press, 2006.

Digital Library

[8]

A. Chandra and P. Merlin. Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the ninth annual ACM symposium on Theory of computing, pages 77--90. ACM, 1977.

Digital Library

[9]

M. Chein and M.-L. Mugnier. Graph-based Knowledge Representation: Computational Foundations of Conceptual Graphs. Springer Publishing Company, Incorporated, 2008.

Digital Library

[10]

O. M. Duschka and M. R. Genesereth. Answering recursive queries using views. In PODS '97: Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, pages 109--116, New York, NY, USA, 1997. ACM.

Digital Library

[11]

H. Garcia-Molina, J. Hammer, K. Ireland, Y. Papakonstantinou,J. Ullman, and J. Widom. Integrating and accessing heterogeneous information sources in tsimmis. In Proceedings of the AAAI Symposium on Information Gathering, pp. 61--64, March 1995.

[12]

G. Gottlob, N. Leone, and F. Scarcello. Hypertree decompositions and tractable queries. In Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 21--32. ACM, 1999.

Digital Library

[13]

A. Halevy. Answering queries using views: A survey. The VLDB Journal, 10(4):270--294, Dec. 2001.

Digital Library

[14]

H. Kondylakis and D. Plexousakis. Enabling ontology evolution in data integration. In Proceedings of the 2010 EDBT Workshops, pages 1--7. ACM, 2010.

Digital Library

[15]

M. Lenzerini. Data integration: A theoretical perspective. In PODS, pages 233--246, 2002.

Digital Library

[16]

A. Levy, A. Mendelzon, Y. Sagiv, and D. Srivastava. Answering queries using views (extended abstract). In Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, pages 95--104. ACM, 1995.

Digital Library

[17]

A. Levy, A. Rajaraman, and J. Ordille. Querying heterogeneous information sources using source descriptions. pages 251--262, 1996.

Digital Library

[18]

V. L'ın, V. Vassalos, and P. Malakasiotis. MiniCount: Efficient Rewriting of COUNT-Queries Using Views. 22nd International Conference on Data Engineering (ICDE'06), pages 1--1, 2006.

Digital Library

[19]

R. Pottinger and A. Halevy. MiniCon: A scalable algorithm for answering queries using views. The VLDB Journal, 10(2):182--198, 2001.

Digital Library

[20]

L. Zhou, H. Chen, Y. Zhang, and C. Zhou. A Semantic Mapping System for Bridging the Gap between Relational Database and Semantic Web. American Association for Artificial InteIligence (www. aaai. org), 2008.

Cited By

Alhazmi ABlount TKonstantinidis G(2022)ForBackBenchProceedings of the VLDB Endowment10.14778/3529337.352933815:8(1519-1532)Online publication date: 22-Jun-2022
https://dl.acm.org/doi/10.14778/3529337.3529338
Konstantinidis GHolt JChapman A(2022)Enabling personal consent in databasesProceedings of the VLDB Endowment10.14778/3489496.348951615:2(375-387)Online publication date: 4-Feb-2022
https://dl.acm.org/doi/10.14778/3489496.3489516
Pareti PKonstantinidis GMogavero F(2022)Satisfiability and containment of recursive SHACLJournal of Web Semantics10.1016/j.websem.2022.10072174(100721)Online publication date: Oct-2022
https://doi.org/10.1016/j.websem.2022.100721
Show More Cited By

Index Terms

Scalable query rewriting: a graph-based approach

Recommendations

Rewriting general conjunctive queries using views

The problem of rewriting queries using views has important applications in data integration, query optimization, and physical data independence maintenance. Previous researchers have proposed rewriting algorithms for queries and views that are Datalog ...
Rewriting general conjunctive queries using views
ADC '02: Proceedings of the 13th Australasian database conference - Volume 5

The problem of rewriting queries using views has important applications in data integration, query optimization, and physical data independence maintenance. Previous researchers have proposed rewriting algorithms for queries and views that are Datalog ...
Query containment for data integration systems
Special issue on PODS 2000

The problem of query containment is fundamental to many aspects of database systems, including query optimization, determining independence of queries from updates, and rewriting queries using views. In the data-integration framework, however, the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '11: Proceedings of the 2011 ACM SIGMOD International Conference on Management of data

June 2011

1364 pages

ISBN:9781450306614

DOI:10.1145/1989323

General Chair:
Timos Sellis
IMIS/RC Athena
,
Program Chair:
Renée J. Miller
University of Toronto
,
Publications Chairs:
Anastasios Kementsietsidis
IBM T.J. Watson Research Center
,
Yannis Velegrakis
University of Trento

Copyright © 2011 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: 12 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMOD/PODS '11

Sponsor:

SIGMOD

SIGMOD/PODS '11: International Conference on Management of Data

June 12 - 16, 2011

Athens, Greece

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
660
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)6

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Alhazmi ABlount TKonstantinidis G(2022)ForBackBenchProceedings of the VLDB Endowment10.14778/3529337.352933815:8(1519-1532)Online publication date: 22-Jun-2022
https://dl.acm.org/doi/10.14778/3529337.3529338
Konstantinidis GHolt JChapman A(2022)Enabling personal consent in databasesProceedings of the VLDB Endowment10.14778/3489496.348951615:2(375-387)Online publication date: 4-Feb-2022
https://dl.acm.org/doi/10.14778/3489496.3489516
Pareti PKonstantinidis GMogavero F(2022)Satisfiability and containment of recursive SHACLJournal of Web Semantics10.1016/j.websem.2022.10072174(100721)Online publication date: Oct-2022
https://doi.org/10.1016/j.websem.2022.100721
Nadal SAbello ARomero OVansummeren SVassiliadis P(2021)Graph-driven Federated Data ManagementIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2021.3077044(1-1)Online publication date: 2021
https://doi.org/10.1109/TKDE.2021.3077044
Konstantinidis GChapman AWeal MAlzubaidi ABallard LLucassen A(2020)The Need for Machine-Processable Agreements in Health Data ManagementAlgorithms10.3390/a1304008713:4(87)Online publication date: 7-Apr-2020
https://doi.org/10.3390/a13040087
Kondylakis HStefanidis KRao PParry D(2020)Report on the Second International Workshop on Semantic Web Meets Health Data Management (SWH 2019)ACM SIGMOD Record10.1145/3442322.344233349:2(59-62)Online publication date: 10-Dec-2020
https://dl.acm.org/doi/10.1145/3442322.3442333
Konstantinidis GMogavero FSuciu DSkritek SKoch C(2019)Attacking DiophantusProceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3294052.3319689(399-413)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1145/3294052.3319689
Chapman ASimperl EKoesten LKonstantinidis GIbáñez LKacprzak EGroth P(2019)Dataset search: a surveyThe VLDB Journal10.1007/s00778-019-00564-xOnline publication date: 24-Aug-2019
https://doi.org/10.1007/s00778-019-00564-x
Stripelis DAnastasiou CAmbite J(2018)Extending Apache Spark with a Mediation LayerProceedings of the International Workshop on Semantic Big Data10.1145/3208352.3208354(1-6)Online publication date: 10-Jun-2018
https://dl.acm.org/doi/10.1145/3208352.3208354
Stripelis DAmbite JChiang YEckel SHabre R(2017)A Scalable Data Integration and Analysis Architecture for Sensor Data of Pediatric Asthma2017 IEEE 33rd International Conference on Data Engineering (ICDE)10.1109/ICDE.2017.198(1407-1408)Online publication date: Apr-2017
https://doi.org/10.1109/ICDE.2017.198
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.

Media

Figures

Other

Tables

View Table of Contents