Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/27149
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: | 2018 | Publisher: | Springer International Publishing AG | Source: | Ferrarotti, Flavio; Woltran, Stefan (Ed.). Foundations of Information and Knowledge Systems: 10th International Symposium, FoIKS 2018, Budapest, Hungary, May 14–18, 2018, Proceedings, Springer International Publishing AG,p. 360-378 | Series/Report: | Lecture Notes in Computer Science | Series/Report no.: | 10833 | Abstract: | We identify three basic modalities for expressing boolean queries using the expressions of a query language: nonemptiness, emptiness, and containment. 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 ways, e.g., we can compare a fixed query language F under emptiness to F under nonemptiness. 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. As an important auxiliary result, we establish a preservation theorem for monotone containments of conjunctive queries. | Document URI: | http://hdl.handle.net/1942/27149 | ISBN: | 9783319900490 | DOI: | 10.1007/978-3-319-90050-6_20 | ISI #: | WOS:000546329500020 | Category: | C1 | Type: | Proceedings Paper | Validations: | ecoom 2021 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
budapest.pdf Restricted Access | Peer-reviewed author version | 289.76 kB | Adobe PDF | View/Open Request a copy |
SCOPUSTM
Citations
2
checked on Sep 2, 2020
WEB OF SCIENCETM
Citations
1
checked on Oct 12, 2024
Page view(s)
70
checked on Sep 7, 2022
Download(s)
50
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.