Document Server@UHasselt >
Research publications >
Please use this identifier to cite or link to this item:
|Title: ||A Framework for Comparing Query Languages in Their Ability to Express Boolean Queries|
|Authors: ||Surinx, Dimitri|
|Advisors: ||Van den Bussche, Jan|
|Issue Date: ||2017|
|Abstract: ||When a relational database is queried, the result is normally a relation.
Some queries, however, only require a yes/no answer; such
queries are often called boolean queries. In this thesis, we introduce a framework along which we can investigate boolean queries.
We introduce three natural base modalities: testing for nonemptiness of a query; testing for
emptiness; and testing for the containment of the result of one
query in the result of another query. For the class of
first-order queries, these three modalities have exactly the same
expressive power. For other classes of queries, e.g., expressed
in weaker query languages, the modalities may differ in
expressiveness. The expressive power under these different modalities can be compared in several different themes, e.g., we can compare a fixed query language F under emptiness to F under nonemptiness. We introduce four general themes to compare the base modalities:
(1) We identify crucial query features that enable us to go from one modality to
another for a fixed query language. Furthermore, we identify semantical
properties that reflect the lack of these query features to establish
(2) We compare the expressive power of the base modalities by comparing
different query languages under fixed modalities.
(3) We compare the expressive power of different query languages under
(4) We investigate the closure of the modalities under the boolean connectives.
For each of these themes, we establish subsumption as well as separation results for well known query languages such as conjunctive queries and navigational graph query languages.|
|Type: ||Theses and Dissertations|
|Appears in Collections: ||PhD theses|
Files in This Item:
|N/A||1.5 MB||Adobe PDF|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.