# Revision Programming

In this project we introduce and investigate 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

$a\; <-\; a$_{1},...,a_{k}

where $a$ and all $a$_{i} are
of the form $in(a)$ and $out(b)$. 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 B a collection (possibly empty)
of P-justified revisions of B. In our investigations,
we exhibited fundamental properties of revision programming.
We studied the relationship of revision
programming to logic programming. We investigated the complexity of reasoning
with revision programs as well as algorithms to compute P-justified
revisions. Most importantly from the practical database perspective, we
identified two classes of revision programs, safe and stratified,
with a desirable property that they determine for each initial database
a unique revision.
Our current focus is on algorithms for computing justified revisions and
on implementations.

This project is supported by the NSF grant IRI-9400568.

### People Involved

#### Faculty

#### Graduate Students

### Related papers

**
Revision programming **
**
Revision programming, database updates and integrity constraints
**
**
Revision specifications by means of programs **
**
Approximating the stable model semantics is hard **
**
Experimenting with Nonmonotonic Reasoning **
**
Extremal problems in logic programming and stable model
computation**
**
Minimal number of permutations sufficient to compute all
extensions ...**

Send us mail about computing
with default logic
##### Last modified: March 11, 97 MT