Intensional Expressive Power of Query Languages
Participants: Limsoon Wong
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.
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.
- 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.
- 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.
This project is supported in part by
a Singapore Ministry of Education Tier 1 grant,
MOE T1 251RES1206.
Last updated: 16/11/2015, Limsoon Wong.