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

research-article

A Logical Framework for Querying and Repairing Inconsistent Databases

Authors:

Gianluigi Greco,

Ester ZumpanoAuthors Info & Claims

IEEE Transactions on Knowledge and Data Engineering, Volume 15, Issue 6

Pages 1389 - 1408

https://doi.org/10.1109/TKDE.2003.1245280

Published: 01 November 2003 Publication History

Abstract

In this paper, we address the problem of managing inconsistent databases, i.e., databases violating integrity constraints. We propose a general logic framework for computing repairs and consistent answers over inconsistent databases. A repair for a possibly inconsistent database is a minimal set of insert and delete operations which makes the database consistent, whereas a consistent answer is a set of tuples derived from the database, satisfying all integrity constraints. In our framework, different types of rules defining general integrity constraints, repair constraints (i.e., rules defining conditions on the insertion or deletion of atoms), and prioritized constraints (i.e., rules defining priorities among updates and repairs) are considered. We propose a technique based on the rewriting of constraints into (prioritized) extended disjunctive rules with two different forms of negation (negation as failure and classical negation). The disjunctive program can be used for two different purposes: to compute "repairs" for the database and produce consistent answers, i.e., a maximal set of atoms which do not violate the constraints. We show that our technique is sound, complete (each preferred stable model defines a repair and each repair is derived from a preferred stable model), and more general than techniques previously proposed.

References

[1]

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

Digital Library

[2]

S. Agarwal A.M. Keller G. Wiederhold and K. Saraswat, “Flexible Relation: An Approach for Integrating Data from Multiple, Possibly Inconsistent Databases,” Proc. Int'l Conf. Data Eng., 1995.]]

Digital Library

[3]

M. Arenas L. Bertossi and J. Chomicki, “Consistent Query Answers in Inconsistent Databases,” Proc. Int'l Symp. Principles of Database Systems, pp. 68-79, 1999.]]

Digital Library

[4]

M. Arenas L. Bertossi and J. Chomicki, “Specifying and Querying Database Repairs Using Logic Programs with Exceptions,” Proc. Int'l Conf. Flexible Query Answering, pp. 27-41, 2000.]]

[5]

M. Arenas L. Bertossi and J. Chomicki, “Scalar Aggregation in FD-Inconsistent Databases,” Proc. Int'l Conf. Database Theory, pp. 39-53, 2001.]]

Digital Library

[6]

C. Baral S. Kraus and J. Minker, “Combining Multiple Knowledge Bases,” IEEE Trans. Knowledge and Data Eng., vol. 3, no. 2, pp. 208-220, June 1991.]]

Digital Library

[7]

C. Baral S. Kraus J. Minker and V.S. Subrahmanian, “Combining Knowledge Bases Consisting of First Order Theories,” Proc. ISMIS Conf., pp. 92-101, 1991.]]

Digital Library

[8]

R. Ben-Eliyahu and R. Dechter, “On Computing Minimal Models,” Annals of Math. and Artificial Intelligence, vol. 18, no. 1, pp. 3-27, 1996.]]

[9]

S. Brass J. Dix I. Niemelae and T. Przymusinski, “On the Equivalence of the STATIC and Disjunctive Well-Founded Semantics and Their Computation,” Theoretical Computer Science, vol. 258, nos. 1-2, pp. 523-553, 2001.]]

Digital Library

[10]

F. Bry, “Query Answering in Information System with Integrity Constraints,” Proc. IFIP WG 11.5 Working Conf. Integrity and Control in Information System, 1997.]]

Digital Library

[11]

F. Bry and R. Manthey, “Checking Consistency of Database Constraints: A Logical Basis,” Proc. Very Large Data Bases Conf., pp. 13-20, 1986.]]

Digital Library

[12]

F. Bry, “Intensional Updates: Abduction via Deduction,” Proc. Int'l Conf. Logic Programming (ICLP), pp. 561-575, 1990.]]

Digital Library

[13]

F. Bry and A.H. Yahya, “Positive Unit Hyperresolution Tableaux and Their Application to Minimal Model Generation,” J. Automated Reasoning, vol. 25, no. 1, pp. 35-82, 2000.]]

Digital Library

[14]

F. Buccafurri W. Faber and N. Leone, “Disjunctive Deductive Databases with Inheritance,” Proc. Int'l Conf. Logic Programming, pp. 79-93, 1999.]]

Digital Library

[15]

M. Cadoli T. Eiter and G. Gottlob, “Default Logic as a Query Language,” IEEE Trans. Knowledge and Data Eng., vol. 9, no. 3, pp. 448-463, May/June 1997.]]

Digital Library

[16]

J. Dix U. Furbach and I. Niemela, “Nonmonotonic Reasoning: Towards Efficient Calculi and Implementations,” Handbook of Automated Reasoning, pp. 1241-1354, 2001.]]

Digital Library

[17]

P.M. Dung, “Integrating Data from Possibly Inconsistent Databases,” Proc. Int'l Conf. Cooperative Information Systems, pp. 58-65, 1996.]]

Digital Library

