Query Optimization for Deductive Databases

A systematic, efficient compilation method for query evaluation of DeductiveDatabases (DeDB) is proposed in this paper. In order to eliminate redundancyand to minimize the potentially relevant facts, which are two key issues to theefficiency of a DeDB, the compilation process is decomposed into two phases.The first is the pre-compilation phase, which is responsible for the minimiza-tion of the potentially relevant facts. The second, which we refer to as thegeneral compilation phase, is responsible for the elimination of redundancy.The rule/goal graph devised by J. D. Ullman is appropriately extended andused as a uniform formalism. Two general algorithms corresponding to the twophases respectively are described intuitively and formally

On Local StratifiabUity of Logic Programs and Databases

In this paper,we deal with the problem of verifying local stratifiability of logic programs and databases presented by Przymusinski.Necessary and sufficient conditions for the local stratifiability of logic programs are presented and algorithms for performing the verification are developed.Finally,we prove that a database DB containing clauses with disjunctive consequents can be easily converted into a logic program P such that DB is locally stratified iff P is locally stratified.

A Deductive Database Approach for Complex Objects

A deductive database approach for complex objects reasoning is proposed,which is characterized by handling predicates nesting in terms of mapping hierarchically structured rules and facts to a flattened Horn-clause implementation scheme.

Closed World Assumption for Disjunctive Reasoning

In this paper, the relationship between argumentation and closed world reasoning for disjunctive information is studied. In particular, the authors propose a simple and intuitive generalization of the closed world assumption (CWA) for general disjunctive deductive databases (with default negation). This semantics, called DCWA, allows a natural argumentation-based interpretation and can be used to represent reasoning for disjunctive information. We compare DCWA with GCWA and prove that DCWA extends Minker's GCWA to the class of disjunctive databases with default negation. Also we compare our semantics with some related approaches. In addition, the computational complexity of DCWA is investigated.

Magic Sets Revisited

This paper distinguishes among three kinds of linear recursions: canonical strongly linear recursion (CSLR), non-interdependent linear recursion (NILR) and interdependent linear recurstion (ILR) and presents an optimal algorithm for each. First, for the CSLRs, the magic-set method is refined in such a way that queries can be evaluated efficiently. Then, for the NILRS and ILRs, the concept of query dependency graphs is introduced to partition the rules of a program into a set of CSLRs and the computation is elaborated so that the oplimization for CSLRs can also be applied.

Bottom-up Evaluation of Datalog with Negation

Declarative semantics gives the meaning of a logic program in terms of properties,while the procedural semantics gives the meaning in terms of the execution or evalua-tion of the program. From the database point of view, the procedural semantics of theprogram is equally important. This paper focuses on the study of the bottom-up eval-uation of the WFM semantics of datalog- programs. To compute the WFM, first, thestability transformation is revisited, and a new operator Op and its fixpoint are defined.Based on this, a fixpoint semantics, called oscillating fixpoint model semantics, is de-fined. Then, it is shown that for any datalog program the oscillating fixpoint model isidentical to its WFM. So, the oscillating fixpoint model can be viewed as an alternative(constructive) definition of WFM. The underlying operation (or transformation) forreaching the oscillating fixpoint provides a potential of bottom-up evaluation. For thesake of computational feasibility, the strongly range-restricted program is considered,and an algorithm used to compute the oscillating fixpoint is described.

Techniques of Integrating Datalogwith PROLOG

Since extending DATALOG to a general-purpose programming language seems very difficult, many projects have embedded a DATALOG-based query language into a procedural host language, such as CORAL, Glue-Nail, etc.Although DATALOG can be considered as function-free PROLOG, they are very different in many aspects. For instance, DATALOG is declarative while PROLOG isn't, DATALoG takes 'a-set-at-atime' mode of evaluation but PROLOG takes 'a-tuple-at-a-time' one, DATALOG is only a query language whereas PROLOG is a general-purpose programming language. It is thought that integrating DATALOG with PROLOG may take their advantages. KBASEP is such a language. It uses KBASE as the query language and PROLOG as its procedural host language, where KBASE is an extension of DATALOG with negation and function. This paper introduces the integration techniques used in KBASE-P system.

Class Based Contextual Logic for DOOD

Contextual logic provides a mechanism to reason about modules. In this paper, this theory of modules is extended to a context theory of classes where class is in the true spirit of object-oriented databases. The logic, referred to as CLOG,is class-based. CLOG supports class, object identity, multiple role of object,monotonic and non-monotonic inheritance of data a-nd method, method factor-ing, views, derived and query classes. Views and derived classes are queries in themselves- Objects are pure data terms representing the ground instances of facts in the class. 'Object identity is a first class term in the logic. Inheritance is handled through delegation.