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

research-article

Public Access

Consistent Query Answering for Primary Keys on Path Queries

Authors:

Paraschos Koutris,

Xiating Ouyang,

Jef WijsenAuthors Info & Claims

PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

Pages 215 - 232

https://doi.org/10.1145/3452021.3458334

Published: 20 June 2021 Publication History

Abstract

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 input, and asks whether or not each repair satisfies the query q. It is known that for any self-join-free Boolean conjunctive query q, CERTAINTY(q) is in FO, L-complete, or coNP-complete. In particular, CERTAINTY(q) is in FO for any self-join-free Boolean path query q. In this paper, we show that if self-joins are allowed, then the complexity of CERTAINTY(q) for Boolean path queries q exhibits a tetrachotomy between FO, NL-complete, PTIME-complete, and coNP-complete. Moreover, it is decidable, in polynomial time in the size of the query q, which of the four cases applies.

References

[1]

Foto N. Afrati, Phokion G. Kolaitis, and Angelos Vasilakopoulos. 2015. Consistent Answers of Conjunctive Queries on Graphs. CoRR, Vol. abs/1503.00650 (2015).

[2]

Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki. 1999. Consistent Query Answers in Inconsistent Databases. In PODS. ACM Press, 68--79.

[3]

Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. 2017. Answering Conjunctive Queries under Updates. In PODS. ACM, 303--318.

[4]

Leopoldo E. Bertossi. 2019. Database Repairs and Consistent Query Answering: Origins and Further Developments. In PODS. ACM, 48--58.

[5]

Andrei A. Bulatov. 2011. Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Log., Vol. 12, 4 (2011), 24:1--24:66.

Digital Library

[6]

Jan Chomicki and Jerzy Marcinkowski. 2005. Minimal-change integrity maintenance using tuple deletions. Inf. Comput., Vol. 197, 1--2 (2005), 90--121. https://doi.org/10.1016/j.ic.2004.04.007

Digital Library

[7]

Jan Chomicki, Jerzy Marcinkowski, and Slawomir Staworko. 2004. Hippo: A System for Computing Consistent Answers to a Class of SQL Queries. In EDBT (Lecture Notes in Computer Science), Vol. 2992. Springer, 841--844.

[8]

Akhil A. Dixit and Phokion G. Kolaitis. 2019. A SAT-Based System for Consistent Query Answering. In SAT (Lecture Notes in Computer Science), Vol. 11628. Springer, 117--135.

[9]

Gaë lle Fontaine. 2015. Why Is It Hard to Obtain a Dichotomy for Consistent Query Answering? ACM Trans. Comput. Log., Vol. 16, 1 (2015), 7:1--7:24.

Digital Library

[10]

Cibele Freire, Wolfgang Gatterbauer, Neil Immerman, and Alexandra Meliou. 2015. The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries. Proc. VLDB Endow., Vol. 9, 3 (2015), 180--191.

Digital Library

[11]

Cibele Freire, Wolfgang Gatterbauer, Neil Immerman, and Alexandra Meliou. 2020. New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins. In PODS. ACM, 271--284.

[12]

Ariel Fuxman and René e J. Miller. 2007. First-order query rewriting for inconsistent databases. J. Comput. Syst. Sci., Vol. 73, 4 (2007), 610--635.

Digital Library

[13]

Leslie M. Goldschlager. 1977. The Monotone and Planar Circuit Value Problems Are Log Space Complete for P . SIGACT News, Vol. 9, 2 (July 1977), 25--29. https://doi.org/10.1145/1008354.1008356

Digital Library

[14]

Gianluigi Greco, Sergio Greco, and Ester Zumpano. 2003. A Logical Framework for Querying and Repairing Inconsistent Databases. IEEE Trans. Knowl. Data Eng., Vol. 15, 6 (2003), 1389--1408.

Digital Library

[15]

