Designing deductive databases

We consider the problem of designing schemas for deductive databases. The design problem is to construct a database schema that supports, at minimal expected cost, a given set of database transactions. Our results include a formal definition of both a deductive database schema and a schema transformation. A schema transformation is used in the design process to transform one schema into another, with the goal of reducing the expected database costs. Our design methodology defines the concept of a schema transformation within the context of the clause-based deductive database model. The IDB of the schema that results from the design process includes clauses sufficient for a theorem prover to map queries stated against the original schema into queries against the (more cost effective) resulting schema. This allows users to interact exclusively with the initial schema, while the schema that results from the design process specifies the actual structure of the implemented database. In other words, the initial schema serves as the logical schema for the database, and the result of the design process serves as its physical schema.     

Approaches to deductive object-oriented databases

The paper is concerned with the problem of combining deductive and object-oriented features to produce a deductive object-oriented database system which is comparable to those currently available under the relational view of data modelling not only in its functionality but also in the techniques employed in its construction and use. Under this assumption, the kinds of issues that have to be tackled for a similar research strategy to produce comparable results are highlighted. The authors motivate their terms of comparison, characterize three broad approaches to deductive object-oriented databases and introduce the notion of language convergence to help in the characterization of some shortcomings that have been perceived in them. Three proposals that have come to light in the past three years are looked into in some detail, in so far as they exemplify some of the positions in the space of choices defined. The main contribution of the paper is towards a characterization of the language convergence property of deductive database languages which has a key role in addressing critiques of the deductive and object-oriented database research enterprise. A basic familiarity with notions from deductive databases and from object-oriented databases is assumed.     

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.     

A semantical framework for supporting subjective and conditional probabilities in deductive databases

We present a theoretical basis for supporting subjective and conditional probabilities in deductive databases. We design a language that allows a user greater expressive power than classical logic programming. In particular, a user can express the fact thatA is possible (i.e.A has non-zero probability),B is possible, but (A B) as a whole is impossible. A user can also freely specify probability annotations that may contain variables. The focus of this paper is to study the semantics of programs written in such a language in relation to probability theory. Our model theory which is founded on the classical one captures the uncertainty described in a probabilistic program at the level of Herbrand interpretations. Furthermore, we develop a fixpoint theory and a proof procedure for such programs and present soundness and completeness results. Finally we characterize the relationships between probability theory and the fixpoint, model, and proof theory of our programs.     

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.     

Ordered model trees: A normal form for disjunctive deductive databases

Model trees were conceived as a structure-sharing approach to represent information in disjunctive deductive databases. In this paper we introduce the concept ofordered minimal model trees as a normal form for disjunctive deductive databases. These are model trees in which an order is imposed on the elements of the Herbrand base. The properties of ordered minimal model trees are investigated as well as their possible utilization for efficient manipulation of disjunctive deductive databases. Algorithms are presented for constructing and performing operations on ordered model trees. The complexity of ordered model tree processing is addressed. Model forests are presented as an approach to reduce the complexity of ordered model tree construction and processing.This research was supported by the National Science Foundation, under the grant Nr. IRI-89-16059, the Air Force Office of Scientific Research, under the grant Nr. AFOSR-91-0350, and the Fulbright Scholar Program.This work was done while visiting at the University of Maryland Institute for Advanced Computer Studies.     

Extending Query-Subquery Nets for Deductive Databases under the Well-Founded Semantics

ABSTRACT

