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

Alberto Lerner, Dennis Shasha

Research output: Chapter in Book/Report/Conference proceedingChapter


This chapter introduces a new query language and algebra, called A Query, that supports order from-the ground-up. An order-dependent query is one whose result 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 a stock’s five-price moving-average in a trades 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 instance, has a new “window” mechanism which can sort data in limited parts of a query. Add-ons make order-dependent queries difficult to write and to optimize. This chapter reveals that order can be a natural property of the underlying data model and algebra. New order-related query transformations arise in this setting. Experiment show that this framework-language plus optimization techniques-brings orders-of-magnitude improvement over SQL:1999 systems on many natural order-dependent queries.

Original languageEnglish (US)
Title of host publicationProceedings 2003 VLDB Conference
Subtitle of host publication29th International Conference on Very Large Databases (VLDB)
Number of pages12
ISBN (Electronic)9780127224428
StatePublished - Jan 1 2003

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of 'AQuery: Query Language for Ordered Data, Optimization Techniques, and Experiments'. Together they form a unique fingerprint.

Cite this