resource bound analysis for database queries
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.
resource bounds databases query languages