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 was 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
This project aimed to deliver major breakthroughs in the
theoretical study and analysis of the intensional expressive power of
query languages in a way that was more general and more powerful
than earlier works.
- We studied intensional expressive power in a non-query specific setting.
This was the first time that intensional expressive power was
studied in such a general setting.
- We studied 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 was
the first time the intensional expressive power of SQL is studied.
- We developed a series of powerful general analytical tools for
investigating intensional expressive power. To date, few such general
analytical tool is available.
Achievements
- The Dichotomy Theorem for NRC(powerset),
which is the language obtained by augmenting the usual nested
relational calculus with a powerset operation. Thus,
if a query cannot be expressed in NRC(powerset) without
the powerset operation, any implementation of it in NRC(powerset)
must use exponential amount of space.
- The Dichotomy Theorem for NRC(Q, +. -. *, ÷, ∑, powerset),
which is the language obtained by augmenting NRC(powerset)
with arithmetic and aggregating functions. Thus, if a query cannot
be expressed in NRC(Q, +, -, *, ÷,∑, powerset) without
the powerset operation, any implementation of it in
NRC(Q, +, -, *, ÷, ∑, powerset) must use an exponential
amount of space.
- The Dichotomy Theorem for NRC(Q, +, -, *, ÷, ∑, eqn),
which replaces the powerset operation by an operation that iterates
over all subsets in a consume-and-discard manner (i.e. it does not
produce and store the entire powerset before processing it). Thus,
if a query cannot be expressed in NRC(Q, +, -, *, ÷, ∑, eqn)
without the eqn operation, any implementation of it in
NRC(Q, +, -, *, ÷, ∑, eqn) must use an exponential
amount of time.
- The Quasi-Locality and the Quasi-Bounded-Degree Properties
of NRC(>ι, iter), which is a hierarch of languages obtained
by augmenting the usual nested relational calculus with a family of
sub-logarithmic-depth recursion operations. Thus, if a query is
expressible in NRC(>ι iter), its output is determined by
considering small neighbourhoods of sub-logarithmic-length radius of
its input and the number of distinct degrees in its output is
a constant sub-logarithmic power of the size and degree of its input.
This is a generalization of the locality and bounded-degree properties
of nested relational calculus, for the first time, to recursive operations.
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
Acknowledgements
This project was supported in part by
a Singapore Ministry of Education Tier 1 grant,
MOE T1 251RES1206.
Last updated: 11/3/2019, Limsoon Wong.