Programming with logical queries, bulk updates, and hypotheticalreasoning

The paper presents a language of update programs that integrates logical queries, bulk updates and hypothetical reasoning in a seamless manner. There is no syntactic or semantic distinction between queries and updates. Update programs extend logic programs with negation in both syntax and semantics. They allow bulk updates in which an arbitrary update is applied simultaneously for all answers of an arbitrary query. Hypothetical reasoning is naturally supported by testing the success or failure of an update. We describe an alternating fixpoint semantics of update programs and show that it can express all nondeterministic database transformations     

Efficient recursive aggregation and negation in deductive databases

We present an efficient evaluation technique for modularly stratified deductive database programs for which the local strata level mappings are known at compile time. We present an important subclass of these programs (called EMS-programs) in which one can easily express problems, such as shortest distance, company ownership, bill of materials, and preferential vote counting. Programs written in this style have an easy-to-understand semantics and can be efficiently computed. Another important virtue of these programs is that their modular-stratification properties are independent of the extensional database     

Static analysis of logical languages with deferred update semantics

Static analysis of declarative languages deals with the detection, at compile time, of program properties that can be used to better understand the program semantics and to improve the efficiency of program evaluation. In logical update languages, an interesting problem is the detection of conflicting updates, inserting and deleting the same fact, for transactions based on set-oriented updates and active rules. In this paper, we investigate this topic in the context of the U-Datalog language, a set-oriented update language for deductive databases, based on a deferred semantics. We first formally define relevant properties of U-Datalog programs, mainly related to update conflicts. Then, we prove that the defined properties are decidable and we propose an algorithm to detect such conditions. Finally, we show how the proposed techniques can be applied to other logical update languages. Our results are based on the concept of labeling and query-tree.     

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     

Well-founded semantics and stratification for ordered logic programs

This paper present an extension of traditional logic programming, called ordered logic (OL) programming, to support classical negation as well as constructs from the object-oriented paradigm. In particular, such an extension allows to cope with the notions of object, multiple inheritance and non-monotonic reasoning. The contribution of the work is mainly twofold. First, a rich wellfounded semantics for ordered logic programs is defined. Second, an efficient method for the well-founded model computation of a meaningful class of ordered logic programs, called stratified programs, is provided.     

Updating Recursive XML Views of Relations

This paper investigates the view update problem for XML views published from relational data.We consider XML views defined in terms of mappings directed by possibly reeursive DTDs compressed into DAGs and stored in relations. We provide new techniques to efficiently support XML view updates specified in terms of XPath expressions with recursion and complex filters.The interaction between XPath recursion and DAG compression of XML views makes the analysis of the XML view update problem rather intriguing.Furthermore,many issues are still open even for relational view updates, and need to be explored.In response to these,on the XML side,we revise the notion of side effects and update semantics based on the semantics of XML views,and present efficient algorithms to translate XML updates to relational view updates. On the relational side,we propose a mild condition on SPJ views,and show that under this condition the analysis of deletions on relational views becomes PTIME while the insertion analysis is NP-complete.We develop an efficient algorithm to process relational view deletions,and a heuristic algorithm to handle view insertions.Finally,we present an experimental study to verify the effectiveness of our techniques.     

Primitives for schema updates in an object-oriented database system: a proposal

Updating the schema is an important facility for object-oriented databases. However, updates should not result in inconsistencies either in the schema or in the database. We propose a classification of basic schema updates and define a set of parametrized primitives to perform schema updates which the designer will use to define his/her own update semantics.     

Towards an efficient evaluation of recursive aggregates in deductive databases

This paper is devoted to the evaluation of aggregates (avg, sum,…) in deductive databases. Aggregates have proved to be a necessary modeling tool for a wide range of applications in non-deductive relational databases. They also appear to be important in connection with recursive rules, as shown by thebill of materials example. Several recent papers have studied the problem of semantics for aggregate programs. As in these papers, we distinguish between the classes of stratified (non-recursive) and recursive aggregate programs. For each of these two classes, the declarative semantics is recalled and an efficient evaluation algorithm is presented. The semantics and computation of aggregate programs in the recursive case are more complex: we rely on the notion of graph traversal to motivate the semantics and the evaluation method proposed. The algorithms presented here are integrated in the QSQ framework. Our work extends the recent work on aggregates by proposing an efficient algorithm in the recursive case. Recursive aggregates have been implemented in the EKS-V1 system.     

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.     

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 evaluation of the program.From the database point of view,the procedural semantics of the program is equally important.This paper focuses on the study of the bottom-up evaluation of the WFM semantics of datalog‘ programs.To compute the WFM,first,the stability 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 defined.Then,it is shown that for any datalog‘ program the oscillating fixpoint model is identical to its WFM.So,the oscillating fixpoint model can be viewed as an alternative (constructive) definition of WFM.The underlying operation (or transformation) for reaching the oscillating fixpoint provides a potential of bottom-up evaluation.For the sake of computational feasibility,the strongly range-restricted program is considered,and an algorithm used to compute the oscillating fixpoint is described.     

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.     

