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