Title: AQuery: Query Language for Ordered Data, Optimization Techniques, and Experiments 

(NYU-CS-TR836)

Authors: Alberto Lerner and Dennis Shasha 

Abstract:
An order-dependent query is one whose result (interpreted as a multi-set)
changes if the order of the input records is changed. In a stock-quotes
database, for instance, retrieving all quotes concerning a given stock for
a given day does not depend on order, because the collection of quotes
does not depend on order. By contrast, finding the five price moving av-
erage in a trade table gives a result that depends on the order of the
table. Query languages based on the relational data model can handle order-
dependent queries only through add-ons. SQL:1999, for example, permits the
use of a data ordering mechanism called a "window" in limited parts of a
query. As a result, order-dependent queries become difficult to write in
those languages and optimization techniques for these features, applied as
pre- or post-enumerating phases, are generally crude. The goal of this
paper is to show that when order is a property of the underlying data model
and algebra, writing order-dependent queries in a language can be as natural
as is their optimization. We introduce AQuery, an SQL-like query language
and algebra that has from-the-ground-up support for order. We also present
a framework for optimization of the order-dependent queries catagories it
expresses. The framework is able to take advantage of the large body of
query transformations on relational systems while incorporating new ones
described here. We show by experiment that the resulting system is orders
of magnitude faster than current SQL:1999 systems on many natural order-
dependent queries.