Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/16407
Title: | The impact of transitive closure on the expressiveness of navigational query languages on unlabeled graphs | Authors: | Fletcher, G.H.L. GYSSENS, Marc LEINDERS, Dirk VAN DEN BUSSCHE, Jan Van Gucht, Dirk VANSUMMEREN, Stijn Wu, Yuqing |
Issue Date: | 2015 | Source: | ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 73 (1-2), 167-203 | Abstract: | Several established and novel applications motivate us to study the expressive power of navigational query languages on graphs, which represent binary relations. Our basic language has only the operators union and composition, together with the identity relation. Richer languages can be obtained by adding other features such as intersection, difference, projection and coprojection, converse, and the diversity relation. The expressive power of the languages thus obtained cannot only be evaluated at the level of path queries (queries returning binary relations), but also at the level of Boolean or yes/no queries (expressed by the nonemptiness of an expression). For the languages considered above, adding transitive closure augments the expressive power not only at the level of path queries but also at the level of Boolean queries, for the latter provided that multiple input relations are allowed. This is no longer true in the context of unlabeled graphs (i.e., in the case where there is only one input relation), however. In this paper, we prove that this is indeed not the case for the basic language to which none, one, or both of projection and the diversity relation are added, a surprising result given the limited expressive power of these languages. In combination with earlier work (Fletcher et al. 2011, 2012), this result yields a complete understanding of the impact of transitive closure on the languages under consideration. | Notes: | [Fletcher, George H. L.] Eindhoven Univ Technol, Dept Math & Comp Sci, NL-5600 MB Eindhoven, Netherlands. [Gyssens, Marc; Leinders, Dirk; Van den Bussche, Jan] Hasselt Univ, Sch Informat Technol, B-3500 Hasselt, Belgium. [Gyssens, Marc; Leinders, Dirk; Van den Bussche, Jan] Transnat Univ Limburg, B-3500 Hasselt, Belgium. [Van Gucht, Dirk; Wu, Yuqing] Indiana Univ, Sch Informat & Comp, Bloomington, IN 47405 USA. [Vansummeren, Stijn] Univ Libre Bruxelles, Dept Comp & Decis Engn CoDE, B-1050 Brussels, Belgium. | Keywords: | Boolean query; transitive closure; relation algebra; unlabeled graph; expressiveness | Document URI: | http://hdl.handle.net/1942/16407 | ISSN: | 1012-2443 | e-ISSN: | 1573-7470 | DOI: | 10.1007/s10472-013-9346-x | ISI #: | 000347691500007 | Rights: | © Springer Science+Business Media Dordrecht 2013 | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2016 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
art%3A10.1007%2Fs10472-013-9346-x.pdf Restricted Access | 741.26 kB | Adobe PDF | View/Open Request a copy | |
amai2015.pdf | 299 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
12
checked on Sep 3, 2020
WEB OF SCIENCETM
Citations
11
checked on May 17, 2024
Page view(s)
86
checked on Apr 26, 2023
Download(s)
152
checked on Apr 26, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.