Lara A Kahale, Assem M Khamis, Batoul Diab, Yaping Chang, Luciane Cruz Lopes, Arnav Agarwal, Ling Li, Reem A Mustafa, Serge Koujanian, Reem Waziry, et almbox. 2020. Meta-Analyses Proved Inconsistent in How Missing Data Were Handled Across Their Included Primary Trials: A Methodological Survey. Clinical Epidemiology, Vol. 12 (2020), 527--535.

[16]

Yannis Katsis, Alin Deutsch, Yannis Papakonstantinou, and Vasilis Vassalos. 2010. Inconsistency resolution in online databases. In ICDE. IEEE Computer Society, 1205--1208.

[17]

Aziz Amezian El Khalfioui, Jonathan Joertz, Dorian Labeeuw, Gaë tan Staquet, and Jef Wijsen. 2020. Optimization of Answer Set Programs for Consistent Query Answering by Means of First-Order Rewriting. In CIKM. ACM, 25--34.

[18]

Phokion G. Kolaitis and Enela Pema. 2012. A dichotomy in the complexity of consistent query answering for queries with two atoms. Inf. Process. Lett., Vol. 112, 3 (2012), 77--85.

Digital Library

[19]

Phokion G. Kolaitis, Enela Pema, and Wang-Chiew Tan. 2013. Efficient Querying of Inconsistent Databases with Binary Integer Programming. Proc. VLDB Endow., Vol. 6, 6 (2013), 397--408.

Digital Library

[20]

Paraschos Koutris and Dan Suciu. 2014. A Dichotomy on the Complexity of Consistent Query Answering for Atoms with Simple Keys. In ICDT. OpenProceedings.org, 165--176.

[21]

Paraschos Koutris and Jef Wijsen. 2015. The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints. In PODS. ACM, 17--29.

[22]

Paraschos Koutris and Jef Wijsen. 2017. Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints. ACM Trans. Database Syst., Vol. 42, 2 (2017), 9:1--9:45.

Digital Library

[23]

Paraschos Koutris and Jef Wijsen. 2018. Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms. In PODS. ACM, 209--224.

[24]

Paraschos Koutris and Jef Wijsen. 2019. Consistent Query Answering for Primary Keys in Logspace. In ICDT (LIPIcs), Vol. 127. Schloss Dagstuhl - Leibniz-Zentrum fü r Informatik, 23:1--23:19.

[25]

Paraschos Koutris and Jef Wijsen. 2020. First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys. In PODS. ACM, 113--129.

[26]

Paraschos Koutris and Jef Wijsen. 2021. Consistent Query Answering for Primary Keys in Datalog. Theory Comput. Syst., Vol. 65, 1 (2021), 122--178.

Digital Library

[27]

Leonid Libkin. 2004. Elements of Finite Model Theory .Springer.

Digital Library

[28]

Carsten Lutz and Frank Wolter. 2015. On the Relationship between Consistent Query Answering and Constraint Satisfaction Problems. In ICDT (LIPIcs), Vol. 31. Schloss Dagstuhl - Leibniz-Zentrum fü r Informatik, 363--379.

[29]

Marco Manna, Francesco Ricca, and Giorgio Terracina. 2015. Taming primary key violations to query large inconsistent data via ASP . Theory Pract. Log. Program., Vol. 15, 4--5 (2015), 696--710.

[30]

Mó nica Caniupá n Marileo and Leopoldo E. Bertossi. 2010. The consistency extractor system: Answer set programs for consistent query answering in databases. Data Knowl. Eng., Vol. 69, 6 (2010), 545--572.

Digital Library

[31]

Dany Maslowski and Jef Wijsen. 2013. A dichotomy in the complexity of counting database repairs. J. Comput. Syst. Sci., Vol. 79, 6 (2013), 958--983.

Digital Library

[32]

Dany Maslowski and Jef Wijsen. 2014. Counting Database Repairs that Satisfy Conjunctive Queries with Self-Joins. In ICDT. OpenProceedings.org, 155--164.

