An Extension to GCWA and Query Evaluation for Disjunctive Deductive Databases

We present a simple and intuitive extension GCWA^G of the generalized closed world assumption (GCWA) from positive disjunctive deductive databases to general disjunctive deductive databases (with default negation). This semantics is defined in terms of unfounded sets and possesses an argumentation-theoretic characterization. We also provide a top-down procedure for GCWA^G, which is sound and complete with respect to GCWA^G. We investigate two query evaluation methods for GCWA^G: database partition, and database splitting. The basic idea of these methods is to divide the original deductive database into several smaller sub-databases and the query evaluation in the original database is transformed into the problem of query evaluation in smaller or simplified components. We prove that these two methods of query evaluation are all sound with respect to GCWA^G.     

Transactions and updates in deductive databases

In this paper, we develop a new approach that provides a smooth integration of extensional updates and declarative query languages for deductive databases. The approach is based on a declarative specification of updates in rule bodies. Updates are not executed as soon as evaluated. Instead, they are collected and then applied to the database when the query evaluation is completed. We call this approach nonimmediate update semantics. We provide a top-down and equivalent bottom-up semantics which reflect the corresponding computation models. We also package set of updates into transactions and we provide a formal semantics for transactions. Then, in order to handle complex transactions, we extend the transaction language with control constructors still preserving formal semantics and semantics equivalence     

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.     

Querying datalog with arrays: Design and implementation issues

This paper deals with the implementation of logic queries where array structures are manipulated. Both top-down and bottom-up implementations of the presented logic language, called Datalog ^A , are considered. Indeed, SLD-resolution is generalized to realize Datalog ^A top-down query answering. Further, a fixpoint based evaluation of Datalog ^A queries is introduced, which forms the basis for efficient bottom-up implementation of queries obtained by generalizing rewriting techniques such as magic set method to the case of Datalog ^A programs.Work partially supported by a European Union grant under the EC-US project DEUS EX MACHINA: nondeterminism for deductive databases and by a MURST grant (40% share) under the project Sistemi formali e strumenti per basi di dati evolute.     

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.     

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

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

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     

Upside-down meta-interpretation of the model elimination theorem-proving procedure for deduction and abduction

Typical bottom-up, forward-chaining reasoning systems such as hyperresolution lack goaldirectedness, while typical top-down, backward-chaining reasoning systems like Prolog or model elimination repeatedly solve the same goals. Reasoning systems that are goal-directed and avoid repeatedly solving the same goals can be constructed by formulating the top-down methods meta-theoretically for execution by a bottom-up reasoning system (hence, we use the term upside-down meta-interpretation). This formulation also facilitates the use of flexible search strategies, such as merit-ordered search, that are common to bottom-up reasoning systems. The model elimination theorem-proving procedure, its extension by an assumption rule for abduction, and its restriction to Horn clauses are adapted here for such upside-down meta-interpretation. This work can be regarded as an extension of the magic-sets or Alexander method for query evaluation in deductive databases to both non-Horn clauses and abductive reasoning.This research was supported by the National Science Foundation under Grant CCT-8922330 and by the Defense Advanced Research Projects Agency under Office of Naval Research Contract N00014-90-C-0220. The views and conclusions contained herein are those of the author and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the National Science Foundation, the Defense Advanced Research Projects Agency, or the United States Government.     

Memoing Evaluation for Constraint Extensions of Datalog

This paper proposes an efficient method for evaluation of deductive queries over constraint databases. The method is based on a combination of the top-down resolution with memoing and the closed form bottom-up evaluation. In this way the top-down evaluation is guaranteed to terminate for all queries for which the bottom-up evaluation terminates. The main advantage of the proposed method is the direct use of the information present in partially instantiated queries without the need for rewriting of the original program. The evaluation algorithm automatically propagates the necessary constraints during the computation. In addition, the top-down evaluation potentially allows the use of compilation techniques, developed for compilers of logic programming languages, which can make the query evaluation very efficient.     

On Local Stratifiability of Logic Prograns 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 condition for the local stratifiability of logic programs are presented and algorithms of performing the verification are developed.Finally,we prove that a database D B containing clauses with disjunctive consequents can be easily converted into a logic program P such that D B is locally statified iff P is locally stratified.     

Issues of non-determinism in PROLOG and the Committed Choice Non-Deterministic logic languages

