@inproceedings{acfba23c839141c1a8d35bb4a80d9837,
title = "AQuery: Query language for ordered data, optimization techniques, and experiments",
abstract = "An order-dependent query is one whose result (interpreted as a multiset) 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 fiveprice 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. In this paper we show that order can be a natural property of the underlying data model and algebra. We introduce a new query language and algebra, called AQuery, that supports order from-theground-up. New order-related query transformations arise in this setting. We show by experiment that this framework - language plus optimization techniques - brings orders-ofmagnitude improvement over SQL:1999 systems on many natural order-dependent queries.",
author = "Alberto Lerner and Dennis Shasha",
year = "2003",
language = "English (US)",
series = "Proceedings - 29th International Conference on Very Large Data Bases, VLDB 2003",
publisher = "Morgan Kaufmann",
pages = "345--356",
editor = "Selinger, {Patricia G.} and Carey, {Michael J.} and Freytag, {Johann Christoph} and Serge Abiteboul and Lockemann, {Peter C.} and Andreas Heuer",
booktitle = "Proceedings - 29th International Conference on Very Large Data Bases, VLDB 2003",
note = "29th International Conference on Very Large Data Bases, VLDB 2003 ; Conference date: 09-09-2003 Through 12-09-2003",
}