Petri Net Semantics of Logic Programs and Deductive Databases
Joining ideas from database theory and logic programming leads to the theory of deductive databases. In addition to the data stored in a database (extensional facts), a deductive database stores rule based knowledge concerning parts of the real world which are modeled by the system. A deductive database management system (DDBMS) consists of two parts: 1) An arbitrary database management system and 2) a deduction mechanism that uses extensional as well as intensional facts and rules for deducing new data (intensional facts). Since rules can be seen as a declarative (programming, query) language, one of the main serious problems arising from logic programming and deductive databases is to find a (constructive) semantics which coincides with the user's intuitive meaning of the rules.
The aim of this work is to introduce a Petri net semantics for logic programs and deductive databases which is more constructive than any currently known semantics. Logic programs and deductive databases are transformed into a Petri net class whose elements are called, according to their dynamical behaviour, fixpoint nets. The problems of non- monotonic reasoning are expressed by means of generalized conflict situations in fixpoint nets. The semantics of a logic program or a deductive database is defined by means of logical consequences of a set of (possibly three-valued) models, which can be generated from the saturated marking of the program's Petri net representation. It is shown that for stratified normal programs and for positive disjunctive programs the Petri net semantics coincides with the perfect model semantics and the Minker/Rajasekar semantics respectively.