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

article

Minimal-change integrity maintenance using tuple deletions

Authors:

Jerzy MarcinkowskiAuthors Info & Claims

Information and Computation, Volume 197, Issue 1-2

Pages 90 - 121

Published: 01 February 2005 Publication History

Abstract

We address the problem of minimal-change integrity maintenance in the context of integrity constraints in relational databases. We assume that integrity-restoration actions are limited to tuple deletions. We focus on two basic computational issues: repair checking (is a database instance a repair of a given database?) and consistent query answers [in: ACM Symposium on Principles of Database Systems (PODS), 1999, 68] (is a tuple an answer to a given query in every repair of a given database?). We study the computational complexity of both problems, delineating the boundary between the tractable and the intractable cases. We consider denial constraints, general functional and inclusion dependencies, as well as key and foreign key constraints. Our results shed light on the computational feasibility of minimal-change integrity maintenance. The tractable cases should lead to practical implementations. The intractability results highlight the inherent limitations of any integrity enforcement mechanism, e.g., triggers or referential constraint actions, as a way of performing minimal-change integrity maintenance.

References

[1]

Abiteboul, S., Hull, R. and Vianu, V., Foundations of databases. 1995. Addison-Wesley, Reading, MA.

Digital Library

[2]

S. Agarwal, A.M. Keller, G. Wiederhold, K. Saraswat, Flexible relation: an approach for integrating data from multiple, possibly inconsistent databases, in: IEEE International Conference on Data Engineering (ICDE), 1995, pp. 495-504

Digital Library

[3]

M. Arenas, L. Bertossi, J. Chomicki, Consistent query answers in inconsistent databases, in: ACM Symposium on Principles of Database Systems (PODS), 1999, pp. 68-79

Digital Library

[4]

Arenas, M., Bertossi, L. and Chomicki, J., Specifying and querying database repairs using logic programs with exceptions. In: International conference on flexible query answering systems (FQAS), Springer-Verlag, Berlin. pp. 27-41.

[5]

Arenas, M., Bertossi, L. and Chomicki, J., Scalar aggregation in FD-inconsistent databases. In: LNCS, vol. 1973. Springer-Verlag, Berlin. pp. 39-53.

Digital Library

[6]

Arenas, M., Bertossi, L. and Chomicki, J., Answer sets for consistent query answering in inconsistent databases. Theory and Practice of Logic Programming. v3 i4-5. 393-424.

Digital Library

[7]

Arenas, M., Bertossi, L., Chomicki, J., He, X., Raghavan, V. and Spinrad, J., Scalar aggregation in inconsistent databases. Theoretical Computer Science. v296 i3. 405-434.

Digital Library

[8]

Arenas, M., Bertossi, L. and Kifer, M., Applications of annotated predicate calculus to querying inconsistent databases. In: LNCS, vol. 1861. Springer-Verlag, Berlin. pp. 926-941.

Digital Library

[9]

Baral, C., Kraus, S., Minker, J. and Subrahmanian, V.S., Combining knowledge bases consisting of first-order theories. Computational Intelligence. v8. 45-71.

[10]

P. Barcelo, L. Bertossi, Repairing databases with annotated predicate logic, in: S. Benferhat, E. Giunchiglia (Eds.), Ninth International Workshop on Non-Monotonic Reasoning (NMR02), Special Session: Changing and Integrating Information: From Theory to Practice, 2002, pp. 160-170

[11]

Barcelo, P. and Bertossi, L., Logic programs for querying inconsistent databases. In: LNCS, vol. 2562. Springer-Verlag, Berlin. pp. 208-222.

Digital Library

[12]

Bertossi, L. and Chomicki, J., Query answering in inconsistent databases. In: Chomicki, J., van der Meyden, R., Saake, G. (Eds.), Logics for emerging applications of databases, Springer-Verlag, Berlin. pp. 43-83.

Digital Library

[13]