We propose a method, called QSQN-WF, for evaluating queries to Datalog^¬ databases under the well-founded semantics. It is the first one that is set-at-a-time and strictly goal-directed w.r.t. SLS-resolution defined by Przymusinski. These properties are important for reducing accesses to the secondary storage and redundant computations. The first property distinguishes our method from the one based on SLG-resolution by Chen, Swift, and Warren (1995 Chen, W., T. Swift, and D. S. Warren. 1995. Efficient top-down computation of queries under the well-founded semantics. Journal of Logic Programming 24 (3):161–99. doi:10.1016/0743-1066(94)00028-5[Crossref] , [Google Scholar]) (which is tuple-at-a-time). The second property distinguishes our method from the ones based on the magic-sets transformation by Kemp, Srivastava, and Stuckey (1995 Kemp, D. B., D. Srivastava, and P. J. Stuckey. 1995. Bottom-up evaluation and query optimization of well-founded models. Theoretical Computer Science 146 (1 & 2):145–84. doi:10.1016/0304-3975(94)00153-a[Crossref], [Web of Science ®] , [Google Scholar]) and Morishita (1996 Morishita, S. 1996. An extension of Van Gelder's alternating fixpoint to magic programs. Journal of Computer and System Sciences 52 (3):506–21. doi:10.1006/jcss.1996.0038[Crossref], [Web of Science ®] , [Google Scholar]), which use magic atoms not in the most appropriate way and are not strictly goal-directed w.r.t. SLS-resolution. Our method follows SLS-resolution, with Van Gelder’s alternating fixpoint semantics on the background, but uses a query-subquery net to implement tabulation and the set-at-a-time technique, reduce redundant computations, and allow any control strategy within each iteration of the main loop. It is sound and complete w.r.t. the well-founded semantics and has PTIME data complexity.     

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.     

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

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

ConceptBase — A deductive object base for meta data management

Deductive object bases attempt to combine the advantages of deductive relational databases with those of object-oriented databases. We review modeling and implementation issues encountered during the development of ConceptBase, a prototype deductive object manager supporting the Telos object model. Significant features include: 1) The symmetric treatment of object-oriented, logic-oriented and graph-oriented perspectives, 2) an infinite metaclass hierarchy as a prerequisite for extensibility and schema evolution, 3) a simple yet powerful formal semantics used as the basis for implementation, 4) a client-server architecture supporting collaborative work in a wide-area setting. Several application experiences demonstrate the value of the approach especially in the field of meta data management.     

Top-Down Query Processing in First-Order Deductive Databases under the DWFS

A top-down query-processing method for first-order deductive databases under the disjunctive well-founded semantics (DWFS) is presented. The method is based on a characterization of the DWFS in terms of the Gelfond–Lifschitz transformation and employs a hyperresolution-like operator and quasi-cyclic trees to handle minimal model processing. The method is correct and complete and can be guaranteed to terminate given certain mild constraints on the format of database rules. The efficiency of the method is enhanced by the fact that large parts of the search tree are naturally grounded, even for first-order queries and databases. In the case of a grounded yes/no answer, the search tree becomes nongrounded only if processing enters the definite part of the database. For finite propositional databases the method runs in polynomial space. Efficiency may be enhanced by the application of partial compilation.     

Analysis and optimization of active databases

We introduce a new formal semantics for active databases that relies on a transaction rewriting technique. A user-defined transaction, which is viewed here as a sequence of atomic database updates forming a semantic atomic unit, is translated by means of active rules into induced one(s). These transactions embody active rule semantics which can be either immediate or deferred. Rule semantics, confluence, equivalence and optimization are then formally investigated and characterized in a solid framework that naturally extends a known model for relational database transactions.     

An alternative approach to the semantics of disjunctive logic programs and deductive databases

In this paper, we study a new semantics of logic programming and deductive databases. Thepossible model semantics is introduced as a declarative semantics of disjunctive logic programs. The possible model semantics is an alternative theoretical framework to the classical minimal model semantics and provides a flexible inference mechanism for inferring negation in disjunctive logic programs. We also present a proof procedure for the possible model semantics and show that the possible model semantics has an advantage from the computational complexity point of view.This is a revised and extended version of the paper [36] which was presented at the Tenth International Conference on Logic Programming, Budapest, 21–25 June 1993.     

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.     

An Overview of the Rule-Based Object Language

This paper presents an overview of a novel strongly typed deductive object database language, called Rule-based Object Language, which is being developed at the University of Regina. Rule-based Object Language is a uniform language for defining, querying, and manipulating a database, which integrates important features of deductive databases and object databases. It supports object identity, complex objects, classes, class hierarchies, multiple inheritance with overriding and blocking, and schema definition. It also supports structured values such as functor objects and sets, treating them as first class citizens and providing powerful mechanisms for representing both partial and complete information about sets. Important integrity constraints such as domain, referential, functional dependency, multi-valued dependency, and cardinality are built-in in a uniform framework. Rule-based Object Language directly supports non-first normal form relations and is an extension of the pure valued-oriented deductive languages such as Datalog and LDL (without grouping) and subsumes them as special cases. It supports schema, object, fact and rule queries in a uniform framework. It also supports schema, fact and rule updates.     

A Bayesian model for disclosure control in statistical databases

