More Web Proxy on the site http://driver.im/

research-article

Free access

Reconcilable differences

Authors:

Zachary G. Ives,

Val TannenAuthors Info & Claims

ICDT '09: Proceedings of the 12th International Conference on Database Theory

Pages 212 - 224

https://doi.org/10.1145/1514894.1514920

Published: 23 March 2009 Publication History

Abstract

Exact query reformulation using views in positive relational languages is well understood, and has a variety of applications in query optimization and data sharing. Generalizations to larger fragments of the relational algebra (RA) --- specifically, support for the difference operator --- would increase the options available for query reformulation, and also apply to view adaptation (updating a materialized view in response to a modified view definition) and view maintenance. Unfortunately, most questions about queries become undecidable in the presence of difference/negation. We present a novel way of managing this difficulty via an excursion through a non-standard semantics, Z-relations, where tuples are annotated with positive or negative integers.

We show that under Z-semantics RA queries have a normal form as a single difference of positive queries and this leads to the decidability of equivalence. In most real-world settings with difference, it is possible to convert the queries to this normal form. We give a sound and complete algorithm that explores all reformulations of an RA query (under Z-semantics) using a set of RA views, finitely bounding the search space with a simple and natural cost model. We investigate related complexity questions, and we also extend our results to queries with built-in predicates.

Z-relations are interesting in their own right because they capture updates and data uniformly. However, our algorithm turns out to be sound and complete also for bag semantics, albeit necessarily only for a subclass of RA. This subclass turns out to be quite large and covers generously the applications of interest to us. We also show a subclass of RA where reformulation and evaluation under Z-semantics can be combined with duplicate elimination to obtain the answer under set semantics.

References

[1]

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

Digital Library

[2]

F. Afrati and V. Pavlaki. Rewriting queries using views with negation. AI Communications, 19:229--237, 2006.

Digital Library

[3]

A. K. Chandra and P. M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In STOC, 1977.

Digital Library

[4]

S. Chaudhuri, R. Krishnamurthy, S. Potamianos, and K. Shim. Optimizing queries with materialized views. In ICDE, 1995.

Digital Library

[5]

S. Chaudhuri and M. Y. Vardi. Optimization of real conjunctive queries. In PODS, pages 59--70, 1993.

Digital Library

[6]

S. Cohen. Containment of aggregate queries. SIGMOD Record, 34(1):77--85, 2005.

Digital Library

[7]

S. Cohen, W. Nutt, and Y. Sagiv. Rewriting queries with arbitrary aggregation functions using views. ACM Trans. Database Syst., 31(2):672--715, 2006.

Digital Library

[8]

S. Cohen, W. Nutt, and Y. Sagiv. Deciding equivalences among conjunctive aggregate queries. J. ACM, 54(2), 2007.

Digital Library

[9]

S. Cohen, W. Nutt, and A. Serebrenik. Rewriting aggregate queries using views. In PODS, 1999.

Digital Library

[10]

S. Cohen, Y. Sagiv, and W. Nutt. Equivalences among aggregate queries with negation. ACM TOCL, 6(2):328--360, April 2005.

Digital Library

[11]

T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. McGraw-Hill / MIT Press, 1990.

Digital Library

[12]

G. Graefe and W. J. McKenna. The Volcano optimizer generator: Extensibility and efficient search. In ICDE, 1993.

Digital Library

[13]

T. J. Green. Containment of conjunctive queries on annotated relations. In ICDT, 2009.

Digital Library

[14]

T. J. Green, G. Karvounarakis, Z. G. Ives, and V. Tannen. Update exchange with mappings and provenance. In VLDB, 2007. Amended version available as Univ. of Pennsylvania report MS-CIS-07-26.

Digital Library

[15]

T. J. Green, G. Karvounarakis, and V. Tannen. Provenance semirings. In PODS, 2007.

Digital Library

[16]

A. Gupta, I. S. Mumick, J. Rao, and K. A. Ross. Adapting materialized views after redefinitions: Techniques and a performance study. Information Systems, 26(5):323--362, 2001.

Digital Library

[17]

A. Gupta, I. S. Mumick, and V. S. Subrahmanian. Maintaining views incrementally. In SIGMOD, 1993.

Digital Library

[18]

L. M. Haas, J. C. Freytag, G. M. Lohman, and H. Pirahesh. Extensible query processing in Starburst. In SIGMOD, 1989.

Digital Library

[19]

A. Y. Halevy. Answering queries using views: A survey. VLDB J., 10(4), 2001.

Digital Library

[20]

P. Hell and J. Nešetřil. Graphs and Homomorphisms. Oxford University Press, 2004.

[21]

Y. E. Ioannidis and R. Ramakrishnan. Containment of conjunctive queries: Beyond relations as sets. TODS, 20(3):288--324, 1995.

Digital Library

[22]

T. S. Jayram, P. G. Kolaitis, and E. Vee. The containment problem for real conjunctive queries with inequalities. In PODS, 2006.

Digital Library

[23]

