Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/18681
Title: | Relative expressive power of navigational querying on graphs | Authors: | Fletcher, George H. L. GYSSENS, Marc LEINDERS, Dirk SURINX, Dimitri VAN DEN BUSSCHE, Jan Van Gucht, Dirk VANSUMMEREN, Stijn Wu, Yuqing |
Issue Date: | 2015 | Publisher: | ELSEVIER SCIENCE INC | Source: | INFORMATION SCIENCES, 298, p. 390-406 | 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 difference; projection; coprojection; converse; 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 some nontrivial separations and a few surprising collapses. (C) 2014 Elsevier Inc. All rights reserved. | Notes: | [Fletcher, George H. L.] Eindhoven Univ Technol, NL-5600 MB Eindhoven, Netherlands. [Gyssens, Marc; Leinders, Dirk; Surinx, Dimitri; Van den Bussche, Jan] Hasselt Univ, Diepenbeek, Belgium. [Gyssens, Marc; Leinders, Dirk; Surinx, Dimitri; Van den Bussche, Jan] Transnatl Univ Limburg, Diepenbeek, Belgium. [Van Gucht, Dirk; Wu, Yuqing] Indiana Univ, Bloomington, IN 47405 USA. [Vansummeren, Stijn] Univ Libre Bruxelles, Brussels, Belgium. | Keywords: | graph databases; query languages; expressive power;Graph databases; Query languages; Expressive power | Document URI: | http://hdl.handle.net/1942/18681 | ISSN: | 0020-0255 | e-ISSN: | 1872-6291 | DOI: | 10.1016/j.ins.2014.11.031 | ISI #: | 000349590000022 | Rights: | © 2014 Elsevier Inc. All rights reserved. | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2016 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
fletcher 1.pdf Restricted Access | Published version | 697.78 kB | Adobe PDF | View/Open Request a copy |
1401.8201v2.pdf | Non Peer-reviewed author version | 539.55 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.