Boolean expression simplification is a well-known problem in the history of computer science. The problem of determining prime implicates from an arbitrary Boolean expression has been mostly studied in the contexts of hardware design and automated reasoning. While many of the same principles can be applied to the simplification of search conditions in ANSI SQL queries, the richness of its language and SQL's three-valued logic present a number of challenges. We propose a modified version of a matrix-based normalization algorithm suitable for normalizing SQL search conditions in constrained-memory environments. In particular we describe a set of tradeoffs that enable our algorithm to discover a useful set of implicates without requiring a complete conversion of the input condition to a normal form, preventing a combinatorial explosion in the number of terms.

In today's computing environment, database technology can be found on virtually any device, from traditional mainframes to cellular phones. Sophisticated applications, whether enterprise information portals or sales force automation systems, can 'push' much of their complexity into the database itself; indeed, this represents one of the main benefits of database technology. The challenge, however, is to support these complex applications, and the queries they generate, on small computing devices. We describe a deterministic join enumeration algorithm for left-deep processing trees, currently implemented in Sybase SQL Anywhere, a small-footprint relational database system whose target market ranges from workgroup servers to small hand-held devices. The algorithm is able to efficiently optimize complex queries with high join degree by employing a novel approach to cost based pruning of the search space. We present some empirical performance results on several production queries obtained from SQL Anywhere customers, and show that our approach requires significantly less memory than other deterministic join enumeration algorithms which have been described in the literature.

Consider an SQL query that specifies duplicate elimination via a DISTINCT clause. Because duplicate elimination often requires an expensive sort of the query result, it is often worthwhile to identify unnecessary DISTINCT clauses and avoid the sort altogether. We prove a necessary and sufficient condition for deciding if a query requires duplicate elimination. The condition exploits knowledge about keys, table constraints, and query predicates. Because the condition cannot always be tested efficiently, we offer a practical algorithm that tests a simpler, sufficient condition. We consider applications of this condition for various types of queries, and show that we can exploit this condition in both relational and nonregulation database systems.>