J. W. Klop. Handbook of Logic in Computer Science, volume 2, chapter 1. Oxford University Press, 1992.

[24]

A. Y. Levy, A. O. Mendelzon, Y. Sagiv, and D. Srivastava. Answering queries using views. In PODS, 1995.

Digital Library

[25]

L. Lovász. Operations with structures. Acta Mathematica Hungarica, 18(3--4):321--328, 1967.

[26]

Y. Sagiv and M. Yannakakis. Equivalences among relational expressions with the union and difference operators. J. ACM, 27(4):633--655, 1980.

Digital Library

[27]

P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price. Access path selection in a relational database management system. In SIGMOD, 1979.

Digital Library

Cited By

Grädel ETannen V(2020)Provenance analysis for logic and gamesMoscow Journal of Combinatorics and Number Theory10.2140/moscow.2020.9.2039:3(203-228)Online publication date: 15-Oct-2020
https://doi.org/10.2140/moscow.2020.9.203
Dannert KGrädel E(2019)Provenance Analysis: A Perspective for Description Logics?Description Logic, Theory Combination, and All That10.1007/978-3-030-22102-7_12(266-285)Online publication date: 1-Jun-2019
https://doi.org/10.1007/978-3-030-22102-7_12
Glavic BMiller RAlonso G(2013)Using SQL for Efficient Generation and Querying of Provenance InformationIn Search of Elegance in the Theory and Practice of Computation10.1007/978-3-642-41660-6_16(291-320)Online publication date: 2013
https://doi.org/10.1007/978-3-642-41660-6_16
Show More Cited By

Reconcilable differences
1. Information systems
  1. Data management systems
    1. Database management system engines
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory

Recommendations

Reconcilable Differences

In this paper we study a problem motivated by the management of changes in databases. It turns out that several such change scenarios, e.g., the separately studied problems of view maintenance (propagation of data changes) and view adaptation (...
Effects of expertise differences in synchronous social Q&A
SIGIR '12: Proceedings of the 35th international ACM SIGIR conference on Research and development in information retrieval

Synchronous social question-and-answer (Q&A) systems match askers to answerers and support real-time dialog between them to resolve questions. These systems typically find answerers based on the degree of expertise match with the asker's initial ...
Equivalence and minimization of conjunctive queries under combined semantics
ICDT '12: Proceedings of the 15th International Conference on Database Theory

The problems of query containment, equivalence, and minimization are fundamental problems in the context of query processing and optimization. In their classic work [2] published in 1977, Chandra and Merlin solved the three problems for the language of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICDT '09: Proceedings of the 12th International Conference on Database Theory

March 2009

334 pages

ISBN:9781605584232

DOI:10.1145/1514894

Editor:
Ronald Fagin
IBM Research

Copyright © 2009 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 March 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

EDBT/ICDT '09

EDBT/ICDT '09: EDBT/ICDT '09 joint conference

March 23 - 25, 2009

St. Petersburg, Russia

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
303
Total Downloads

Downloads (Last 12 months)82
Downloads (Last 6 weeks)19

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Grädel ETannen V(2020)Provenance analysis for logic and gamesMoscow Journal of Combinatorics and Number Theory10.2140/moscow.2020.9.2039:3(203-228)Online publication date: 15-Oct-2020
https://doi.org/10.2140/moscow.2020.9.203
Dannert KGrädel E(2019)Provenance Analysis: A Perspective for Description Logics?Description Logic, Theory Combination, and All That10.1007/978-3-030-22102-7_12(266-285)Online publication date: 1-Jun-2019
https://doi.org/10.1007/978-3-030-22102-7_12
Glavic BMiller RAlonso G(2013)Using SQL for Efficient Generation and Querying of Provenance InformationIn Search of Elegance in the Theory and Practice of Computation10.1007/978-3-642-41660-6_16(291-320)Online publication date: 2013
https://doi.org/10.1007/978-3-642-41660-6_16
Sovran YPower RAguilera MLi JWobber TDruschel P(2011)Transactional storage for geo-replicated systemsProceedings of the Twenty-Third ACM Symposium on Operating Systems Principles10.1145/2043556.2043592(385-400)Online publication date: 23-Oct-2011
https://dl.acm.org/doi/10.1145/2043556.2043592
Amsterdamer YDeutch DTannen VLenzerini MSchwentick T(2011)Provenance for aggregate queriesProceedings of the thirtieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems10.1145/1989284.1989302(153-164)Online publication date: 13-Jun-2011
https://dl.acm.org/doi/10.1145/1989284.1989302
Koch CParedaens JVan Gucht D(2010)Incremental query evaluation in a ring of databasesProceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems10.1145/1807085.1807100(87-98)Online publication date: 6-Jun-2010
https://dl.acm.org/doi/10.1145/1807085.1807100
Green T(2009)Containment of conjunctive queries on annotated relationsProceedings of the 12th International Conference on Database Theory10.1145/1514894.1514930(296-309)Online publication date: 23-Mar-2009
https://dl.acm.org/doi/10.1145/1514894.1514930

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