Issues of logic programming have always been bound with those of search. Logic programs are generally thought of as a logical specification of the problem (the declarative reading) in terms of clauses. The inference mechanism of the given logic language provides a means by which the clauses can be used to prove a query to the system (procedural interpretation). The problem of search can be related into forms of non-determinism. That is how to select a possible solution path (clause). It is this criteria that is used to consider the issues of search in PROLOG and the Committed Choice Non-Deterministic execution models.     

Inductive expansion: A calculus for verifying and synthesizing functional and logic programs

Guarded Horn clauses over a many-sorted polymorphic signature provide a powerful syntax for design specifications. Expressed as a set of positive Gentzen clauses with a common guard, requirements to such a specification can be proved top-down by inductive expansion: conclusions and generators of the clauses are transformed via resolution and paramodulation upon axioms, lemmas and induction hypotheses into the guard. Case distinctions are generated when axioms or lemmas are applied in parallel. They split the proof into subexpansions, which are later rejoined by applying disjunctive lemmas. Induction orderings need not be selected before redices for induction hypotheses have been created.The controlled expansion of requirements to a function (or predicate) may produce axioms representing a program for that function. This generalizes traditional approaches to program synthesis such as fold& unfold, divide&conquer or deductive tableaus. Ground confluent and strongly terminating design specifications yield decidable criteria for constructors and unsolvable goals and thus reduce the search space of inductive expansion.     

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.     

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.     

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     

Updates with Disjunctive Information: From Syntactical and Semantical Perspectives

The possible models approach is a classical minimal change semantics for knowledge base update, which provides an exclusive interpretation for disjunctive information in updates. It has been recognized that the exclusive interpretation for disjunction may be problematic under some circumstances. In this paper, we investigate inclusive interpretations for disjunctions in updates from both syntactical and semantical viewpoints. In particular, we propose two approaches for disjunctive update—the minimal change with exceptions (MCE) and the minimal change with maximal disjunctive inclusions (MCD). Both approaches provide inclusive interpretations for disjunctions in updates, though the first is syntax‐based and the second is model‐theoretic. We then characterize the MCE and MCD in terms of alternative minimal change criteria and relate them to traditional Katsuno and Mendelzon's update postulates.     

Query Answering for OWL-DL with rules

Both OWL-DL and function-free Horn rules are decidable fragments of first-order logic with interesting, yet orthogonal expressive power. A combination of OWL-DL and rules is desirable for the Semantic Web; however, it might easily lead to the undecidability of interesting reasoning problems. Here, we present a decidable such combination where rules are required to be DL-safe: each variable in the rule is required to occur in a non-DL-atom in the rule body. We discuss the expressive power of such a combination and present an algorithm for query answering in the related logic extended with DL-safe rules, based on a reduction to disjunctive programs.     

On the Computation of the Disjunctive Well-Founded Semantics

A characterization of the disjunctive well-founded semantics (DWFS) is given in terms of the Gelfond–Lifschitz transformation. This characterization is used to develop a top-down method of testing DWFS membership, employing a hyperresolution-like operator and quasi-cyclic trees to handle minimal model processing. A flexible bottom-up method of computing the DWFS is also given that admits the use of a powerful reduction operator. For finite propositional databases, all of our methods run in polynomial space.     

On Logical Foundations of Multilevel Secure Databases

It is envisaged that the application of the multilevel security (MLS) scheme will enhance flexibility and effectiveness of authorization policies in shared enterprise databases and will replace cumbersome authorization enforcement practices through complicated view definitions on a per user basis. However, the critical problem with the current model is that the belief at a higher security level is cluttered with irrelevant or inconsistent data as no mechanism for attenuation is supported. Critics also argue that it is imperative for MLS database users to theorize about the belief of others, perhaps at different security levels, an apparatus that is currently missing and the absence of which is seriously felt.The impetus for our current research is the need to provide an adequate framework for belief reasoning in MLS databases. In this paper, we show that these concepts can be captured in a F-logic style declarative query language, called MultiLog, for MLS deductive databases for which a proof theoretic, model theoretic and fixpoint semantics exist. This development is significant from a database perspective as it now enables us to compute the semantics of MultiLog databases in a bottom-up fashion. We also define a bottom-up procedure to compute unique models of stratified MultiLog databases. Finally, we establish the equivalence of MultiLog's three logical characterizations—model theory, fixpoint theory and proof theory.