A data warehouse stores materialized views of data from one or more sources, with the purpose of efficiently implementing decision-support or OLAP queries. One of the most important decisions in designing a data warehouse is the selection of materialized views to be maintained at the warehouse. The goal is to select an appropriate set of views that minimizes total query response time and the cost of maintaining the selected views, given a limited amount of resource, e.g., materialization time, storage space, etc. In This work, we have developed a theoretical framework for the general problem of selection of views in a data warehouse. We present polynomial-time heuristics for a selection of views to optimize total query response time under a disk-space constraint, for some important special cases of the general data warehouse scenario, viz.: 1) an AND view graph, where each query/view has a unique evaluation, e.g., when a multiple-query optimizer can be used to general a global evaluation plan for the queries, and 2) an OR view graph, in which any view can be computed from any one of its related views, e.g., data cubes. We present proofs showing that the algorithms are guaranteed to provide a solution that is fairly close to (within a constant factor ratio of) the optimal solution. We extend our heuristic to the general AND-OR view graphs. Finally, we address in detail the view-selection problem under the maintenance cost constraint and present provably competitive heuristics.

We consider the problems of containment, equivalence, satisfiability and query-reachability for datalog programs with negation. These problems are important for optimizing datalog programs. We show that both query-reachability and satisfiability are decidable for programs with stratified negation provided that negation is applied only to EDB predicates or that all EDB predicates are unary. In the latter case, we show that equivalence is also decidable. The algorithms we present can also be used to push constraints from a given query to the EDB predicates. In showing our decidability results we describe a powerful tool, the query-tree, which is used for several optimization problems for datalog programs. Finally, we show that satisfiability is undecidable for datalog programs with unary IDB predicates, stratified negation and the interpreted predicate ≠.

We present an efficient protocol for multi-version concurrency control in distributed databases. The protocol creates no more than three versions of any data item, while guaranteeing that: update transactions never interfere with read-only transactions; the version advancement mechanism is completely asynchronous with (both update and read-only) user transactions; and read-only transactions do not acquire locks and do not write control information into the data items being read. This is an improvement over existing multi-versioning schemes for distributed databases, which either require a potentially unlimited number of versions, or require coordination between version advancement and user transactions. Our protocol can be applied in a centralized system also, where the improvement over existing techniques is in reducing the number of versions from four to three. The proposed protocol is valuable in large applications that currently shut off access to the system while managing version advancement manually, but now have a need for automating this process and providing continuous access to the data.

Presents a multiversioning scheme for a distributed system with the workload consisting of read-only transactions and update transactions, (most of) which commute on individual nodes. The scheme introduces a version advancement protocol that is completely asynchronous with user transactions, thus allowing the system to scale to very high transaction rates and frequent version advancements. Moreover, the scheme never creates more than three copies of a data item. Combined with existing techniques to avoid global concurrency control for commuting transactions that execute in a particular version, our multiversioning scheme results in a protocol where no user transaction on a node can be delayed by any activity (either version advancement or another transaction) occurring on another node. Non-commuting transactions are gracefully handled. Our technique is of particular value to distributed recording systems where guaranteeing global serializability is often desirable, but rarely used because of the high performance cost of running distributed transactions. Examples include calls on a telephone network, inventory management in a "point-of-sale" system, operations monitoring systems in automated factories, and medical information management systems.

Materialized views and view maintenance are becoming increasingly important in practice. In order to satisfy different data currency and performance requirements, a number of view maintenance policies have been proposed. Immediate maintenance involves a potential refresh of the view after every update to the deriving tables. When staleness of views can be tolerated, a view may be refreshed periodically or (on-demand) when it is queried. The maintenance policies that are chosen for views have implications on the validity of the results of queries and affect the performance of queries and updates. In this paper, we investigate a number of issues related to supporting multiple views with different maintenance policies.

Data warehouses contain large amounts of information, often collected from a variety of independent sources. Decision-support functions in a warehouse, such as on-line analytical processing (OLAP), involve hundreds of complex aggregate queries over large volumes of data. It is not feasible to compute these queries by scanning the data sets each time. Warehouse applications therefore build a large number of summary tables, or materialized aggregate views, to help them increase the system performance. As changes, most notably new transactional data, are collected at the data sources, all summary tables at the warehouse that depend upon this data need to be updated. Usually, source changes are loaded into the warehouse at regular intervals, usually once a day, in a batch window, and the warehouse is made unavailable for querying while it is updated. Since the number of summary tables that need to be maintained is often large, a critical issue for data warehousing is how to maintain the s...

