Document Server@UHasselt >
Research publications >
Please use this identifier to cite or link to this item:
|Title: ||Conjunctive Context-Free Path Queries|
|Authors: ||HELLINGS, Jelle|
|Issue Date: ||2014|
|Citation: ||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.|
|Link to publication: ||http://openproceedings.org/ICDT/2014/paper_34.pdf|
|Type: ||Proceedings Paper|
|Appears in Collections: ||Research publications|
Files in This Item:
|Main article||367.03 kB||Adobe PDF|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.