We provide a logic-based semantics for active database rules under the immediately-after, tuple-level activation policy of SQL3. This result allows us to characterize and analyze the behavior of complex rule systems using the declarative framework of stable models, and to lay the theoretical foundation for a very desirable integration of active databases and deductive databases.
The problem of finding effective logic-based formalizations for problems involving actions remains one of the main application challenges of non-monotonic knowledge representation. In this paper, we show that complex planning strategies find natural logic-based formulations and efficient implementations in the framework of deductive database languages. We begin by modeling classical STRIPS-like totally ordered plans by means of Datalog_{1S} programs, and show that these programs have a stable model semantics that is also amenable to efficient computation. We then show that the proposed approach is quite expressive and flexible, and can also model partially ordered plans, which are abstract plans whereby each plan stands for a whole class of totally ordered plans. This results in a reduction of the search space and a subsequent improvement in efficiency.
While non-determinism has long been established as a key concept in logic pro-gramming, its importance in the context of deductive databases was recognized only recently. This paper provides an overview of recent results on this topic with the aim of providing an introduction to the theory and practice of non-determinism in deductive databases. In particular we (i) recall the main results linking non-deterministic constructs in database languages to the theory of data complexity and the expressibility hierarchy of query languages; (ii) provide a reasoned introduction to effective programming with non-deterministic constructs; (iii) compare the usage of non-deterministic constructs in languages such as LDL++ to that of traditional logic programming languages; (iv) discuss the link between the semantics of logic programs with non-deterministic constructs and the stable-model semantics of logic programs with negation.
An important feature of many advanced active database prototypes is support for rules triggered by complex patterns of events. Their composite event languages provide powerful primitives for event-based temporal reasoning. In fact, with one important exception, their expressive power matches and surpasses that of sophisticated languages offered by Time Series Management Systems (TSMS), which have been extensively used for temporal data analysis and knowledge discovery. This exception pertains to temporal aggregation, for which, current active database systems offer only minimal support, if any. In this paper, we introduce the language TREPL, which addresses this problem. The TREPL prototype, under development at UCLA, offers primitives for temporal aggregation that exceed the capabilities of state-of-the-art composite event languages, and are comparable to those of TSMS languages. TREPL also demonstrates a rigorous and general approach to the definition of composite event language semantics. The meaning of a TREPL rule is formally defined by mapping it into a set of $Datalog_{1S}$ rules, whose logic-based semantics characterizes the behavior of the original rule. This approach handles naturally temporal aggregates, including user-defined ones, and is also applicable to other composite event languages, such as ODE, Snoop and SAMOS.
A major thrust of current research in active databases focuses on allowing complex patterns of temporal events to serve as preconditions for rule triggering. Currently, there is no common formalism for specifying the semantics of composite event languages. Different systems have used an assortment of different techniques, including Finite State Automata, Petri Nets and Event Graphs. In this paper, we propose a unifying approach, based on a syntax-directed translation of composite event expressions into $Datalog_{1S}$ rules, whose formal semantics defines the meaning of the original expressions. We demonstrate our method by providing a formal specification of the Event Pattern Language (EPL) developed at UCLA. This method overcomes problems and limitations affecting previous approaches and is applicable to other languages such as ODE, SNOOP and SAMOS---thus, allowing a more direct comparison across different systems.
Stable models have been first introduced in the domain of total interpretations ({\em T-stable} models), where the existence of multiple T-stable models for the same program provides a powerful mechanism to express non-determinism. Stable models have been later extended to the domain of partial interpretations ({\em P-stable} models). In this paper, we show that the presence of multiple P-stable models need not be a direct manifestation of non-determinism, for it can be instead an expression of assorted degrees of undefinedness. To separate the two factors, non-determinism and undefinedness, this paper introduces the notion of {\em deterministic} stable models and {\em strictly non-deterministic} ones. Deterministic stable models form an interesting family, having a lattice structure where the well-founded model serves as the bottom; the top of the lattice, the {\em maximum deterministic} stable model, resolves differences between any two P-stable models in the family. On the other hand, every two models in a family of strictly non-deterministic P-stable models have unreconcilable differences, so that one must be chosen to the exclusion of the other. One such strictly non-deterministic family is constituted by the T-stable models. The paper characterizes two other interesting families: the maximal stable ({\em M-stable}) models (\ie those not contained in any other P-stable model), and the least-undefined stable ({\em L-stable}) models (\ie maximal stable models with the minimal set of undefined atoms). The paper studies the properties of models in these classes, and characterizes the computational complexity of finding stable models for the various types of Datalog programs.
The expanding role of intelligent information systems and a new wave of database applications are creating a strong demand for database-centered programming environments. In response to this demand, deductive database systems support complex queries and reasoning, rule-based programming and the integration of databases with knowledge bases. The LDL and LDL++ systems are the two prototypes produced by a leading research project in this area. This paper focuses on the second system that was shaped by the experience gained with its predecessor and recent research advances in the field. The {\LDL}++ system features a better integration with external databases, a new execution model, and various language extensions to support non-deterministic and non-monotonic programming.
We provide a logic-based semantics for the active database under SQL3 immediately-after, tuple-level activation policy. This result allows us to characterize and analyze the behavior of complex rule systems using the declarative framework of stable models, and lays the theoretical foundation for a powerful integration of active and deductive database technologies.