Solving the Database Update Problem Using Linear Logic
Dong-tsan LEE
Department of Computer Science,
The University of Western Australia,
Nedlands, Western Australia, AUSTRALIA.
dtlee@cs.uwa.edu.au
C. P. TSANG
Department of Computer Science,
The University of Western Australia,
Nedlands, Western Australia, AUSTRALIA.
tsang@cs.uwa.edu.au
Abstract
Database update has not been under the same intensity of research as
other aspects of databases. The main difficulty lies on the state based
semantics of the addition and deletion operations. This cannot be
expressed with the static semantics of data models. In this paper, we
formulate the database update problem in terms of Linear Logic which was
introduced by J.-Y. Girard as a resource-sensitive logic. It has aroused
considerable interest from theoretical computer scientists because of its
unique way of modelling computation. We demonstrate here that it is possible
to represent database updates by using state based properties of Linear Logic.
This approach centres around the computation of the next database
state. One feature in our approach is that it not only provides real updates
rather than database revision, but it also allows the users to reason on
previous database states. This approach works well with traditional relational
models as well as deductive databases. We also show that this formulation will
overcome the semantic difficulty of the retract assert operation as well as
the AI frame problem.
Conference Home Page