Document Server@UHasselt >
Research >
Research publications >

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
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.
URI: http://hdl.handle.net/1942/16709
Link to publication: http://openproceedings.org/ICDT/2014/paper_34.pdf
DOI: 10.5441/002/icdt.2014.15
ISBN: 978-3-89318066-1
Category: C1
Type: Proceedings Paper
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Main article367.03 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.