Materialized views and view maintenance are important for data warehouses, retailing, banking, and billing applications. We consider two related view maintenance problems: 1) how to maintain views after the base tables have already been modified, and 2) how to minimize the time for which the view is inaccessible during maintenance.Typically, a view is maintained immediately, as a part of the transaction that updates the base tables. Immediate maintenance imposes a significant overhead on update transactions that cannot be tolerated in many applications. In contrast, deferred maintenance allows a view to become inconsistent with its definition. A refresh operation is used to reestablish consistency. We present new algorithms to incrementally refresh a view during deferred maintenance. Our algorithms avoid a state bug that has artificially limited techniques previously used for deferred maintenance.Incremental deferred view maintenance requires auxiliary tables that contain information recorded since the last view refresh. We present three scenarios for the use of auxiliary tables and show how these impact per-transaction overhead and view refresh time. Each scenario is described by an invariant that is required to hold in all database states. We then show that, with the proper choice of auxiliary tables, it is possible to lower both per-transaction overhead and view refresh time.

Much recent work has focused on the bottom-up evaluation of Datalog programs [Bancilhon and Ramakrishnan 1988]. One approach, called magic-sets, is based on rewriting a logic program so that bottom-up fixpoint evaluation of the program avoids generation of irrelevant facts [Bancilhon et al. 1986; Beeri and Ramakrishnan 1987; Ramakrishnan 1991]. It was widely believed for some time that the principal application of the magic-sets technique is to restrict computation in recursive queries using equijoin predicates. We extend the magic-sets transformation to use predicates other than equality ( X >10, for example) in restricting computation. The resulting ground magic-sets transformation is an important step in developing an extended magic-sets transformation that has practical utility in “real” relational databases, not only for recursive queries, but for nonrecursive queries as well [Mumick et al. 1990b; Mumick 1991].

To meet the stringent performance requirements of transaction recording systems, much of the recording and query processing functionality, which should preferably be in the database, is actually implemented in the procedural application code, with the attendant difficulties in development, modularization, maintenance, and evolution.To combat this deficiency, we propose a new data model, the chronicle model, which permits the capture, within the data model, Queries over the stored sequence of transaction records, with stringent response time requirements.Of particular interest are summary queries, that access summarization, or aggregation information of past transactional activity.For example, a cellular phone company may want to provide a facility for a summary query that computes the total number of minutes of calls made in the current billing month from a phone number.This query could be executed whenever a cellular phone is turned on, and the result could be displayed on the customer's phone instrument.Another example of a summary query that a customer care agent in the cellular company may want to execute is: What is the total number of minutes of calls made from a given cellular number since the number was assigned to the current customer.These applications can be (and are) implemented using commercially available relational databases.However, the relational model is not suitable to capture and exploit the peculiar characteristics of a transaction recording system.For example, there is no support for answering a summary query over a sequence that is not

We consider a variant of the view maintenance problem: How does one keep a materialized view up-to-date when the view definition itself changes? Can one do better than recomputing the view from the base relations? Traditional view maintenance tries to maintain the materialized view in response to modifications to the base relations; we try to “adapt ” the view in response to changes in the view definition. Such techniques are needed for applications where the user can change queries dynamically and see the changes in the results fast. Data archaeology, data visualization, and dynamic queries are examples of such applications. We consider all possible redefinitions of SQL SELECT-FROM-UHERE-GROUPBY, UNION, and EXCEPT views, and show how these views can be adapted using the old materialization for the cases where it is possible to do so. We identify extra information that can be kept with a materialization to facilitate redefinition. Multiple simultaneous changes to a view can be handled without necessarily materializing intermediate results. We iden-tify guidelines for users and database administrators that can be used to facilitate efficient view adaptation. 1

