Grant: Discovery Grants Program - Individual

Relational database systems became the predominant technology for storing, handling, and querying data only after great improvement in the efficiency of query evaluation in such systems. The key factor in this improvement was the introduction and development of a number of query optimization techniques. Despite enormous progress in query processing technology, there is still great need for new optimization techniques. Minimizing query response time has become particularly important in electronic commerce where the users expect almost instantaneous answers to their queries.Query optimizers draw upon many sources of information about the database to optimize queries. Among these sources, they employ semantic characterizations of stored data to reduce the time needed to search for the requested information. In this work we investigate a new type of such characterization which we call order dependency. Order dependencies describe monotonic relationships between database attributes. Such monotonic relationships may exist between taxes and income, age and date, shipping cost and distance. We analyze properties of order dependencies, provide a mechanism for reasoning about them, and show how they can be used to improve query performance. The techniques we develop here have already been shown to provide dramatic performance improvements of some queries. Our goal is to revolutionize the design of the query optimizer to the point where almost any query asked in a database runs faster.