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

research-article

Free access

Consistent query answering under primary keys: a characterization of tractable queries

Author:

Jef WijsenAuthors Info & Claims

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

Pages 42 - 52

https://doi.org/10.1145/1514894.1514900

Published: 23 March 2009 Publication History

Abstract

This article deals with consistent query answering to conjunctive queries under primary key constraints. The repairs of an inconsistent database db are obtained by selecting a maximum number of tuples from db without ever selecting two tuples that agree on their primary key. For a Boolean conjunctive query q, we are interested in the following question: does there exist a Boolean first-order query φ such that for every database db, φ evaluates to true on db if and only if q evaluates to true on every repair of db? We address this problem for acyclic conjunctive queries in which no relation name occurs more than once. Our results improve previous solutions that are based on Fuxman-Miller join graphs.

References

[1]

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

Digital Library

[2]

M. Arenas, L. E. Bertossi, and J. Chomicki. Consistent query answers in inconsistent databases. In PODS, pages 68--79. ACM Press, 1999.

Digital Library

[3]

C. Beeri, R. Fagin, D. Maier, and M. Yannakakis. On the desirability of acyclic database schemes. J. ACM, 30(3):479--513, 1983.

Digital Library

[4]

A. Calì, D. Lembo, and R. Rosati. On the decidability and complexity of query answering over inconsistent and incomplete databases. In PODS, pages 260--271. ACM, 2003.

Digital Library

[5]

A. Calì, D. Lembo, and R. Rosati. Query rewriting and answering under constraints in data integration systems. In G. Gottlob and T. Walsh, editors, IJCAI, pages 16--21. Morgan Kaufmann, 2003.

[6]

J. Chomicki. Consistent query answering: Five easy pieces. In T. Schwentick and D. Suciu, editors, ICDT, volume 4353 of Lecture Notes in Computer Science, pages 1--17. Springer, 2007.

Digital Library

[7]

J. Chomicki and J. Marcinkowski. Minimal-change integrity maintenance using tuple deletions. Inf. Comput., 197(1--2):90--121, 2005.

Digital Library

[8]

W. Fan. Dependencies revisited for improving data quality. In M. Lenzerini and D. Lembo, editors, PODS, pages 159--170. ACM, 2008.

Digital Library

[9]

A. Fuxman, E. Fazli, and R. J. Miller. Conquer: Efficient management of inconsistent databases. In F. Özcan, editor, SIGMOD Conference, pages 155--166. ACM, 2005.

Digital Library

[10]

A. Fuxman and R. J. Miller. First-order query rewriting for inconsistent databases. In T. Eiter and L. Libkin, editors, ICDT, volume 3363 of Lecture Notes in Computer Science, pages 337--351. Springer, 2005.

Digital Library

[11]

A. Fuxman and R. J. Miller. First-order query rewriting for inconsistent databases. J. Comput. Syst. Sci., 73(4):610--635, 2007.

Digital Library

[12]

G. Gottlob, N. Leone, and F. Scarcello. Hypertree decompositions and tractable queries. J. Comput. Syst. Sci., 64(3):579--627, 2002.

Digital Library

[13]

L. Grieco, D. Lembo, R. Rosati, and M. Ruzzi. Consistent query answering under key and exclusion dependencies: algorithms and experiments. In O. Herzog, H.-J. Schek, N. Fuhr, A. Chowdhury, and W. Teiken, editors, CIKM, pages 792--799. ACM, 2005.

Digital Library

[14]

D. Lembo, R. Rosati, and M. Ruzzi. On the first-order reducibility of unions of conjunctive queries over inconsistent databases. In T. Grust, H. Höpfner, A. Illarramendi, S. Jablonski, M. Mesiti, S. Müller, P.-L. Patranjan, K.-U. Sattler, M. Spiliopoulou, and J. Wijsen, editors, EDBT Workshops, volume 4254 of Lecture Notes in Computer Science, pages 358--374. Springer, 2006.

Digital Library

[15]

L. Libkin. Elements of Finite Model Theory. Springer, 2004.

Digital Library

[16]

J. Lin and A. O. Mendelzon. Merging databases under constraints. Int. J. Cooperative Inf. Syst., 7(1):55--76, 1998.

[17]

J. Wijsen. Database repairing using updates. ACM Trans. Database Syst., 30(3):722--768, 2005.

Digital Library

[18]

J. Wijsen. On the consistent rewriting of conjunctive queries under primary key constraints. In M. Arenas and M. I. Schwartzbach, editors, DBPL, volume 4797 of Lecture Notes in Computer Science, pages 112--126. Springer, 2007. An extended version will appear in Information Systems.

Digital Library

Cited By

