AQuery: a simple, efficient extension to SQL for ordered data As John McCarthy once pointed out when asked why Lisp was based on lists rather than sets, any query expressible on a multiset of records can be expressed on an array of records. The reverse doesn't hold. In fact, when order-dependent queries are formulated against a (multi-) set, they become intricate at best. For instance, the query to find the average pair-wise differences between time-consecutive values of a column in SQL:1999 requires a join, but the operation could be written trivially as a single loop on an array. In this talk, we - Show motivating order-dependent queries coming from domains as diverse as road traffic management, finances, biology, and network management. - Illustrate several flavors (categories) of order-dependent queries. - Describe AQuery (a syntactically simple extension to SQL) as a natural way to express these queries. - Define the underlying data model that treats order as a property of the model and algebra. In this model, data is semantically organized in a structure called an "arrable" (array table). - Discuss equivalences and transformation rules over the algebra for purposes of optimization. - Compare AQuery's performance to various implementations of SQL:1999 on the the queries discussed. (Joint work with Alberto Lerner)