Processing negation and disjunction in logic programs through integrity constraints

Integrity constraints were initially defined to verify the correctness of the data that is stored in a database. They were used to restrict the modifications that can be applied to a database. However, there are many other applications in which integrity constraints can play an important role. For example, the semantic query optimization method developed by Chakravarthy, Grant, and Minker for definite deductive databases uses integrity constraints during query processing to prevent the exploration of search space that is bound to fail. In this paper, we generalize the semantic query optimization method to apply to negated atoms. The generalized method is referred to assemantic compilation. This exploration has led to two significant results. First, semantic compilation provides an alternative search space for negative query literals. The alternative search space can find answers in cases for which negation-as-finite-failure and constructive negation cannot. Second, we show how semantic compilation can be used to transform a disjunctive database with or without functions and denial constraints without negation into a new disjunctive database that complies with the integrity constraints.     

Duality for Goal-Driven Query Processing in Disjunctive Deductive Databases

Bottom-up query-answering procedures tend to explore a much larger search space than what is strictly needed. Top-down processing methods use the query to perform a more focused search that can result in more efficient query answering. Given a disjunctive deductive database, DB, and a query, Q, we establish a strong connection between model generation and clause derivability in two different representations of DB and Q. This allows us to use a bottom-up procedure for evaluating Q against DB in a top-down fashion. The approach requires no extensive rewriting of the input theory and introduces no new predicates. Rather, it is based on a certain duality principle for interpreting logical connectives. The duality transformation is achieved by reversing the direction of implication arrows in the clauses representing both the theory and the negation of the query. The application of a generic bottom-up procedure to the transformed clause set results in top-down query answering. Under favorable conditions efficiency gains are substantial, as shown by our preliminary testing. We give the logical meaning of the duality transformation and point to the conditions and sources of improved efficiency. We show how the duality approach can be used for refined query answering by specifying the minimal conditions (weakest updates) to DB under which Q becomes derivable. This is shown to be useful for view updates in disjunctive deductive databases as well as for other interesting applications.     

Minimal model generation for refined answering of generalized queries in disjunctive deductive databases

Generalized queries are defined as sets of clauses in implication form. They cover several tasks of practical importance for database maintenance such as answering positive queries, computing database completions and integrity constraints checking. We address the issue of answering generalized queries under the minimal model semantics for the class of disjunctive deductive databases (DDDBs). The advanced approach is based on having the query induce an order on the models returned by a sound and complete minimal model generating procedure. We consider answers that are true in all and those that are true in some minimal models of the theory. We address the issue of answering positive queries through the construction of the minimal model state of the DDDB, using a minimal model generating procedure. The refinements allowed by the procedure include isolating a minimal component of a disjunctive answer, the specification of possible updates to the theory to enable the derivability of certain queries and deciding the monotonicity properties of answers to different classes of queries.     

Query evaluation in recursive databases: bottom-up and top-down reconciled

It is desirable to answer queries posed to deductive databases by computing fixpoints because such computations are directly amenable to set-oriented fact processing. However, the classical fixpoint procedures based on bottom-up processing — the naive and semi-naive methods — are rather primitive and often inefficient. In this article, we rely on bottom-up meta-interpretation for formalizing a new fixpoint procedure that performs a different kind of reasoning: We specify a top-down query answering method, which we call the Backward Fixpoint Procedure. Then, we reconsider query evaluation methods for recursive databases. First, we show that the methods based on rewriting on the one hand, and the methods based on resolution on the other hand, implement the Backward Fixpoint Procedure. Second, we interpret the rewritings of the Alexander and Magic Set methods as specializations of the Backward Fixpoint Procedure. Finally, we argue that such a rewriting is also needed in a database context for implementing efficiently the resolution-based methods. Thus, the methods based on rewriting and the methods based on resolution implement the same top-down evaluation of the original database rules by means of auxiliary rules processed bottom-up.     

Extending Datalog with Declarative Updates

