A Framework for Comparing Query Languages in Their Ability to Express Boolean Queries

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 separations. (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 different modalities. (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.