L. Bertossi, J. Chomicki, A. Cortes, C. Gutierrez, Consistent answers from integrated data sources, in: International Conference on Flexible Query Answering Systems (FQAS), Copenhagen, Denmark, October 2002, Springer-Verlag, Berlin, pp. 71-85

Digital Library

[14]

L. Bravo, L. Bertossi, Logic programs for consistently querying data integration systems, in: International Joint Conference on Artificial Intelligence (IJCAI), 2003, pp. 10-15

Digital Library

[15]

Bry, F., Query answering in information systems with integrity constraints. In: IFIP WG 11.5 working conference on integrity and control in information systems, Chapman and Hall, London. pp. 113-130.

Digital Library

[16]

Buneman, P., Davidson, S., Fan, W., Hara, C. and Tan, W., Keys for XML. Computer Networks. v39 i5. 473-487.

[17]

A. Calı¿, D. Lembo, R. Rosati, On the decidability and complexity of query answering over inconsistent and incomplete databases, in: ACM Symposium on Principles of Database Systems (PODS), 2003, pp. 260-271

Digital Library

[18]

A. Calı¿, D. Lembo, R. Rosati, Query rewriting and answering under constraints in data integration systems, in: International Joint Conference on Artificial Intelligence (IJCAI), 2003, pp. 16-21

Digital Library

[19]

Celle, A. and Bertossi, L., Querying inconsistent databases: algorithms and implementation. In: LNCS, vol. 1861. Springer-Verlag, Berlin. pp. 942-956.

Digital Library

[20]

A. Chandra, P. Merlin, Optimal implementation of conjunctive queries in relational databases, in: ACM SIGACT Symposium on the Theory of Computing (STOC), 1977, pp. 77-90

Digital Library

[21]

Chandra, A.K. and Harel, D., Computable queries for relational databases. Journal of Computer and System Sciences. v21. 156-178.

[22]

J. Chomicki, J. Marcinkowski, On the computational complexity of consistent query answers, Technical Report, April 2002. Available from: <arXiv:cs.DB/0204010, arXiv.org e-Print archive>

[23]

J. Chomicki, J. Marcinkowski, On the computational complexity of minimal-change integrity maintenance in relational databases, in: L. Bertossi, A. Hunter, T. Schaub (Eds.), Inconsistency Tolerance, Springer-Verlag, Berlin, 2005

Digital Library

[24]

J. Chomicki, J. Marcinkowski, S. Staworko, Computing consistent query answers using conflict hypergraphs, in: International Conference on Information and Knowledge Management (CIKM), ACM Press, 2004. Short version in IIWeb'04

Digital Library

[25]

Chou, T. and Winslett, M., A model-based belief revision system. Journal of Automated Reasoning. v12. 157-208.

[26]

Complexity and expressive power of logic programming. ACM Computing Surveys. v33 i3. 374-425.

Digital Library

[27]

C.J. Date, Referential integrity, in: International Conference on Very Large Data Bases (VLDB), 1981, pp. 2-12

Digital Library

[28]

Dung, P.M., Integrating data from possibly inconsistent databases. In: International conference on cooperative information systems (COOPIS), brussels, belgium, IEEE Press. pp. 58-65.

Digital Library

[29]

Duschka, O.M., Genesereth, M.R. and Levy, A.Y., Recursive query plans for data integration. Journal of Logic Programming. v43 i1. 49-73.

[30]

T. Eiter, M. Fink, G. Greco, D. Lembo, Efficient evaluation of logic programs for querying data integration systems, in: International Conference on Logic Programming (ICLP), 2003, pp. 163-177

[31]

Eiter, T. and Gottlob, G., On the complexity of propositional knowledge base revision, updates, and counterfactuals. Artificial Intelligence. v57 i2-3. 227-270.

Digital Library

[32]

Fan, W., Kuper, G. and Simeon, J., A unified constraint model for XML. Computer Networks. v39 i5. 489-505.

[33]

Fan, W. and Simeon, J., Integrity constraints for XML. Journal of Computer and System Sciences. v66 i1. 254-291.