Semantics and complexity of recursive aggregates in answer set programming

The addition of aggregates has been one of the most relevant enhancements to the language of answer set programming (ASP). They strengthen the modelling power of ASP in terms of natural and concise problem representations. Previous semantic definitions typically agree in the case of non-recursive aggregates, but the picture is less clear for aggregates involved in recursion. Some proposals explicitly avoid recursive aggregates, most others differ, and many of them do not satisfy desirable criteria, such as minimality or coincidence with answer sets in the aggregate-free case.In this paper we define a semantics for programs with arbitrary aggregates (including monotone, antimonotone, and nonmonotone aggregates) in the full ASP language allowing also for disjunction in the head (disjunctive logic programming — DLP). This semantics is a genuine generalization of the answer set semantics for DLP, it is defined by a natural variant of the Gelfond–Lifschitz transformation, and treats aggregate and non-aggregate literals in a uniform way. This novel transformation is interesting per se also in the aggregate-free case, since it is simpler than the original transformation and does not need to differentiate between positive and negative literals. We prove that our semantics guarantees the minimality (and therefore the incomparability) of answer sets, and we demonstrate that it coincides with the standard answer set semantics on aggregate-free programs.Moreover, we carry out an in-depth study of the computational complexity of the language. The analysis pays particular attention to the impact of syntactical restrictions on programs in the form of limited use of aggregates, disjunction, and negation. While the addition of aggregates does not affect the complexity of the full DLP language, it turns out that their presence does increase the complexity of normal (i.e., non-disjunctive) ASP programs up to the second level of the polynomial hierarchy. However, we show that there are large classes of aggregates the addition of which does not cause any complexity gap even for normal programs, including the fragment allowing for arbitrary monotone, arbitrary antimonotone, and stratified (i.e., non-recursive) nonmonotone aggregates. The analysis provides some useful indications on the possibility to implement aggregates in existing reasoning engines.     

A functional approach to database updates

PFL is a functional database language in which functions are defined equationally and bulk data is stored using a special class of functions called selectors. It is a lazy language, supports higher-order functions, has a strong polymorphic type inference system, and allows new user-defined data types and values to be declared. All functions, types and values persist in a database. Functions can be written which update all aspects of the database: by adding data to selectors, by defining new equations, and by introducing new data types and values. PFL is “semi-referentially transparent”, in the sense that whilst updates are referentially opaque and are executed destructively, all evaluation is referentially transparent. Similarly, type checking is “semi-static” in the sense that whilst updates are dynamically type checked at run time, expressions are type checked before they are evaluated and no type errors can occur during their evaluation.

In this paper we examine the expressiveness of PFL with respect to updates, and illustrate the language by developing a number of general purpose update functions, including functions for restructuring selectors, for memoisation, and for generating unique system identifiers. We also provide a translation mechanism between Datalog programs and equations, and show how different Datalog evaluation strategies can be supported.     

A Deductive Database Approach to A.I. Planning

In this paper, we show that the classical A.I. planning problem can be modelled using simple database constructs with logic-based semantics. The approach is similar to that used to model updates and nondeterminism in active database rules. We begin by showing that planning problems can be automatically converted to Datalog_1S programs with nondeterministic choice constructs, for which we provide a formal semantics using the concept of stable models. The resulting programs are characterized by a syntactic structure (XY-stratification) that makes them amenable to efficient implementation using compilation and fixpoint computation techniques developed for deductive database systems. We first develop the approach for sequential plans, and then we illustrate its flexibility and expressiveness by formalizing a model for parallel plans, where several actions can be executed simultaneously. The characterization of parallel plans as partially ordered plans allows us to develop (parallel) versions of partially ordered plans that can often be executed faster than the original partially ordered plans.     

