Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/13198
Title: | Relative expressive power of navigational querying on graphs | Authors: | Fletcher, George H. L. GYSSENS, Marc LEINDERS, Dirk VAN DEN BUSSCHE, Jan Van Gucht, Dirk VANSUMMEREN, Stijn Wu, Yuqing |
Issue Date: | 2011 | Publisher: | ACM Press | Source: | Milo, Tova (Ed.). Database Theory - ICDT 2011, 14th International Conference, Uppsala, Sweden, March 21-24, 2011, Proceedings, ACM Press,p. 197-207 | Abstract: | Motivated by both established and new applications, we study navigational query languages for graphs (binary relations). The simplest language has only the two operators union and composition, together with the identity relation. We make more powerful languages by adding any of the following operators: intersection; set di erence; projection; coprojection; converse; transitive closure; and the diversity relation. All these operators map binary relations to binary relations. We compare the expressive power of all resulting languages. We do this not only for general path queries (queries where the result may be any binary relation) but also for boolean or yes/no queries (expressed by the nonemptiness of an expression). For both cases, we present the complete Hasse diagram of relative expressiveness. In particular, the Hasse diagram for boolean queries contains nontrivial separations and a few surprising collapses. | Keywords: | XPath; graphs; relation algebra; indistinguishability; expressive power; finite variable logic | Document URI: | http://hdl.handle.net/1942/13198 | ISBN: | 978-1-4503-0529-7 | DOI: | 10.1145/1938551.1938578 | Rights: | Copyright 2011 ACM | Category: | C1 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
uppsala.pdf Restricted Access | Non Peer-reviewed author version | 309.49 kB | Adobe PDF | View/Open Request a copy |
SCOPUSTM
Citations
27
checked on Sep 3, 2020
Page view(s)
68
checked on Sep 7, 2022
Download(s)
56
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.