Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-41660-6-30
Title: The dichotomous intensional expressive power of the nested relational calculus with powerset
Authors: Wong, L. 
Issue Date: 2013
Source: Wong, L. (2013). The dichotomous intensional expressive power of the nested relational calculus with powerset. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 8000 : 542-556. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-41660-6-30
Abstract: 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 a key concern in computer science. In this paper, the efficiency of queries in, a nested relational calculus with a powerset operation, is discussed. A dichotomy in the efficiency of these queries on a large general class of structures - which include long chains, deep trees, etc. - is proved. In particular, it is shown that these queries are either already expressible in the usual nested relational calculus or require at least exponential space. This Dichotomy Theorem, when coupled with the bounded degree and locality properties of the usual nested relational calculus becomes a powerful general tool in studying the intensional expressive power of query languages. The bounded degree and locality properties make it easy to prove that a query is inexpressible in the usual nested relational calculus. Then, if the query is expressible in, subject to the conditions of the Dichotomy Theorem, the query must take at least exponential space. © 2013 Springer-Verlag Berlin Heidelberg.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/77931
ISBN: 9783642416590
ISSN: 03029743
DOI: 10.1007/978-3-642-41660-6-30
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

28
checked on Feb 23, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.