Search

Multiple issues with SQL's handling of nulls have been well documented. Having efficiency as its main goal, SQL disregards the standard notion of correctness on incomplete databases -- certain answers -- due to its high complexity. As a result, the evaluation of SQL queries on databases with nulls may produce answers that are just plain wrong. However, SQL evaluation can be modified, at least for relational algebra queries, to approximate certain answers, i.e., return only correct answers. We examine recently proposed approximation schemes for certain answers and analyze their complexity, both theoretical bounds and real-life behavior

Take a database conference paper and search for "in the real world" in it; chances are high you will find it. Of course what is real depends on one's perspective: for a pure theory paper it could be what one saw in a systems paper, for a systems paper it could be an issue that implementors of DBMSs had to deal with, and for the latter it may be what the customers need. But to sharpen our research tools, it helps tremendously to understand that the real "real world" is, and adjust our (sometimes very elaborate) techniques to address problems that actually occur. A nice example of this is analyzing the computational complexity of database queries. Database theory has developed an arsenal of tools for this. We know that for many classes of queries, the complexity is roughly kDkO(kQk) for a database D and a query Q, where k k means size. Thus, much research went into the detailed analysis of the structure of queries that removes kQk from the exponent and replaces it by a small fixed constant. We have a very good theoretical understanding of such classes, but we know much less about their relationship with queries that real-world users write.

The notion of variable independence was introduced by Chomicki, Goldin, and Kuper in their PODS'96 paper as a means of adding a limited form of aggregation to constraint query languages while retaining the closure property. Later, Grumbach, Rigoux and Segoufin showed in their ICDT'99 paper that variable independence and a related notion of orthographic dimension are useful tools for optimizing constraint queries. However, several results in those papers are incorrect as stated. As the notions of variable independence and orthographic dimension appear to be important for implementing constraint database prototypes, I explain in this short note the problems with the above mentioned papers and outline a solution for aggregate closure.

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.