The paper proposes a novel approach for on-line max and min query auditing, in which a Bayesian network addresses disclosures based on probabilistic inferences that can be drawn from released data. In the literature, on-line max and min auditing has been addressed with some restrictive assumptions, primarily that sensitive values must be all distinct and the sensitive field has a uniform distribution. We remove these limitations and propose a model able to: provide a graphical representation of user knowledge; deal with the implicit delivery of information that derives from denying the answer to a query; and capture user background knowledge. Finally, we discuss the results of experiments aimed at assessing the scalability of the approach, in terms of response time and size of the conditional probability table, and the usefulness of the auditor system, in terms of probability to deny.     

A practical mandatory access control model for XML databases

A practical mandatory access control (MAC) model for XML databases is presented in this paper. The label type and label access policy can be defined according to the requirements of different applications. In order to preserve the integrity of data in XML databases, a constraint between a read-access rule and a write-access rule in label access policy is introduced. Rules for label assignment and propagation are presented to alleviate the workload of label assignments. Furthermore, a solution for resolving conflicts in label assignments is proposed. Rules for update-related operations, rules for exceptional privileges of ordinary users and the administrator are also proposed to preserve the security of operations in XML databases. The MAC model, we proposed in this study, has been implemented in an XML database. Test results demonstrated that our approach provides rational and scalable performance.     

Locality-preserving hash functions for general purpose parallel computation

Consider the problem of efficiently simulating the shared-memory parallel random access machine (PRAM) model on massively parallel architectures with physically distributed memory. To prevent network congestion and memory bank contention, it may be advantageous to hash the shared memory address space. The decision on whether or not to use hashing depends on (1) the communication latency in the network and (2) the locality of memory accesses in the algorithm.We relate this decision directly to algorithmic issues by studying the complexity of hashing in the Block PRAM model of Aggarwal, Chandra, and Snir, a shared-memory model of parallel computation which accounts for communication locality. For this model, we exhibit a universal family of hash functions having optimal locality. The complexity of applying these hash functions to the shared address space of the Block PRAM (i.e., by permuting data elements) is asymptotically equivalent to the complexity of performing a square matrix transpose, and this result is best possible for all pairwise independent universal hash families. These complexity bounds provide theoretical evidence that hashing and randomized routing need not destroy communication locality, addressing an open question of Valiant.This work was started when the author was a student at Oxford University, supported by a National Science Foundation Graduate Fellowship and a Rhodes Scholarship. Any opinions, findings, conclusions, or recommendations expressed in this publication are those of the author and do not necessarily reflect the views of the National Science Foundation or the Rhodes Trust.     

A generalization of analytic deduction via labelled deductive systems. Part I: Basic substructural logics

In this series of papers we set out to generalize the notion of classical analytic deduction (i.e., deduction via elimination rules) by combining the methodology of labelled deductive systems (LDS) with the classical systemKE. LDS is a unifying framework for the study of logics and of their interactions. In the LDS approach the basic units of logical derivation are not just formulae butlabelled formulae, where the labels belong to a given labelling algebra. The derivation rules act on the labels as well as on the formulae, according to certain fixed rules of propagation. By virtue of the extra power of the labelling algebras, standard (classical or intuitionistic) proof systems can be extended to cover a much wider territory without modifying their structure. The systemKE is a new tree method for classical analytic deduction based on analytic cut.KE is a refutation system, like analytic tableaux and resolution, but it is essentially more efficient than tableaux and, unlike resolution, does not require any reduction to normal form.We start our investigation with the family of substructural logics. These are logical systems (such as Lambek's calculus, Anderson and Belnap's relevance logic, and Girard's linear logic) which arise from disallowing some or all of the usual structural properties of the notion of logical consequence. This extension of traditional logic yields a subtle analysis of the logical operators which is more in tune with the needs of applications. In this paper we generalize the classicalKE system via the LDS methodology to provide a uniform refutation system for the family of substructural logics.The main features of this generalized method are the following: (a) each logic in the family is associated with a labelling algebra; (b) the tree-expansion rules (for labelled formulae) are the same for all the logics in the family; (c) the difference between one logic and the other is captured by the conditions under which a branch is declared closed; (d) such conditions depend only on the labelling algebra associated with each logic; and (e) classical and intuitionistic negations are characterized uniformly, by means of the same tree-expansion rules, and their difference is reduced to a difference in the labelling algebra used in closing a branch. In this first part we lay the theoretical foundations of our method. In the second part we shall continue our investigation of substructural logics and discuss the algorithmic aspects of our approach.