The semantics of static deductive databases is well understood based on the work in logic programming. In the past decade, various methods to incorporate update constructs into logic programming and deductive databases have been proposed. However, there is still no consensus about the appropriate treatment of dynamic behavior in deductive databases. In this paper, we propose a language called DatalogU, which is a minimal but powerful extension of Datalog with updates to base relations. DatalogU allows the user to program set-oriented complex database transactions with concurrent, disjunctive and sequential update operations in a simple and direct way. It has a simple and intuitive declarative semantics that naturally accounts for set-oriented updates in deductive databases.     

Chain-split evaluation in deductive databases

Many popularly studied recursions in deductive databases can be compiled into one or a set of highly regular chain generating paths, each of which consists of one or a set of connected predicates. Previous studies on chain-based query evaluation in deductive databases take a chain generating path as an inseparable unit in the evaluation. However, some recursions, especially many functional recursions whose compiled chain consists of infinitely evaluable function(s), should be evaluated by chain-split evaluation, which splits a chain generating path into two portions in the evaluation: an immediately evaluable portion and a delayed-evaluation portion. The necessity of chain-split evaluation is examined from the points of view of both efficiency and finite evaluation, and three chain-split evaluation techniques: magic sets, buffered evaluation, and partial evaluation are developed. Our study shows that chain-split evaluation is a primitive recursive query evaluation technique for different kinds of recursions, and it can be implemented efficiently in deductive databases by extensions to the existing recursive query evaluation methods     

Dynamic maintenance of the transitive closure in disjunctive graphs

We propose an approach with feasible space requirement to maintain the transitive closure of a class of hypergraphs called OR-graphs. OR-graphs are equivalent to disjunctive deductive databases where disjunctions are limited to one attribute in each OR-table. It has been shown that query processing in disjunctive deductive databases grows into CoNP with very simple examples, but few attempts have been made, as is done in this paper, to obtain classes of disjunctive databases and queries for which efficient algorithms exist. Polynomial time algorithms are presented to compute the transitive closure of OR-graphs and to handle dynamic insertions and deletions. With algorithms for insertions and deletions, we provide a simple but efficient technique to solve the failure set problem in reliability models, which is equivalent to finding the closure of an arbitrary non-empty set of simple nodes. We also show that a minimal extension to OR-graphs makes the computational complexity of the transitive closure CoNP-complete.Research supported in part by NSF under IRI-9210220 and IRI-9111988, Omron Corporation and Omron Management Center of America.     

Relaxation as a platform for cooperative answering

Responses to queries posed by a user of a database do not always contain the information desired. Database answers to a query, although they may be logically correct, can sometimes be misleading. Research in the area of cooperative answering for databases and deductive databases seeks to rectify these problems. We introduce a cooperative method calledrelaxation for expanding deductive database and logic programming queries. The relaxation method expands the scope of a query by relaxing the constraints implicit in the query. This allows the database to return answers related to the original query as well as the literal answers themselves. These additional answers may be of interest to the user. In section 1 we introduce the problem and method. In Section 2 we give some background on the research done in cooperative answering. Section 3 discusses the relaxation method, a potential control strategy, and uses. Section 4 looks at a semantic counterpart to this notion. In Section 5 we explore some of the control and efficiency issues. We enumerate open issues in Section 6, and conclude in Section 7.     

A database of groups of prime-power order

The design, implementation and performance of TwoGroups, a deductive database for the 58,761 groups of order 2ⁿ, (n ≤ 8), is described. The system is implemented in NU-Prolog, a Prolog system with built-in functions for creating and using deductive databases. TwoGroups has a set-theoretic query language, which provides users with a familiar notation to access the data. The paper describes the data and its representation, the set-theoretic query language, its translator and optimiser, and the experiments on the performance of the database.     

Constraint-based query evaluation in deductive databases