[18]

T. Eiter G. Gottlob and H. Mannila, “Disjunctive Datalog,” ACM Trans. Database Systems, vol. 22, no. 3, pp. 364-418, 1997.]]

Digital Library

[19]

T. Eiter N. Leone C. Mateis G. Pfeifer and F. Scarcello, “A Deductive System for Non-Monotonic Reasoning,” Proc. Int'l Conf. Logic Programming and Nonmonotonic Reasoning, pp. 364-375, 1997.]]

Digital Library

[20]

E. Franconi A. Laureti Palma N. Leone S. Perri and F. Scarcello, “Census Data Repair: A Challenging Application of Disjunctive Logic Programming,” Proc. Int'l Conf. Logic for Programming and Automated Reasoning, pp. 561-578, 2001.]]

Digital Library

[21]

M. Gelfond and V. Lifschitz, “The Stable Model Semantics for Logic Programming,” Proc. Fifth Conf. Logic Programming, pp. 1070-1080, 1988.]]

[22]

M. Gelfond and V. Lifschitz, “Classical Negation in Logic Programs and Disjunctive Databases,” New Generation Computing, vol. 9, pp. 365-385, 1991.]]

Digital Library

[23]

J. Grant and V.S. Subrahmanian, “Reasoning in Inconsistent Knowledge Bases,” IEEE Trans. Knowledge and Data Eng., vol. 7, no. 1, pp. 177-189 Feb. 1995.]]

Digital Library

[24]

S. Greco and D. Sacca, “Negative Logic Programs,” Proc. North Am. Conf. Logic Programming, pp. 480-497, 1990.]]

Digital Library

[25]

S. Greco, “Binding Propagation in Disjunctive Databases,” Proc. Int'l Conf. Very Large Data Bases, pp. 287-298, 1998.]]

Digital Library

[26]

S. Greco and D. Sacca, “Complexity and Expressive Power of Deterministic Semantics for DATALOG<sup>¬</sup>,” Information and Computation, vol. 153,no. 1, pp. 81-98, 1999.]]

Digital Library

[27]

S. Greco, “Minimal Founded Semantics for Disjunctive Logic Programming,” Proc. Int'l Conf. Logic Programming and Nonmonotonic Reasoning, 1999.]]

Digital Library

[28]

S. Greco and E. Zumpano, “Querying Inconsistent Database,” Proc. Int'l Conf. Logic for Programming and Automated Reasoning, pp. 308-325, 2000.]]

[29]

G. Greco S. Greco and E. Zumpano, “Deterministic Semantics for Disjunctive Logic Programs,” Proc. AGP Int'l Conf. Declarative Programming, 2001.]]

[30]

G. Greco S. Greco and E. Zumpano, “A Logic Programming Approach to the Integration, Repairing, and Querying of Inconsistent Databases,” Proc. Int'l Conf. Logic Programming, 2001.]]

Digital Library

[31]

P.C. Kanellakis, “Elements of Relational Database Theory,” Handbook of Theoretical Computer Science, J. van Leewen, ed., vol. 2,North-Holland, 1991.]]

Digital Library

[32]

R.A. Kowalski and F. Sadri, “Logic Programs with Exceptions,” New Generation Computing, vol. 9, nos. 3/4, pp. 387-400, 1991.]]

Digital Library

[33]

J. Lin, “A Semantics for Reasoning Consistently in the Presence of Inconsistency,” Artificial Intelligence, vol. 86, no. 1, pp. 75-95, 1996.]]

Digital Library

[34]

J. Lin, “Integration of Weighted Knowledge Bases,” Artificial Intelligence, vol. 83, no. 2, pp. 363-378, 1996.]]

Digital Library

[35]

J. Lin and A.O. Mendelzon, “Merging Databases under Constraints,” Int'l J. Cooperative Information Systems, vol. 7, no. 1, pp. 55-76, 1998.]]

[36]

J. Lin and A.O. Mendelzon, “Knowledge Base Merging by Majority,” Dynamic Worlds: From the Frame Problem to Knowledge Management, R. Pareschi and B. Fronhoefer eds., Kluwer, 1999.]]

[37]

J. Minker, “On Indefinite Data Bases and the Closed World Assumption,” Proc. Sixth Conf. Automated Deduction, pp. 292-308, 1982.]]

Digital Library

[38]

J.M. Nicolas, “Logic for Improving Integrity Checking in Relational Data Bases,” Acta Informatica, vol. 18, pp. 227-253, 1982.]]

Digital Library

[39]

I Niemela, “Stable Model Semantics: From Theory to Implementations and Applications,” Proc. Tutorial First Int'l Conf. Computational Logic (CL2000), 2000.]]

[40]

L.M. Pereira J.J. Alferes and J.N. Aparicio, “Contradiction Removal Semantics with Explicit Negation,” Knowledge Representation and Reasoning Under Uncertainty, M. Masuch and L. Polos, eds., pp. 91-106, Springer-Verlag, 1994.]]

Digital Library

[41]

