Order Dependencies in Database Systems

只有在关系数据库系统的查询评估效率得到极大提高之后，关系数据库系统才成为存储、处理和查询数据的主要技术。这种改进的关键因素是引入和开发了许多查询优化技术。尽管查询处理技术取得了巨大的进步，但仍然需要新的优化技术。最小化查询响应时间在电子商务中变得尤为重要，因为用户希望查询几乎可以即时得到回答。****查询优化器利用关于数据库的许多信息源来优化查询。在这些数据源中，它们使用存储数据的语义特征来减少搜索所请求信息所需的时间。在这项工作中，我们研究了一种新的表征，我们称之为顺序依赖。顺序依赖描述了数据库属性之间的单调关系。这种单调关系可能存在于税收和收入、年龄和日期、运费和距离之间。我们分析了顺序依赖的属性，提供了一种对它们进行推理的机制，并展示了如何使用它们来提高查询性能。我们在这里开发的技术已经被证明为某些查询提供了显著的性能改进。我们的目标是彻底改变查询优化器的设计，使数据库中几乎所有查询都运行得更快。**************

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. **************