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

Locally consistent transformations and query answering in data exchange

Published: 14 June 2004 Publication History

Abstract

Data exchange is the problem of taking data structured under a source schema and creating an instance of a target schema. Given a source instance, there may be many solutions - target instances that satisfy the constraints of the data exchange problem. Previous work has identified two classes of desirable solutions: canonical universal solutions, and their cores. Query answering in data exchange amounts to rewriting a query over the target schema to another query that, over a materialized target instance, gives the result that is semantically consistent with the source. A basic question is then whether there exists a transformation sending a source instance into a solution over which target queries can be answered.We show that the answer is negative for many data exchange transformations that have structural properties similar to canonical universal solutions and cores. Namely, we prove that many such transformations preserve the local structure of the data. Using this notion, we further show that every target query rewritable over such a transformation cannot distinguish tuples whose neighborhoods in the source are similar. This gives us a first tool that helps check whether a query is rewritable, We also show that these results are robust: they hold for an extension of relational calculus with grouping and aggregates, and for two different semantics of query answering.

References

[1]
S. Abiteboul and O. Duschka. Complexity of answering queries using materialized views. In PODS 1998, pages 254--263.
[2]
S. Abiteboul, R. Hull and V. Vianu. Foundations of Databases. Addison Wesley, 1995.
[3]
S. Abiteboul and P Kanellakis, Object identity as a query language primitive, Journal of the ACM 45(5), pages 798--842. 1998.
[4]
C. Beeri and M. Y. Vardi. A proof procedure for data dependencies. Journal of the ACM 31(4), pages 718--741, 1984.
[5]
O. Duschka and A. Levy. Recursive plans for information gathering. In IJCAI 1997. pages 778--784.
[6]
H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer Verlag, 1995.
[7]
R. Fagin. Horn clauses and database dependencies, Journal of the ACM 29(4), pages 952--985, 1982.
[8]
R. Fagin. Probabilities on finite models. Journal of Symbolic Logic 41(1), pages 50--58, 1976.
[9]
R. Fagin. Ph. Kolaitis, R. Miller and L. Popa. Data exchange: semantics and query answering. In ICDT 2003, pages 207--224.
[10]
R. Fagin. Ph. Kolaitis and L. Popa. Data exchange: getting to the core. In PODS 2003, pages 90--101.
[11]
R. Fagin, L. Stockmeyer and M. Vardi. On monadic NP vs monadic co-NP. Information and Computation 120(1), pages 78--92, 1995.
[12]
H. Gaifman. On local and non-local properties. In Proceedings of the Herbrand Symposium, Logic Colloquium '81, North Holland, 1982.
[13]
E. Grädel and Y. Gurevich. Metafinite model theory. Information and Computation 140(1), pages 26--81, 1998.
[14]
A. Halevy. Theory of answering queries using views, SIGMOD Record 29(4), pages 40--47, 2000.
[15]
W. Hanf. Model-theoretic methods in the study of elementary logic. In J. W. Addison et al. eds, The Theory of Models, North Holland. pages 132--145, 1965.
[16]
P. Hell and J. Nešetřil. The core of a graph. Discrete Mathematics 109, pages 117--126, 1992.
[17]
L. Hella. Logical hierarchies in PTIME. Information and Computation 129(1), pages 1--19, 1996.
[18]
L. Hella, L. Libkin, J. Nurmonen and L. Wong. Logics with aggregate operators. Journal of the ACM 48(4). pages 880--907, 2001
[19]
R. Hull and M. Yoshikawa. ILOG: declarative creation and manipulation of object identifiers. In VLDB 1990, pages 455--468.
[20]
T. Imielinski and W. Lipski. Incomplete information in relational databases. Journal of the ACM 31(4), pages 761--791, 1984.
[21]
A. Klug. Equivalence of relational algebra and relational calculus query languages having aggregate functions. Journal of the ACM 29(3), pages 699--717, 1982.
[22]
K. Larsen. On grouping in relational algebra. International Journal of Foundations of Computer Science 10(3), pages 301--311. 1999.
[23]
M. Lenzerini. Data integration: a theoretical perspective. In PODS 2002, pages 233--246.
[24]
A. Levy, A. Mendelzon, Y. Sagiv and D. Srivastava. Answering queries using views. In PODS 1995, pages 95--104.
[25]
L. Libkin. Logics with counting and local properties. ACM Transactions on Computational Logic 1(1), pages 33--59, 2000.
[26]
D. Maier, A. O. Mendelzon and Y. Sagiv. Testing implications of data dependencies. ACM Transactions on Database Systems 4(4), pages 455--469, 1979.
[27]
N. Shu, B. Housel, R. Taylor, S. Ghosh and V. Lum. EXPRESS: a data extraction, processing, and restructuring system. ACM Transactions on Database Systems 2(2), pages 134--174, 1977.
[28]
J. Van den Bussche, D. Van Gucht, M. Andries and M. Gyssens. On the completeness of object-creating database transformation languages. Journal of the ACM 44(2), pages 272--319, 1997.

Cited By

View all
  • (2022)Incomplete Data and Data Dependencies in Relational DatabasesundefinedOnline publication date: 2-Mar-2022
  • (2022)Relational and XML Data ExchangeundefinedOnline publication date: 23-Feb-2022
  • (2019)Simplified data posting in practiceProceedings of the 23rd International Database Applications & Engineering Symposium10.1145/3331076.3331104(1-7)Online publication date: 10-Jun-2019
  • 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)5
  • Downloads (Last 6 weeks)1
Reflects downloads up to 31 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2022)Incomplete Data and Data Dependencies in Relational DatabasesundefinedOnline publication date: 2-Mar-2022
  • (2022)Relational and XML Data ExchangeundefinedOnline publication date: 23-Feb-2022
  • (2019)Simplified data posting in practiceProceedings of the 23rd International Database Applications & Engineering Symposium10.1145/3331076.3331104(1-7)Online publication date: 10-Jun-2019
  • (2019)HIKE: A Step Beyond Data ExchangeConceptual Modeling10.1007/978-3-030-33223-5_35(423-438)Online publication date: 4-Nov-2019
  • (2019)An Effective System for User Queries AssistanceFlexible Query Answering Systems10.1007/978-3-030-27629-4_33(361-373)Online publication date: 17-Jun-2019
  • (2017)Discovering User Behavioral Features to Enhance Information Search on Big DataACM Transactions on Interactive Intelligent Systems10.1145/28560597:2(1-33)Online publication date: 29-Jul-2017
  • (2016)Exploiting equality generating dependencies in checking chase terminationProceedings of the VLDB Endowment10.14778/2876473.28764759:5(396-407)Online publication date: 1-Jan-2016
  • (2016)A Framework Enhancing the User Search Activity Through Data PostingRule Technologies. Research, Tools, and Applications10.1007/978-3-319-42019-6_19(287-304)Online publication date: 28-Jun-2016
  • (2015)Bidirectional constraints for exchanging dataProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832581.2832626(2698-2705)Online publication date: 25-Jul-2015
  • (2014)XML Schema MappingsJournal of the ACM10.1145/259077361:2(1-48)Online publication date: 24-Apr-2014
  • 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