AQuery: Query language for ordered data, optimization techniques, and experiments

Alberto Lerner, Dennis Shasha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationProceedings - 29th International Conference on Very Large Data Bases, VLDB 2003
EditorsPatricia G. Selinger, Michael J. Carey, Johann Christoph Freytag, Serge Abiteboul, Peter C. Lockemann, Andreas Heuer
PublisherMorgan Kaufmann
Pages345-356
Number of pages12
ISBN (Electronic)0127224424, 9780127224428
StatePublished - 2003
Event29th International Conference on Very Large Data Bases, VLDB 2003 - Berlin, Germany
Duration: Sep 9 2003Sep 12 2003

Publication series

NameProceedings - 29th International Conference on Very Large Data Bases, VLDB 2003

Other

Other29th International Conference on Very Large Data Bases, VLDB 2003
CountryGermany
CityBerlin
Period9/9/039/12/03

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Information Systems and Management
  • Computer Science Applications
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'AQuery: Query language for ordered data, optimization techniques, and experiments'. Together they form a unique fingerprint.

Cite this