Abstract
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 language | English |
|---|---|
| Title of host publication | Database Theory - ICDT 1995 - 5th International Conference, Proceedings |
| Editors | Moshe Y. Vardi, Georg Gottlob |
| Pages | 368-382 |
| 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 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 893 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 5th International Conference on Database Theory, ICDT 1995 |
|---|---|
| Country/Territory | Czech Republic |
| City | Prague |
| Period | 1/11/95 → 1/13/95 |
Bibliographical note
Publisher Copyright:© Springer-Verlag Berlin Heidelberg 1995.
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science