Higher-order queries and applications

Thesis

Higher-order transformations are ubiquitous within data management. In relational databases, higher-order queries appear in numerous aspects including query rewriting and query specification. In XML databases, higher-order functions are natural due to the close connection of XML query languages with functional programming.

The thesis investigates higher-order query languages that combine higher- order transformations with ordinary database query languages. We de- fine higher-order query languages based on Relational Algebra, Monad Algebra, and XQuery. The thesis also studies basic problems for these query languages including evaluation, containment, and type inference. We show that even though evaluating these higher-order query languages is non-elementary, there are subclasses that are polynomially reducible to evaluation for ordinary query languages.

Our theoretical analysis is complemented by an implementation of the languages, our Higher-Order Mapping Evaluation System (HOMES). The system integrates querying and query transformation in a single higher- order query language. It allows users to write queries that integrate and combine query transformations. The system is implemented on top of traditional database management systems. The evaluation algorithm is optimized by a combination of subquery caching techniques from relational and XML databases and sharing detection schemes from functional programming.

Authors: Vu, Q

• Publication date: 2012
• DOI: 10.5287/ora-pp0apyvb2
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: Oxford University, UK
• Language: English
• Keywords: higher-order; XML; database; lambda calculus; function
• Subjects: Software engineering; Applications and algorithms