This paper describes the [Lscr ][Dscr ][Lscr ]++ system and the research advances that have enabled its design and development. We begin by discussing the new nonmonotonic and nondeterministic constructs that extend the functionality of the [Lscr ][Dscr ][Lscr ]++ language, while preserving its model-theoretic and fixpoint semantics. Then, we describe the execution model and the open architecture designed to support these new constructs and to facilitate the integration with existing DBMSs and applications. Finally, we describe the lessons learned by using [Lscr ][Dscr ][Lscr ]++ on various tested applications, such as middleware and datamining.

Association-rule mining has proved a highly successful technique for extracting useful information from very large databases. This success is attributed not only to the appropriateness of the objectives, but to the fact that a number of new query-optimization ideas, such as the “a-priori” trick, make association-rule mining run much faster than might be expected. In this paper we see that the same tricks can be extended to a much more general context, allowing efficient mining of very large databases for many different kinds of patterns. The general idea, called “query flocks,” is a generate-and-test model for data-mining problems. We show how the idea can be used either in a general-purpose mining system or in a next generation of conventional query optimizers.

We consider the problem of analyzing market-basket data and present several important contributions. First, we present a new algorithm for finding large itemsets which uses fewer passes over the data than classic algorithms, and yet uses fewer candidate itemsets than methods based on sampling. We investigate the idea of item reordering, which can improve the low-level efficiency of the algorithm. Second, we present a new way of generating "implication rules," which are normalized based on both the antecedent and the consequent and are truly implications (not simply a measure of co-occurrence), and we show how they produce more intuitive results than other methods. Finally, we show how different characteristics of real data, as opposed to synthetic data, can dramatically affect the performance of the system and the form of the results. 1 Introduction Within the area of data mining, the problem of deriving associations from data has recently received a great deal of attention. The prob...

The problem of mapping the parallel bottom up execution of Datalog programs to an interconnected network of processors is studied. The parallelization is achieved by using hash functions that partition the set of instantiations for the rules. We first examine this problem in an environment where the number of processors and the interconnection topology is known, and communication between program segments residing at non-adjacent processors is not permitted. An algorithm is presented that decides whether a given Datalog program can be mapped onto such an architecture. We then relax the constraint on the architecture by allowing program segments residing at non-adjacent processors to communicate, A theory of approximate mappings is developed, and an algorithm to obtain the closest approximate mapping of a given Datalog program onto a given architecture is presented.>

has been a topic of extensive research over the last years.A number of prototype systems that implement some of the theoretical results are in various stages of development, Despite this intense activity not enough has been done so far to identify the areas of application in which this emerging technology could be most fruitfully deployed.This paper surveys some of these potential areas, comments on our experience, and suggests some directions for further research that have emerged in the course of our attempts to use this technology.

This paper presents several complementary methods for the parallel, bottom-up evaluation of Datalog queries. We introduce the notion of a discriminating predicate, based on hash functions, that partitions the computation between the processors in order to achieve parallelism. A parallelization scheme with the property of non-redundant computation (no duplication of computation by processors) is then studied in detail. The mapping of Datalog programs onto a network of processors, such that the results is a non-redundant computation, is also studied. The methods reported in this paper clearly demonstrate the trade-offs between redundancy and interprocessor-communication for this class of problems.

The logic data language (LDL) system provides a declarative logic-based language and integrates relational database and logic programming technologies so as to support advanced data and knowledge-based applications. A comprehensive overview of the system and a description of LDL language and the compilation techniques employed to translate LDL queries into target query execution plans on the stored data are presented. The architecture and runtime environment of the system and the optimization techniques employed in order to improve the performance and assure the safety of the compiled queries are given. The experience gained so far with the system and application areas where the LDL approach appears to be particularly effective are discussed.>

We propose compilation methods for supporting set terms in Horn clause programs, without using general-purpose set matching algorithms, which tend to run in times exponential in the size of the participating sets Instead, we take the approach of formulating specialized computation plans that, by taking advantage of information available in the given rules, limit the number of alternatives explored. Our strategy is to employ compile time rewriting techniques and to transform the problem into an “ordinary” Horn clause compilation problem, with minimal additional overhead. The execution cost of the rewritten rules is substantially lower than that of the original rules and the additional cost of compilation can thus be amortized over many executions

In this paper we extend LDL, a Logic Based Database Language, to include finite sets and negation. The new language is called LDL1. We define the notion of a model and show that a negation-free program need not have a model, and that it may have more than one minimal model. We impose syntactic restriction in order to define a deterministic language. These restrictions allow only layered (stratified) programs. We prove that for any program satisfying the syntactic restrictions of layering, there is a minimal model, and that this model can be constructed in a bottom-up fashion. Extensions to the basic grouping mechanism are proposed. We show that these extensions can be translated into equivalent LDL1 programs. Finally, we show how the technique of magic sets can be extended to translate LDL1 programs into equivalent programs which can often be executed more efficiently

This paper presents a simple approach for extending the relational system INGRES into one supporting a semantic data model it describe a DBMS consisting of (i) a user-friendly front-end, supporting the GEM semantic data model and query language under the UNIX time-sharing system, and (ii) a dedicated back-end processor providing efficient support for database transactions, concurrency control and recovery GEM extends the relational model to support the notions of entities with surrogates, the relationships of aggregation and generalization, null values and set-valued attributes, and provides simple extensions of QUEL to handle these new constructs in this proposed implementation of GEM, the relational database processor IDM 500 by Britton-Lee is used as the back-end machine

In this paper we address the performance issues that arise as a result of the two level scheduling in a database/operating system. At the upper (database) level transactions are logically scheduled so as to maintain the database integrity. At the lower (operating system) level physical disk requests are scheduled.We consider the performance problems that result from the interplay between these two levels of scheduling. Our model assumes the existence of a dictionary that must be consulted prior to the execution of a transaction. We derive the optimal disk placement of this dictionary and our results show that the waiting time for dictionary look-up is the critical component in the transaction response-time for a wide range of transaction sizes. To alleviate this problem we suggest alternative approaches to dictionary placement in such systems.

B-trees are a commonly used data structure for indexed access to files and databases. Among the desirable properties of B-trees is the fact that they are dynamically rebalanced after each insertion and deletion operation and therefore need not be reorganized as other static access structures e.g., ISAM. Despite the fact that B-trees are dynamically balanced we demonstrate that operational conditions exist under which it pays off to explicitly reorganize B-trees. The rationale being that by explicit reorganization we defer the event of root splitting and hence reduce the cost of subsequent retrieval requests which are the dominant operations. We present a reorganization algorithm that allows control over storage utilization and discuss the circumstances under which it should be applied. We present simulation results that support our contention that reorganization is indeed economically feasible and we conclude with some suggestions for further work in this area.