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.
|Title of host publication||Database Theory - ICDT 1995 - 5th International Conference, Proceedings|
|Editors||Moshe Y. Vardi, Georg Gottlob|
|Number of pages||15|
|State||Published - 1995|
|Event||5th International Conference on Database Theory, ICDT 1995 - Prague, Czech Republic|
Duration: Jan 11 1995 → Jan 13 1995
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||5th International Conference on Database Theory, ICDT 1995|
|Period||1/11/95 → 1/13/95|
Bibliographical notePublisher Copyright:
© Springer-Verlag Berlin Heidelberg 1995.
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science (all)