Building a Database System for Order

Dennis Shasha
Courant Institute, New York University

Friday, April 12, 2002, 4:00 PM
Volen 101, Brandeis University

(preceeded by a wine and cheese reception at 3:00 pm)

Abstract:

Any query expressible on a set of records can be expressed on an array of records. The reverse doesn't hold: moving averages, autocorrelations, the computation of upticks are all essentially impossible to state in a conventional database system. The vendors have responded with add-ons of less than stunning performance. But ordered data is important in fields ranging from finance to biology to linguistics. We are implementing a query optimizer for a database whose query language is a strict superset of SQL 92. We show examples of the use of order, review previous work, present our data model, query language and rationale. Then we look at some useful transformations and present some experimental results.

(Joint work with Alberto Lerner)

Speaker Bio:

Dennis Shasha is a professor at NYU's Courant Institute where he does research on biological pattern discovery for microarrays, combinatorial pattern matching on trees and graphs, database tuning, and database design for time series. After graduating from Yale in 1977, he worked for IBM designing circuits and microcode for the 3090. He completed his Ph.D. at Harvard in 1984 (thesis advisor: Nat Goodman). Since he enjoys typing, he has written a few books:

• a professional reference book, Database Tuning: principles, experiments, and troubleshooting techniques (2002, Morgan Kaufmann),
• three books about a mathematical detective named Dr. Ecco, The Puzzling Adventures of Dr. Ecco (1988, Freeman, and republished in 1998 by Dover), Codes, Puzzles, and Conspiracy (1992, Freeman), and Dr. Ecco's Cyberpuzzles (2002, W. W. Norton),
• a book of biographies about great computer scientists, Out of Their Minds: the lives and discoveries of 15 great computer scientists (1995, Copernicus/Springer-Verlag),
• Pattern Discovery in Biomolecular Data: Tools, Techniques, and Applications (1999, Oxford University Press).

In addition, he has co-authored thirty journal papers, 40 conference papers, and four patents. He writes a monthly puzzle column for Scientific American and Dr. Dobb's Journal. He spends much of his time building pattern recognition software these days.

Maintained by Dina Goldin dqg AT cse.uconn.edu
Last updated on 3/9/02