DLEJena: A practical forward-chaining OWL 2 RL reasoner combining Jena and Pellet

This paper describes DLEJena, a practical reasoner for the OWL 2 RL profile that combines the forward-chaining rule engine of Jena and the Pellet DL reasoner. This combination is based on rule templates, instantiating at run-time a set of ABox OWL 2 RL/RDF Jena rules dedicated to a particular TBox that is handled by Pellet. The goal of DLEJena is to handle efficiently, through instantiated rules, the OWL 2 RL ontologies under direct semantics, where classes and properties cannot be at the same time individuals. The TBox semantics are treated by Pellet, reusing in that way efficient and sophisticated TBox DL reasoning algorithms. The experimental evaluation shows that DLEJena achieves more scalable ABox reasoning than the direct implementation of the OWL 2 RL/RDF rule set in the Jena’s production rule engine, which is the main target of the system. DLEJena can be also used as a generic framework for applying an arbitrary number of entailments beyond the OWL 2 RL profile.     

Theorem Proving Techniques for View Deletion in Databases

In this paper, we show how techniques from first-order theorem proving can be used for efficient deductive database updates. The key idea is to transform the given database, together with the update request, into a (disjunctive) logic program and to apply the hyper-tableau calculus (Baumgartner et al. 1996) to solve the original update problem. The resulting algorithm has the following properties: it works goal-directed (i.e. the search is driven by the update request), it is rational in the sense that it satisfies certain rationality postulates stemming from philosophical works on belief dynamics, and, unlike comparable approaches, it is of polynomial space complexity. To obtain soundness and completeness results, the hyper-tableau calculus is slightly modified for minimal model reasoning. Besides a direct proof we give an alternate proof which gives insights into the relation to previous approaches. As a by-product we thereby derive a soundness and completeness result of hyper-tableaux for computing minimal abductive explanations.     

A Fixpoint Semantics for Stratified Databases

Przmusinski extended the notion of stratified logic programs,developed by Apt,Blair and Walker,and by van Gelder,to stratified databases that allow both negative premises and disjunctive consequents.However,he did not provide a fixpoint theory for such class of databases.On the other hand,although a fixpoint semantics has been developed by Minker and Rajasekar for non-Horn logic programs,it is tantamount to traditional minimal model semantics which is not sufficient to capture the intended meaning of negation in the premises of clauses in stratified databases.In this paper,a fixpoint approach to stratified databases is developed,which corresponds with the perfect model semantics.Moreover,algorithms are proposed for computing the set of perfect models of a stratified database.     

Hyperlog: a graph-based system for database browsing, querying, andupdate

Hyperlog is a declarative, graph based language that supports database querying and update. It visualizes schema information, data, and query output as sets of nested graphs, which can be stored, browsed, and queried in a uniform way. Thus, the user need only be familiar with a very small set of syntactic constructs. Hyperlog queries consist of a set of graphs that are matched against the database. Database updates are supported by means of programs consisting of a set of rules. The paper discusses the formulation, evaluation, expressiveness, and optimization of Hyperlog queries and programs. We also describe a prototype implementation of the language and we compare and contrast our approach with work in a number of related areas, including visual database languages, graph based data models, database update languages, and production rule systems     

Revision programming

In this paper we introduce revision programming — a logic-based framework for describing constraints on databases and providing a computational mechanism to enforce them. Revision programming captures those constraints that can be stated in terms of the membership (presence or absence) of items (records) in a database. Each such constraint is represented by a revision rule ← ₁,…,_k, where and all ga_i are of the form in(a) and out(b). Collections of revision rules form revision programs. Similarly as logic programs, revision programs admit both declarative and imperative (procedural) interpretations. In our paper, we introduce a semantics that reflects both interpretations. Given a revision program, this semantics assigns to any database B a collection (possibly empty) of P-justified revisions of B. The paper contains a thorough study of revision programming. We exhibit several fundamental properties of revision programming. We study the relationship of revision programming to logic programming. We investigate complexity of reasoning with revision programs as well as algorithms to compute P-justified revisions. Most importantly from the practical database perspective, we identify two classes of revision programs, safe and stratified, with a desirable property that they determine for each initial database a unique revision.