skip to main content
10.1145/1013963.1013977acmconferencesArticle/Chapter ViewAbstractPublication PagesppdpConference Proceedingsconference-collections
Article

Active integrity constraints

Published: 24 August 2004 Publication History

Abstract

In this paper we deal with inconsistent databases and propose a logic framework that allows specifying sets of actions which should be performed to make databases consistent (repairs). The motivation of this work stems from the observation that in repairing a database it is natural to express among a set of update operations, the (preferred) actions which should be performed to repair the database. We introduce (conditioned) active integrity constraints, a simple and powerful form of active rules with declarative semantics, well suited for computing database repairs and consistent answers. We first consider a "prescriptive" semantics where the allowed actions are those specified by the constraints. Under such a semantics the existence of repairs and consistent answers is not guaranteed. Thus, we also investigate the class of universally quantified constraints under a different semantics where actions are interpreted as preference conditions on the set of possible repairs ("preferable" semantics). Under such a semantics every database with integrity constraints admits repairs and consistent answers. We show that (conditioned) active integrity constraints can be rewritten into disjunctive Datalog programs with classical negation and that (preferred) repairs can be derived through the computation of (preferred) disjunctive stable models. We study the complexity of computing repairs and consistent answers and show that active integrity constraints can also be used to express hard problems.

References

[1]
Abiteboul S., Hull R., and Vianu V. Foundations of Databases. Addison-Wesley Publishing Co., 1994.
[2]
Alferes J. J., J. A. Leite, Pereira L. M., Przymusinska H., and Przymusinski T.C. Dynamic updates of non-monotonic knowledge bases. Journal Logic Programming, 45(1-3):43--70, 2000.
[3]
Alferes J. J., Pereira L. M., Przymusinska H., and Przymusinski T. C. Lupsa language for updating logic programs. Artificial Intelligence, 138(1-2):87--116, 2002.
[4]
Arenas M., Bertossi L., and Chomicki J. Consistent query answers in inconsistent databases. In Proc. Int. Symp. on Principles of Database Systems (PODS), pages 68--79, 1999.
[5]
Arenas M., Bertossi L., and Chomicki J. Specifying and querying database repairs using logic programs with exceptions. In Flexible Query-Answering Systems (FQAS), pages 27--41, 2000.
[6]
Baral C. and Zhang Y. On the semantics of knowledge update. In IJCAI Conference, pages 97--102, 2001.
[7]
Chitta C. Embedding revision programs in logic programming situation calculus. Journal of Logic Programming, 30(1):83--97, 1997.
[8]
Bry F. Query answering in information system with integrity constraints. In IFIP, pages 113--130, 1997.
[9]
Brewka G. and Eiter T. Preferred answer sets for extended logic programs. AI, 109(1-2):297--359, 1999.
[10]
Chomicki J. Querying with intrinsic preferences. In Proc. EDBT Conference, pages 34--51, 2002.
[11]
Chomicki J., Lobo J., and Naqvi S. A. Conflict resolution using logic programming. IEEE Trans. Knowl. Data Eng., 15(1):244--249, 2003.
[12]
Eiter T., Gottlob G., and Mannila H. Disjunctive datalog. TODS, 22(3):364--418, 1997.
[13]
Flesca, S., Greco, S., Declarative semantics for active rules, In TPLP, 1(1):43-69, 2001.
[14]
Gelfond M. and Lifschitz V. The stable model semantics for logic programming. In ICLP/SLP, pages 1070--1080, 1988.
[15]
Gelfond M. and Lifschitz V. Classical negation in logic programs and disjunctive databases. NGC, 9(3/4):365--385, 1991.
[16]
Grant J. and Subrahmanian V. S. Reasoning in inconsistent knowledge bases. TKDE, 7(1):177--189, 1995.
[17]
Greco G., Greco S., and Zumpano E. A logic programming approach to the integration, repairing and querying of inconsistent databases. In ICLP, pages 348--364, 2001.
[18]
Kanellakis P. C. Elements of Relational Database Theory - Handbook of Theoretical Computer Science Vol. 2. J. van Leewen (ed.), North-Holland, 1991.
[19]
Kifer M. and Li A. On the semantics of rule-based expert systems with uncertainty. In ICDT, pages 102--117, 1988.
[20]
Kowalski R.A. and Sadri F. Logic programs with exceptions. NGC, 9(3/4):387--400, 1991.
[21]
Lin J. A semantics for reasoning consistently in the presence of inconsistency. AI, 86(1):75--95, 1996.
[22]
Marek V. W., Pivkina I., and Truszczynski M. Revision programming = logic programming + integrity constraints. In Computer Science Logic, pages 73--98, 1998.
[23]
Marek V. W. and Truszczynski M. Revision programming. Theoretical Computer Science, 190(2):241--277, 1998.
[24]
Sakama C. and Inoue K. Priorized logic programming and its application to commonsense reasoning. Artificial Intelligence, 123(1-2):185--222, 2000.
[25]
Subrahmanian V. S. Amalgamating knowledge bases. TODS, 19(2):291--331, 1994.
[26]
Ullman J. K. Principles of Database and Knowledge-Base Systems, Vol. 1. Computer Science Press, 1998.
[27]
Wijsen J. Condensed representation of database repairs for consistent query answering. In ICDT, pages 378--393, 2003.
[28]
Zhang Y. and Foo N. Answer sets for prioritized logic programs. In ILPS, pages 69--83, 1997.

