Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/13190
Title: | The Impact of Transitive Closure on the Boolean Expressiveness of Navigational Query Languages on Graphs | Authors: | Fletcher, George H. L. GYSSENS, Marc LEINDERS, Dirk VAN DEN BUSSCHE, Jan Van Gucht, Dirk VANSUMMEREN, Stijn Wu, Yuqing |
Issue Date: | 2012 | Publisher: | Springer | Source: | Lukasiewicz, Thomas; Sali, Attila (Ed.). Foundations of Information and Knowledge Systems, 7th International Symposium, FoIKS 2012, Kiel, Germany, March 5-9, 2012. Proceedings., Springer,p. 125-144 | Series/Report: | LECTURE NOTES OF COMPUTER SCIENCE | Series/Report no.: | 7153 | 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 other set operators, projection and coprojection, converse, and the diversity relation. In this paper, we show that, when evaluated at the level of boolean queries with an unlabeled input graph (i.e., a single relation), adding transitive closure to the languages with coprojection adds expressive power, while this is not the case for the basic language to which none, one, or both of projection and the diversity relation are added. In combination with earlier work [10], these results yield a complete understanding of the impact of transitive closure on the languages under consideration. | Document URI: | http://hdl.handle.net/1942/13190 | ISBN: | 9783642284717 | Rights: | Copyright Springer-Verlag Berlin Heidelberg 2012 | Category: | C1 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
foiks2012.pdf Restricted Access | Non Peer-reviewed author version | 406.47 kB | Adobe PDF | View/Open Request a copy |
Page view(s)
58
checked on Sep 5, 2022
Download(s)
42
checked on Sep 5, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.