Resource Bound Analysis for Database Queries

James Cheney, Morten Dahl

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

Abstract / Description of output

Many scientific disciplines, such as biology and astronomy, are now collecting large amounts of raw data systematically and storing it centrally in relational databases for shared use by their communities. In many cases such systems accept arbitrary SQL queries submitted using a Web form. Typical database management systems do not provide support for enforcing resource access control policies to guard against expensive or pointless queries submitted accidentally by legitimate users or intentionally by attackers. Instead, such systems typically employ timeouts to halt queries that do not terminate within a reasonable period of time. This approach can limit misuse but cannot prevent it; moreover, it does not provide useful feedback for legitimate users whose queries exceed the time limit.

In this paper, we study a language-based technique for bounding the time and space resource usage of database queries. We introduce a cost semantics for a simple core database query language, define a type-based analysis for estimating an upper bound on the asymptotic running time of a query, and prove its soundness. We also discuss a prototype implementation which we have used to analyze typical SQL queries submitted to the SDSS SkyServer astronomical database.
Original languageEnglish
Title of host publicationProceedings of the Third ACM SIGPLAN Workshop on Programming Languages and Analysis for Security
Place of PublicationNew York, NY, USA
PublisherACM
Pages67-78
Number of pages12
ISBN (Print)978-1-59593-936-4
DOIs
Publication statusPublished - 2008

Publication series

NamePLAS '08
PublisherACM

Keywords / Materials (for Non-textual outputs)

  • databases
  • query languages
  • resource bounds

Fingerprint

Dive into the research topics of 'Resource Bound Analysis for Database Queries'. Together they form a unique fingerprint.

Cite this