Intensional Expressive Power of Query Languages

Participants: Limsoon Wong

Background

Most existing studies on the expressive power of query languages have focused on what queries can be expressed and what queries cannot be expressed in a query language. They do not tell us much about whether a query can be implemented efficiently in a query language. Yet, paradoxically, efficiency is of primary concern in computer science. In contrast, the general goal of our proposed project is the development of powerful general methodology for studying the intensional expressive power of query languages, especially those that support nested relations, aggregate functions, powerset or recursion operations.

Objectives

The key differentiating factors of this project include the followings:

We study intensional expressive power in a non-query specific setting. This is probably the first time that intensional expressive power is studied in such a general setting.
We study intensional expressive power of query languages endowed with aggregate functions. These are languages that have the expressiveness of SQL (the de facto query language of the industry). This is probably the first time the intensional expressive power of SQL is studied.
We develop a series of powerful general analytical tools for investigating intensional expressive power. Currently, no such general analytical tool is available.

In short, this project aims to deliver major breakthroughs in the theoretical study and analysis of the intensional expressive power of query languages in a way that is more general and more powerful than earlier works.

Selected Publications

Limsoon Wong. A dichotomy in the intensional expressive power of nested relational calculi augmented with aggregate functions and a powerset operator. Proceedings of 32nd ACM Symposium on Principles of Database Systems, pages 285--295, New York, 22-27 June 2013. PDF
Limsoon Wong. The Dichotomous Intensional Expressive Power of the Nested Relational Calculus with Powerset. In Search of Elegance in the Theory and Practice of Computation, edited by Val Tannen, Limsoon Wong, Leonid Libkin, Wenfei Fan, Wang-Chiew Tan, Michael Fourman, pages 542--556, Springer, October 2013.

Selected Presentations

Limsoon Wong. A retrospective on naturally embedded query languages. Test of Time Award talk at 17th International Conference on Database Theory (ICDT), Athens, Greece, 25 March 2014.
Limsoon Wong. Some thoughts on designing a genomic query language. Invited talk at GeCo Workshop on Challenges in Data-Driven Genomic Computing, Villa del Grumello, Como, Italy, 6-8 March 2019.

Acknowledgements

This project is supported in part by a Singapore Ministry of Education Tier 1 grant, MOE T1 251RES1206.

Last updated: 11/3/2019, Limsoon Wong.