Revision programming

Victor W. Marek, Mirosław Truszczyński

Research output: Contribution to journalArticlepeer-review

60 Scopus citations

Abstract

In this paper we introduce revision programming - a logic-based framework for describing constraints on databases and providing a computational mechanism to enforce them. Revision programming captures those constraints that can be stated in terms of the membership (presence or absence) of items (records) in a database. Each such constraint is represented by a revision rule α←α1,..., αk, where a and all αi are of the form in(a) and out(e). Collections of revision rules form revision programs. Similarly as logic programs, revision programs admit both declarative and imperative (procedural) interpretations. In our paper, we introduce a semantics that reflects both interpretations. Given a revision program, this semantics assigns to any database script B sign a collection (possibly empty) of P-justified revisions of script B sign. The paper contains a thorough study of revision programming. We exhibit several fundamental properties of revision programming. We study the relationship of revision programming to logic programming. We investigate complexity of reasoning with revision programs as well as algorithms to compute P-justified revisions. Most importantly from the practical database perspective, we identify two classes of revision programs, safe and stratified, with a desirable property that they determine for each initial database a unique revision.

Original languageEnglish
Pages (from-to)241-277
Number of pages37
JournalTheoretical Computer Science
Volume190
Issue number2
DOIs
StatePublished - 1998

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

Dive into the research topics of 'Revision programming'. Together they form a unique fingerprint.

Cite this