Cited By

View all
  • (2022)Database Repair via Event-Condition-Action Rules in Dynamic LogicFoundations of Information and Knowledge Systems10.1007/978-3-031-11321-5_5(75-92)Online publication date: 10-Jul-2022
  • (2021)Stratification in Approximation Fixpoint Theory and Its Application to Active Integrity ConstraintsACM Transactions on Computational Logic10.1145/343075022:1(1-19)Online publication date: 5-Jan-2021
  • (2021)Neural Knowledge Base RepairsThe Semantic Web10.1007/978-3-030-77385-4_17(287-303)Online publication date: 31-May-2021
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PPDP '04: Proceedings of the 6th ACM SIGPLAN international conference on Principles and practice of declarative programming
August 2004
260 pages
ISBN:1581138199
DOI:10.1145/1013963
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: 24 August 2004

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. inconsistent database
  2. integrity constraints
  3. logic programming

Qualifiers

  • Article

Conference

PPDP04
Sponsor:

Acceptance Rates

Overall Acceptance Rate 230 of 486 submissions, 47%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)6
  • Downloads (Last 6 weeks)2
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2022)Database Repair via Event-Condition-Action Rules in Dynamic LogicFoundations of Information and Knowledge Systems10.1007/978-3-031-11321-5_5(75-92)Online publication date: 10-Jul-2022
  • (2021)Stratification in Approximation Fixpoint Theory and Its Application to Active Integrity ConstraintsACM Transactions on Computational Logic10.1145/343075022:1(1-19)Online publication date: 5-Jan-2021
  • (2021)Neural Knowledge Base RepairsThe Semantic Web10.1007/978-3-030-77385-4_17(287-303)Online publication date: 31-May-2021
  • (2020)Existential active integrity constraintsExpert Systems with Applications10.1016/j.eswa.2020.114297(114297)Online publication date: Nov-2020
  • (2019)Learning How to Correct a Knowledge Base from the Edit HistoryThe World Wide Web Conference10.1145/3308558.3313584(1465-1475)Online publication date: 13-May-2019
  • (2019)A logical framework for view updating in indefinite databasesLogic Journal of the IGPL10.1093/jigpal/jzz00327:6(777-811)Online publication date: 27-Feb-2019
  • (2018)Active integrity constraints for general-purpose knowledge basesAnnals of Mathematics and Artificial Intelligence10.1007/s10472-018-9577-y83:3-4(213-246)Online publication date: 1-Aug-2018
  • (2017)Semantics for active integrity constraints using approximation fixpoint theoryProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171642.3171766(866-872)Online publication date: 19-Aug-2017
  • (2017)Safe inductionsProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171642.3171765(859-865)Online publication date: 19-Aug-2017
  • (2017)Active Integrity Constraints: From Theory to ImplementationKnowledge Discovery, Knowledge Engineering and Knowledge Management10.1007/978-3-319-52758-1_22(399-420)Online publication date: 22-Jan-2017
  • 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