Digital Library

[34]

A. Fuxman, R. Miller, Towards inconsistency management in data integration systems, in: IJCAI-03 Workshop on Information Integration on the Web (IIWeb-03), 2003

[35]

P. Gärdenfors, H. Rott, Belief revision, in: D.M. Gabbay, C.J. Hogger, J.A. Robinson (Eds.), Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 4, Oxford University Press, Oxford, 1995, pp. 35-132

Digital Library

[36]

Giannotti, F., Greco, S., Saccí, D. and Zaniolo, C., Programming with non-determinism in deductive databases. Annals of Mathematics and Artificial Intelligence. v19 i3-4.

Digital Library

[37]

Giannotti, F. and Pedreschi, D., Datalog with non-deterministic choice computes NDB-PTIME. Journal of Logic Programming. v35. 75-101.

[38]

Greco, G., Greco, S. and Zumpano, E., A logic programming approach to the integration, repairing and querying of inconsistent databases. In: LNCS, vol. 2237. Springer-Verlag, Berlin. pp. 348-364.

Digital Library

[39]

Greco, G., Greco, S. and Zumpano, E., A logical framework for querying and repairing inconsistent databases. IEEE Transactions on Knowledge and Data Engineering. v15 i6. 1389-1408.

Digital Library

[40]

Greco, S., Sacca, D. and Zaniolo, C., Datalog queries with stratified negation and choice: from P to DP. In: International conference on database theory (ICDT), Springer-Verlag, Berlin. pp. 82-96.

Digital Library

[41]

Greco, S. and Zumpano, E., Querying inconsistent databases. In: LNCS, vol. 1955. Springer-Verlag, Berlin. pp. 308-325.

Digital Library

[42]

Halevy, A.Y., Answering queries using views: a survey. VLDB Journal. v10 i4. 270-294.

Digital Library

[43]

T. Imieliński, S. Naqvi, K. Vadaparty, Incomplete objects-a data model for design and planning applications, in: ACM SIGMOD International Conference on Management of Data, Denver, Colorado, May 1991, pp. 288-297

Digital Library

[44]

Imieliński, T., van der Meyden, R. and Vadaparty, K., Complexity tailored design: a new design methodology for databases with incomplete information. Journal of Computer and System Sciences. v51 i3. 405-432.

Digital Library

[45]

Kanellakis, P.C., Elements of relational database theory. In: van Leeuwen, Jan (Ed.), Handbook of theoretical computer science, vol. B. Elsevier/MIT Press. pp. 1073-1158.

Digital Library

[46]