Constraints play an important role in the efficient query evaluation in deductive databases. Constraint-based query evaluation in deductive databases is investigated, with emphasis on linear recursions with function symbols. Constraints are grouped into three classes: rule constraints, integrity constraints, and query constraints. Techniques are developed for the maximal use of different kinds of constraints in rule compilation and query evaluation. The study on the roles of different classes of constraints in set-oriented evaluation of linear recursions shows the following: rule constraints should be integrated with their corresponding deduction rules in the compilation of recursions; integrity constraints, including finiteness constraints and monotonicity constraints, should be used in the analysis of finite evaluability and termination for specific queries; and query constraints, which are often useful in search space reduction and termination, should be transformed, when necessary, and should be pushed into the compiled chains as deeply as possible for efficient evaluation. The constraint-based query-processing technique integrates query-independent compilation and chain-based query evaluation methods and demonstrates its great promise in deductive query evaluation     

一种自底向上的静态语义查询优化算法

演绎数据库语义查询优化是运用数据库中的语义知识，即完整性约束条件，将用户提交的一种查询转换为能有效执行，并与原查询等价的查询的一种优化方法．至今在这一领域已有了许多的算法，但大多是基于自顶向下的查询计算模式．而本文提出的静态语义查询优化算法及其改进算法是在优化“并”和“连接”操作的过程中进行自底向上的查询计算，因此相对自顶向下的计算方式更有效地提高了查询执行效率．     

Model theoretic approach to view updates in deductive databases

The view update problem for deductive databases has been defined as the problem of accomplishing the update of an intensional predicate by modifying appropriately the extensional database. A previous paper by Grant, Horty, Lobo, and Minker developed algorithms for the insertion and the deletion of an intensional predicate in certain important classes of stratified disjunctive deductive databases. This paper introduces a model theoretic approach which encompasses a wide class of Herbrand semantics, including the perfect model and stable model semantics, for disjunctive databases including negation. This generalizes the earlier results: now the intensional database may contain disjunctive and denial rules, and the database may be required to satisfy integrity constraints. As in the previous paper, the algorithms are proved to be correct and best according to the criterion of causing minimal change to the database, where the first priority is to minimize deletions.     

View updates in stratified disjunctive databases

The view update problem is considered in the context of deductive databases where the update of an intensional predicate is accomplished by modifying appropriately the underlying relations in the extensional database. Two classes of disjunctive databases are considered. The first class contains those disjunctive databases which allow only definite rules in the intensional database and disjunctive facts in the extensional database. The second class contains stratified disjunctive databases so that in addition to the first class, negation is allowed in the bodies of the rules, but the database must be stratified. Algorithms are given both for the insertion of an intensional predicate into and the deletion of an intensional predicate from the database. The algorithms use SLD resolution and the concept of minimal models of the extensional database. The algorithms are proved to be correct and best according to the criterion of causing minimal change to the database, where we give first priority to minimizing deletions.Research supported by the National Science Foundation under grant numbers IRI-8916059, IRI-8921591, IRI-9200898, and IRI-9210220.     

On the declarative and procedural semantics of deductive object-oriented systems

We present declarative and procedural semantics for a deductive object-oriented language, Gulog. The declarative semantics is based on preferred minimal models. We describe both bottom-up and top-down query evaluation procedures and show that they are sound with respect to the declarative semantics. The results contribute to our understanding of the interaction of inheritance, overriding and deduction in the presence of both functional and set-valued methods, and multiple inheritance.     

Incomplete deductive databases

We investigate the complexity of query processing in databases which have both incompletely specified data and deductive rules. The paper is divided into two parts: in the first we consider databases in which incompletely specified data occurs only in the database intension; in the second we consider databases in which incomplete information is represented only in database extension. We prove that, in general, the query processing problem for databases with incomplete intensions is undecidable. A number of classes of rules for which all conjunctive queries can be processed in polynomial time is then characterized. For databases with incomplete extensions we prove a number of CoNP completeness results. For instance, we demonstrate that processing disjunctions which are restricted to individual columns of database predicates can, in general, be as bad as processing arbitrary disjunctions (i.e. CoNP-complete). This falsifies the conjecture that such limited disjunctions could be computationally beneficial. We also show two simple examples of situations in which query processing is guaranteed to be polynomial. These situations are linked to certain assumptions about database updates.Finally, we provide a summary of the data complexity of queries depending on the type of database extension, intension, query sublanguage and Open World vs Closed World assumption.Research supported by NSF grant DCR 85-04140.More precisely, we can say this only in the presence of the closed world assumption [18].     

