www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

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
Citation: 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.
URI: http://hdl.handle.net/1942/16407
DOI: 10.1007/s10472-013-9346-x
ISI #: 000347691500007
ISSN: 1012-2443
Category: A1
Type: Journal Contribution
Validation: ecoom, 2016
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A741.26 kBAdobe PDF
N/A299 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.