Dixit AKolaitis P(2022)Consistent Answers of Aggregation Queries via SAT2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00074(924-937)Online publication date: May-2022
https://doi.org/10.1109/ICDE53745.2022.00074
Dixit ABoncz PManegold SAilamaki ADeshpande AKraska T(2019)CAvSATProceedings of the 2019 International Conference on Management of Data10.1145/3299869.3300095(1823-1825)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1145/3299869.3300095
Dixit AKolaitis P(2019)A SAT-Based System for Consistent Query AnsweringTheory and Applications of Satisfiability Testing – SAT 201910.1007/978-3-030-24258-9_8(117-135)Online publication date: 29-Jun-2019
https://doi.org/10.1007/978-3-030-24258-9_8
Show More Cited By

Index Terms

Consistent query answering under primary keys: a characterization of tractable queries
1. Information systems
  1. Data management systems
    1. Database design and models
      1. Relational database model
    2. Query languages
      1. Relational database query languages

Recommendations

Consistent Query Answering for Primary Keys on Path Queries
PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

We study the data complexity of consistent query answering (CQA) on databases that may violate the primary key constraints. A repair is a maximal consistent subset of the database. For a Boolean query q, the problem CERTAINTY(q) takes a database as ...
First-order under-approximations of consistent query answers

Consistent Query Answering (CQA) is a principled approach for answering queries on inconsistent databases. The consistent answer to a query q on an inconsistent database db is the intersection of the answers to q on all repairs, where a repair is any ...
Consistent Query Answering for Primary Keys in Datalog
Abstract
We study the complexity of consistent query answering on databases that may violate primary key constraints. A repair of such a database is any consistent database that can be obtained by deleting a minimal set of tuples. For every Boolean query q,...

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

Author Tags

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

23
Total Citations
View Citations
294
Total Downloads

Downloads (Last 12 months)65
Downloads (Last 6 weeks)11

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dixit AKolaitis P(2022)Consistent Answers of Aggregation Queries via SAT2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00074(924-937)Online publication date: May-2022
https://doi.org/10.1109/ICDE53745.2022.00074
Dixit ABoncz PManegold SAilamaki ADeshpande AKraska T(2019)CAvSATProceedings of the 2019 International Conference on Management of Data10.1145/3299869.3300095(1823-1825)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1145/3299869.3300095
Dixit AKolaitis P(2019)A SAT-Based System for Consistent Query AnsweringTheory and Applications of Satisfiability Testing – SAT 201910.1007/978-3-030-24258-9_8(117-135)Online publication date: 29-Jun-2019
https://doi.org/10.1007/978-3-030-24258-9_8
Ghawi R(2019)On Repairing Referential Integrity Constraints in Relational DatabasesBeyond Databases, Architectures and Structures. Paving the Road to Smart Data Processing and Analysis10.1007/978-3-030-19093-4_7(82-96)Online publication date: 27-Apr-2019
https://doi.org/10.1007/978-3-030-19093-4_7
Zadorozhny VGrant J(2016)A systematic approach to reliability assessment in integrated databasesJournal of Intelligent Information Systems10.1007/s10844-015-0359-246:3(409-424)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1007/s10844-015-0359-2
Homola MPatkos TFlouris GŠefránek JŠimko AFrtús JZografistou DBaláž M(2015)Resolving conflicts in knowledge for ambient intelligenceThe Knowledge Engineering Review10.1017/S026988891500013230:5(455-513)Online publication date: 30-Oct-2015
https://doi.org/10.1017/S0269888915000132
Chortis MFlouris G(2015)A Diagnosis and Repair Framework for DL-LiteA KBsThe Semantic Web: ESWC 2015 Satellite Events10.1007/978-3-319-25639-9_37(199-214)Online publication date: 31-May-2015
https://dl.acm.org/doi/10.1007/978-3-319-25639-9_37
Martinez MParisi FPugliese ASimari GSubrahmanian V(2014)Policy-based inconsistency management in relational databasesInternational Journal of Approximate Reasoning10.1016/j.ijar.2013.12.00455:2(501-528)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1016/j.ijar.2013.12.004
Wijsen J(2012)Certain conjunctive query answering in first-order logicACM Transactions on Database Systems10.1145/2188349.218835137:2(1-35)Online publication date: 4-Jun-2012
https://dl.acm.org/doi/10.1145/2188349.2188351
Greco SMolinaro C(2012)Probabilistic query answering over inconsistent databasesAnnals of Mathematics and Artificial Intelligence10.1007/s10472-012-9287-964:2-3(185-207)Online publication date: 1-Mar-2012
https://dl.acm.org/doi/10.1007/s10472-012-9287-9
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