K.A. Ross, “The Well Founded Semantics for Disjunctive Logic Programs,” Proc. Int'l Conf. Deductive and Object-Oriented Databases, pp. 385-402, 1989.]]

[42]

D. Sacca and C. Zaniolo, “Deterministic and Non-Deterministic Stable Models,” J. Logic and Computation, vol. 7, no. 5, pp. 555-579, 1997.]]

[43]

C. Sakama and K. Inoue, “Prioritized Logic Programming and Its Application to Commonsense Reasoning,” Artificial Intelligence, vol. 123, pp. 185-222, 2000.]]

Digital Library

[44]

V.S. Subrahmanian, “Amalgamating Knowledge Bases,” ACM Trans. Database Systems, vol. 19, no. 2, pp. 291-331, 1994.]]

Digital Library

[45]

J.K. Ullman, Principles of Database and Knowledge-Base Systems, vol. 1. Rockville, Md.: Computer Science Press, 1988.]]

Digital Library

[46]

X. Wang J.H. You and L.Y. Yuan, “Nonmonotonic Reasoning by Monotonic Inferences with Priority Conditions,” Proc. Int'l Workshop Nonmonotonic Extensions of Logic Programming, pp. 91-109, 1996.]]

Digital Library

[47]

Y. Zang and N. Foo, “Answer Sets for Prioritized Logic Programs,” Proc. Int'l Logic Programming Symp., pp. 69-83, 1997.]]

Digital Library

Cited By

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://dl.acm.org/doi/10.1145/3651139
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://dl.acm.org/doi/10.1145/3588718
Koutris POuyang XWijsen JLibkin LPichler RGuagliardo P(2021)Consistent Query Answering for Primary Keys on Path QueriesProceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3452021.3458334(215-232)Online publication date: 20-Jun-2021
https://dl.acm.org/doi/10.1145/3452021.3458334
Show More Cited By

Index Terms

Recommendations

Repair localization for query answering from inconsistent databases

Query answering from inconsistent databases amounts to finding “meaningful” answers to queries posed over database instances that do not satisfy integrity constraints specified over their schema. A declarative approach to this problem relies on the ...
Querying and repairing inconsistent numerical databases

The problem of extracting consistent information from relational databases violating integrity constraints on numerical data is addressed. In particular, aggregate constraints defined as linear inequalities on aggregate-sum queries on input data are ...
Repair checking in inconsistent databases: algorithms and complexity
ICDT '09: Proceedings of the 12th International Conference on Database Theory

Managing inconsistency in databases has long been recognized as an important problem. One of the most promising approaches to coping with inconsistency in databases is the framework of database repairs, which has been the topic of an extensive ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Knowledge and Data Engineering

IEEE Transactions on Knowledge and Data Engineering Volume 15, Issue 6

November 2003

249 pages

ISSN:1041-4347

Issue’s Table of Contents

Copyright © Copyright © 2003 IEEE. All Rights Reserved.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 November 2003

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

80
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

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://dl.acm.org/doi/10.1145/3651139
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://dl.acm.org/doi/10.1145/3588718
Koutris POuyang XWijsen JLibkin LPichler RGuagliardo P(2021)Consistent Query Answering for Primary Keys on Path QueriesProceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3452021.3458334(215-232)Online publication date: 20-Jun-2021
https://dl.acm.org/doi/10.1145/3452021.3458334
Dixit AKolaitis PLi GLi ZIdreos SSrivastava D(2021)CAvSAT: Answering Aggregation Queries over Inconsistent Databases via SAT SolvingProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3452749(2701-2705)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3452749
Calautti MCaroprese LGreco SMolinaro CTrubitsyna IZumpano EDesai BCho W(2020)Consistent query answering with prioritized active integrity constraintsProceedings of the 24th Symposium on International Database Engineering & Applications10.1145/3410566.3410592(1-10)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3410566.3410592
Amezian El Khalfioui AJoertz JLabeeuw DStaquet GWijsen Jd'Aquin MDietze SHauff CCurry ECudre Mauroux P(2020)Optimization of Answer Set Programs for Consistent Query Answering by Means of First-Order RewritingProceedings of the 29th ACM International Conference on Information & Knowledge Management10.1145/3340531.3411911(25-34)Online publication date: 19-Oct-2020
https://dl.acm.org/doi/10.1145/3340531.3411911
Faber W(2020)An Introduction to Answer Set Programming and Some of Its ExtensionsReasoning Web. Declarative Artificial Intelligence10.1007/978-3-030-60067-9_6(149-185)Online publication date: 24-Jun-2020
https://dl.acm.org/doi/10.1007/978-3-030-60067-9_6
Wijsen J(2019)Foundations of Query Answering on Inconsistent DatabasesACM SIGMOD Record10.1145/3377391.337739348:3(6-16)Online publication date: 20-Dec-2019
https://dl.acm.org/doi/10.1145/3377391.3377393
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
Bertossi LSuciu DSkritek SKoch C(2019)Database Repairs and Consistent Query AnsweringProceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3294052.3322190(48-58)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1145/3294052.3322190
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents