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 <- a1,...,ak
where a and all ai 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