Revision programming, database updates and integrity constraints

V. Wiktor Marek, Mirosław Truszczyński

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

26 Scopus citations


We investigate revision programming, a logic-based mechanism for describing changes in databases and enforcing certain type of integrity constraints. We show that revisions justified by an initial database and a revision program can be computed by a sequential execution of the rules of the program (with subsequent check of the applicability of the rules). In general, a program may determine none, exactly one or many justified revisions of a given initial database. We exhibit two classes of programs, safe and stratified, with the property that for every initial database a unique justified revision exists. We study the complexity of basic problems associated with justified revisions. Although the existence problems are NP.-complete, for safe and stratified programs justified revisions can be computed in polynomial time.

Original languageEnglish
Title of host publicationDatabase Theory - ICDT 1995 - 5th International Conference, Proceedings
EditorsMoshe Y. Vardi, Georg Gottlob
Number of pages15
StatePublished - 1995
Event5th International Conference on Database Theory, ICDT 1995 - Prague, Czech Republic
Duration: Jan 11 1995Jan 13 1995

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference5th International Conference on Database Theory, ICDT 1995
Country/TerritoryCzech Republic

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1995.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)


Dive into the research topics of 'Revision programming, database updates and integrity constraints'. Together they form a unique fingerprint.

Cite this