Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/29982
Title: | A framework for comparing query languages in their ability to express boolean queries | Authors: | SURINX, Dimitri VAN DEN BUSSCHE, Jan Van Gucht, Dirk |
Issue Date: | 2019 | Publisher: | SPRINGER | Source: | ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 87(1-2), p. 157-184 | Abstract: | For any query language F, we consider three natural families of boolean queries. Nonemptiness queries are expressed as e not equal empty set with e an F expression. Emptiness queries are expressed as e = empty set. Containment queries are expressed as e(1) subset of e(2). We refer to syntactic constructions of boolean queries as modalities. In first order logic, the emptiness, nonemptiness and containment 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. We propose a framework for studying the expressive power of boolean query modalities. Along one dimension, one may work within a fixed query language and compare the three modalities. Here, we identify crucial query features that enable us to go from one modality to another. Furthermore, we identify semantical properties that reflect the lack of these query features to establish separations. Along a second dimension, one may fix a modality and compare different query languages. This second dimension is the one that has already received quite some attention in the literature, whereas in this paper we emphasize the first dimension. Combining both dimensions, it is interesting to compare the expressive power of a weak query language using a strong modality, against that of a seemingly stronger query language but perhaps using a weaker modality. We present some initial results within this theme. The two main query languages to which we apply our framework are the algebra of binary relations, and the language of conjunctive queries. | Keywords: | Query languages; Expressive power; Graph databases; Conjunctive queries; Boolean query modalities;Query languages; Expressive power; Graph databases; Conjunctive queries; Boolean query modalities | Document URI: | http://hdl.handle.net/1942/29982 | ISSN: | 1012-2443 | e-ISSN: | 1573-7470 | DOI: | 10.1007/s10472-019-09639-5 | ISI #: | 000491609600007 | Rights: | Springer Nature Switzerland AG 2019 | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2020 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
surinx 1.pdf Restricted Access | Published version | 624.43 kB | Adobe PDF | View/Open Request a copy |
amai_preprint.pdf | Peer-reviewed author version | 359.72 kB | Adobe PDF | View/Open |
Page view(s)
116
checked on Sep 7, 2022
Download(s)
146
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.