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