[33]

Jef Wijsen. 2010. On the first-order expressibility of computing certain answers to conjunctive queries over uncertain databases. In PODS. ACM, 179--190.

[34]

Jef Wijsen. 2012. Certain conjunctive query answering in first-order logic. ACM Trans. Database Syst., Vol. 37, 2 (2012), 9:1--9:35.

Digital Library

[35]

Jef Wijsen. 2019. Foundations of Query Answering on Inconsistent Databases. SIGMOD Rec., Vol. 48, 3 (2019), 6--16.

Digital Library

Cited By

Amezian El Khalfioui AWijsen J(2024)Computing Range Consistent Answers to Aggregation Queries via RewritingProceedings of the ACM on Management of Data10.1145/36958362:5(1-19)Online publication date: 7-Nov-2024
https://doi.org/10.1145/3695836
Koutris POuyang XWijsen J(2024)Consistent Query Answering for Primary Keys on Rooted Tree QueriesProceedings of the ACM on Management of Data10.1145/36511392:2(1-26)Online publication date: 14-May-2024
https://doi.org/10.1145/3651139
Padmanabha ASegoufin LSirangelo C(2024)A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-JoinProceedings of the ACM on Management of Data10.1145/36511372:2(1-15)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651137
Show More Cited By

Index Terms

Consistent Query Answering for Primary Keys on Path Queries
1. Information systems
  1. Data management systems
    1. Query languages
      1. Relational database query languages
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Incomplete, inconsistent, and uncertain databases
      2. Logic and databases

Recommendations

Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints
Invited Paper from SIGMOD 2015, Invited Paper from PODS 2015 and Regular Papers

A relational database is said to be uncertain if primary key constraints can possibly be violated. A repair (or possible world) of an uncertain database is obtained by selecting a maximal number of tuples without ever selecting two distinct tuples with ...
Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms
PODS '18: Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

This paper studies query answering on databases that may be inconsistent with respect to primary key constraints. A repair is any consistent database that is obtained by deleting a minimal set of tuples. Given a Boolean query q, the problem CERTAINTY(q) ...
First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys
PODS'20: Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

We study consistent query answering with respect to key dependencies. Given a (possibly inconsistent) database instance and a set of key dependencies, a repair is an inclusion-maximal subinstance that satisfies all key dependencies. Consistent query ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

June 2021

440 pages

ISBN:9781450383813

DOI:10.1145/3452021

General Chair:
Leonid Libkin
University of Edinburgh, UK and ENS-Paris, France
,
Program Chairs:
Reinhard Pichler
TU Wien, Austria
,
Paolo Guagliardo
University of Edinburgh, UK

Copyright © 2021 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 the author(s) 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: 20 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF (National Science Foundation)

Conference

SIGMOD/PODS '21

Sponsor:

SIGMOD

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

June 20 - 25, 2021

Virtual Event, China

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
260
Total Downloads

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

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Amezian El Khalfioui AWijsen J(2024)Computing Range Consistent Answers to Aggregation Queries via RewritingProceedings of the ACM on Management of Data10.1145/36958362:5(1-19)Online publication date: 7-Nov-2024
https://doi.org/10.1145/3695836
Koutris POuyang XWijsen J(2024)Consistent Query Answering for Primary Keys on Rooted Tree QueriesProceedings of the ACM on Management of Data10.1145/36511392:2(1-26)Online publication date: 14-May-2024
https://doi.org/10.1145/3651139
Padmanabha ASegoufin LSirangelo C(2024)A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-JoinProceedings of the ACM on Management of Data10.1145/36511372:2(1-15)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651137
Fan ZKoutris POuyang XWijsen J(2023)LinCQA: Faster Consistent Query Answering with Linear Time GuaranteesProceedings of the ACM on Management of Data10.1145/35887181:1(1-25)Online publication date: 30-May-2023
https://doi.org/10.1145/3588718

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