Interpreting disjunctive logic programs based on a strong sense of disjunction

This paper studies a strong form of disjunctive information in deductive databases. The basic idea is that a disjunctionA B should be considered true only in the case when neitherA norB can be inferred, but the disjunctionA B is true. Under this interpretation, databases may be inconsistent. For those databases that are consistent, it is shown that a unique minimal model exists. We study a fixpoint theory and present a sound and complete proof procedure for query processing in consistent databases. For a class of inconsistent databases, we obtain a declarative semantics by selecting an interpretation that maximizes satisfaction, and minimizes indefiniteness. Two notions of negation are introduced.     

A methodology to retrieve text documents from multiple databases

This paper presents a methodology for finding the n most similar documents across multiple text databases for any given query and for any positive integer n. This methodology consists of two steps. First, the contents of databases are indicated approximately by database representatives. Databases are ranked using their representatives with respect to the given query. We provide a necessary and sufficient condition to rank the databases optimally. In order to satisfy this condition, we provide three estimation methods. One estimation method is intended for short queries; the other two are for all queries. Second, we provide an algorithm, OptDocRetrv, to retrieve documents from the databases according to their rank and in a particular way. We show that if the databases containing the n most similar documents for a given query are ranked ahead of other databases, our methodology will guarantee the retrieval of the n most similar documents for the query. When the number of databases is large, we propose to organize database representatives into a hierarchy and employ a best-search algorithm to search the hierarchy. It is shown that the effectiveness of the best-search algorithm is the same as that of evaluating the user query against all database representatives.     

Foundations of secure deductive databases

We develop a formal logical foundation for secure deductive databases. This logical foundation is based on an extended logic involving several modal operators. We develop two models of interaction between the user and the database called “yes-no” dialogs, and “yes-no-don't know” dialogs. Both dialog frameworks allow the database to lie to the user. We develop an algorithm for answering queries using yes-no dialogs and prove that secure query processing using yes-no dialogs is NP-complete. Consequently, the degree of computational intractability of query processing with yes-no dialogs is no worse than for ordinary databases. Furthermore, the algorithm is maximally cooperative to user in the sense that lying is resorted to only when absolutely necessary. For Horn databases, we show that secure query processing can be achieved in linear time-hence, this is no more intractable than the situation in ordinary databases. Finally, we identify necessary and sufficient conditions for the database to be able to preserve security. Similar results are also obtained for yes-no-don't know dialogs     

Applying restriction constraints to deductive databases

An operation for restricting deductive databases represented as logic programs is introduced. The constraints are coded in a separate database, and the operator puts the two databases together in order to provide a restricted view of the original database. The operator is given a semantics in terms of the immediate consequence operator. Then a transformational implementation is given and its correctness is proved with respect to the abstract semantics. The approach is presented at first for positive programs and it is then extended to take negation as failure into account.     

SYGRAF: implementing logic programs in a database style

It is shown how Horn logic programs can be implemented using database techniques, namely, mostly bottom-up in combination with certain top-down elements (as opposed to the top-down implementations of logic programs prevailing so far). The proposed method is sound and complete. It easily lends itself to a parallel implementation and is free of nonlogical features like backtracking. As an extension to the common approach to deductive databases, function symbols are allowed to appear in programs, and it is shown that much of database query optimization can be applied to optimize logic programs. An important advantage of present approach is its ability to evaluate successfully many programs that terminate under neither pure top-down nor bottom-up evaluation strategies