D. Lembo, M. Lenzerini, R. Rosati, Source inconsistency and incompleteness in data integration, in: 9th International Workshop on Knowledge Representation meets Databases (KRDB'02), Toulouse, France, 2002

[47]

M. Lenzerini, Data integration: a theoretical perspective, in: ACM Symposium on Principles of Database Systems (PODS), 2002, pp. 233-246, Invited talk

Digital Library

[48]

Lin, J. and Mendelzon, A.O., Merging databases under constraints. International Journal of Cooperative Information Systems. v7 i1. 55-76.

[49]

B. Ludäscher, W. May, G. Lausen, Referential actions as logical rules, in: ACM Symposium on Principles of Database Systems (PODS), 1997, pp. 217-227

Digital Library

[50]

Mannila, H. and Räihä, K.-J., The design of relational databases. 1992. Addison-Wesley, Reading, MA.

Digital Library

[51]

Markowitz, V.M. and Makowsky, J.A., Identifying extended entity-relationship object structures in relational schemas. IEEE Transactions on Software Engineering. v16 i8. 777-790.

Digital Library

[52]

May, W. and Ludäscher, B., Understanding the global semantics of referential actions using logic rules. ACM Transactions on Database Systems. v27 i4. 343-397.

Digital Library

[53]

Melton, J. and Simon, A.R., SQL:1999 understanding relational language components. 2002. Morgan Kaufmann.

Digital Library

[54]

van der Meyden, R., Logical approaches to incomplete information: a survey. In: Chomicki, J., Saake, G. (Eds.), Logics for databases and information systems, Kluwer Academic Publishers, Boston. pp. 307-356.

Digital Library

[55]

Van Nieuwenborgh, D. and Vermeir, D., Preferred answer sets for ordered logic programs. In: LNAI, vol. 2424. Springer-Verlag, Berlin. pp. 432-443.

Digital Library

[56]

M.Y. Vardi, The Complexity of relational query languages, in: ACM Symposium on Theory of Computing (STOC), 1982, pp. 137-146

Digital Library

[57]

Wijsen, J., Condensed representation of database repairs for consistent query answering. In: LNCS, vol. 2572. Springer-Verlag, Berlin. pp. 378-393.

Digital Library

[58]

Wijsen, J., Making more out of an inconsistent database. In: East-european conference on advances in databases and information systems (ADBIS), Springer, Berlin.

[59]

M. Winslett, Reasoning about action using a possible models approach, in: National Conference on Artificial Intelligence, 1988, pp. 79-83

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
Bienvenu MCima GGutiérrez-Basulto VElkind E(2023)REPLACEProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/349(3132-3139)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/349
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
Show More Cited By

Index Terms

Minimal-change integrity maintenance using tuple deletions
1. Information systems
  1. Data management systems
  2. Information systems applications
    1. Decision support systems
      1. Data warehouses
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

On the computational complexity of minimal-change integrity maintenance in relational databases
Inconsistency Tolerance

We address the problem of minimal-change integrity maintenance in the context of integrity constraints in relational databases. Using the framework proposed by Arenas, Bertossi, and Chomicki [5], we focus on two basic computational issues: repair ...
Maintenance of database integrity in a schema-less database system
Differential Relational Calculus for Integrity Maintenance

A differential calculus for first-order logic is developed to enforce database integrity. Formal differentiation of first-order sentences is useful in maintaining database integrity, since once a database constraint is expressed as a first-order ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information and Computation

Information and Computation Volume 197, Issue 1-2

February, 2005

147 pages

ISSN:0890-5401

Issue’s Table of Contents

Copyright © Elsevier Inc. © 2005.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 February 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

108
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 12 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
Bienvenu MCima GGutiérrez-Basulto VElkind E(2023)REPLACEProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/349(3132-3139)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/349
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
Zhang AHu SZong CLi JXia X(2023)Computing Maximal Likelihood Subset Repair for Inconsistent DataWeb and Big Data10.1007/978-981-97-2390-4_1(1-15)Online publication date: 6-Oct-2023
https://dl.acm.org/doi/10.1007/978-981-97-2390-4_1
Li YNadal SRomero O(2022)A Data Quality Framework for Graph-Based Virtual Data Integration SystemsAdvances in Databases and Information Systems10.1007/978-3-031-15740-0_9(104-117)Online publication date: 5-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-15740-0_9
Livshits EHeidari AIlyas IKimelfeld B(2021)Approximate denial constraintsProceedings of the VLDB Endowment10.14778/3401960.340196613:10(1682-1695)Online publication date: 10-Mar-2021
https://dl.acm.org/doi/10.14778/3401960.3401966
Deutch DFrost NGilad ASheffer ODemartini GZuccon GCulpepper JHuang ZTong H(2021)Explanations for Data Repair Through Shapley ValuesProceedings of the 30th ACM International Conference on Information & Knowledge Management10.1145/3459637.3482341(362-371)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3459637.3482341
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
Ye CWang HZheng KKong YZhu RGao JLi J(2021)Constrained Truth DiscoveryIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.298239334:1(205-218)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.1109/TKDE.2020.2982393
Gilad AHu YDeutch DRoy S(2020)MuSeProceedings of the VLDB Endowment10.14778/3415478.341550913:12(2921-2924)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.14778/3415478.3415509
Show More Cited By

View Options

View options

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 Issue’s Table of Contents