Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/16709
Title: | Conjunctive Context-Free Path Queries | Authors: | HELLINGS, Jelle | Issue Date: | 2014 | Source: | Schweikardt, Nicole; Christophides, Vassilis; Leroy, Vincent (Ed.). Database Theory — ICDT 2014, p. 119-130 | Abstract: | In graph query languages, regular expressions are commonly used to specify the labeling of paths. A natural step in increasing the expressive power of these query languages is replacing regular expressions by context-free grammars. With the Conjunctive Context-Free Path Queries (CCFPQ) we introduce such a language based on the well-known Conjunctive Regular Path Queries (CRPQ). First, we show that query evaluation of CCFPQ has polynomial time data complexity. Secondly, we look at the generalization of regular expressions, as used in CRPQ, to regular relations and show how similar generalizations can be applied to context-free grammars, as used in CCFPQ. Thirdly, we investigate the relations between the expressive power of CRPQ, CCFPQ, and their generalizations. In several cases we show that replacing regular expressions by context-free grammars does increase expressive power. Finally, we look at including context-free grammars in more powerful logics than conjunctive queries. We do so by adding negation and provide expressivity relations between the obtained languages. | Document URI: | http://hdl.handle.net/1942/16709 | Link to publication/dataset: | http://openproceedings.org/ICDT/2014/paper_34.pdf | ISBN: | 978-3-89318066-1 | DOI: | 10.5441/002/icdt.2014.15 | Rights: | (c) 2014, Copyright is with the authors. Published in Proc. 17th International Conference on Database Theory (ICDT), March 24-28, 2014, Athens, Greece: ISBN 978-3-89318066-1, on OpenProceedings.org. Distribution of this paper is permitted under the terms of the Creative Commons license CC-by-nc-nd 4.0. | Category: | C1 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
icdt2014_paper.pdf | Peer-reviewed author version | 367.03 kB | Adobe PDF | View/Open |
Page view(s)
22
checked on Sep 7, 2022
Download(s)
10
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.