The problem of determining whether, for every extensional database, a given predicate in a given program has a finite number of derivations is called the universal finiteness problem. The problem of determining whether a given predicate in a given program has a non-empty extension for some extensional database is called the satisfiability problem. We show that the universal finiteness problem can be reduced to the satisfiability problem. Thus all decidability results for satisfiability can be applied to universal finiteness—for example, we can infer that the universal finiteness problem is decidable for Datalog extended with negation on base predicates. The satisfiability problem can be easily reduced to the universal finiteness problem, so that all undecidability results for satisfiability can be applied to universal finiteness. For example we can infer that the universal finiteness problem is undecidable for Datalog extended with stratified negation.

We describe the implementation of the magic-sets transformation in the Starburst extensible relational database system. To our knowledge this is the first implementation of the magic-sets transformation in a relational database system. The Starburst implementation has many novel features that make our implementation especially interesting to database practitioners (in addition to database researchers). (1) We use a cost-based heuristic for determining join orders (sips) before applying magic. (2) We push all equality and non-equality predicates using magic, replacing traditional predicate pushdown optimizations. (3) We apply magic to full SQL with duplicates, aggregation, null values, and subqueries. (4) We integrate magic with other relational optimization techniques. (5) The implementation is extensible.

We consider the problems of equivalence, satisfiability and query-reachability for datalog programs with negation and dense-order constraints. These problems are important for optimizing datalog programs. We show that both query-reachability and satisfiability are decidable for programs with stratified negation provided that negation is applied only to EDB predicates or that all EDB predicates are unary. In the latter case, we show that equivalence is also decidable. The algorithms we present are also used to push constraints from a given query to the EDB predicates. Finally, we show that satisfiability is undecidable for datalog programs with unary IDB predicates, stratified negation and the interpreted predicate ≠

We present incremental evaluation algorithms to compute changes to materialized views in relational and deductive database systems, in response to changes (insertions, deletions, and updates) to the relations. The view definitions can be in SQL or Datalog, and may use UNION, negation, aggregation (e.g. SUM, MIN), linear recursion, and general recursion.We first present a counting algorithm that tracks the number of alternative derivations (counts) for each derived tuple in a view. The algorithm works with both set and duplicate semantics. We present the algorithm for nonrecursive views (with negation and aggregation), and show that the count for a tuple can be computed at little or no cost above the cost of deriving the tuple. The algorithm is optimal in that it computes exactly those view tuples that are inserted or deleted. Note that we store only the number of derivations, not the derivations themselves.We then present the Delete and Rederive algorithm, DRed, for incremental maintenance of recursive views (negation and aggregation are permitted). The algorithm works by first deleting a superset of the tuples that need to be deleted, and then rederiving some of them. The algorithm can also be used when the view definition is itself altered.

this paper we will write database queries in datalog [Ull89]. Datalog is the language of horn clause logic rules, written as "if-then" rules. A datalog rule is required to be range-restricted: it must define a finite relation for the predicate in the head of the rule. In this paper we will concentrate on nonrecursive queries. Mumick [Mum91] shows that nonrecursive datalog programs can be expressed in SQL using views, and that SQL queries can be expressed in datalog extended with duplicates and grouping with aggregation. Thus, the algorithms developed in this paper can be mapped to relational database systems having SQL as their query language. We will use dependency graphs to represent the dependence between predicates in a datalog program.

We study the optimization of a useful subclass of linear recursive queries.In addition to the general purpose magic-sets transformation, special optimization techniques, such as the right-linear and context right-linear

Much recent work has focussed on the bottom-up evaluation of Datalog programs. One approach, called Magic-Sets, is based on rewriting a logic program so that bottom-up fixpoint evaluation of the program avoids generation of irrelevant facts ([BMSU86, BR87, Ram88]). It is widely believed that the principal application of the Magic-Sets technique is to restrict computation in recursive queries using equijoin predicates. We extend the Magic-Set transformation to use predicates other than equality (X > 10, for example). This Extended Magic-Set technique has practical utility in “real” relational databases, not only for recursive queries, but for non-recursive queries as well; in ([MFPR90]) we use the results in this paper and those in [MPR89] to define a magic-set transformation for relational databases supporting SQL and its extensions, going on to describe an implementation of magic in Starburst ([HFLP89]). We also give preliminary performance measurements.

We define the magic-sets transformation for traditional relational systems (with duplicates, aggregation and grouping), as well as for relational systems extended with recursion. We compare the magic-sets rewriting to traditional optimization techniques for nonrecursive queries, and use performance experiments to argue that the magic-sets transformation is often a better optimization technique.