Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/14822

Title: Definability problems for graph query languages
Authors: Neven, Frank
Antonopoulos, Timos
Servais, Frederic
Issue Date: 2013
Publisher: ACM
Citation: ICDT '13: Proceedings of the 16th International Conference on Database Theory, p. 141-152
Abstract: Given a graph, a relation on its nodes, and a query language Q of interest, we study the Q-definability problem which amounts to deciding whether there exists a query in Q defining precisely the given relation over the given graph. Previous research has identified the complexity of FO- and CQ-de nability. In this paper, we consider the definability problem for regular paths and conjunctive regular path queries (CRPQs) over labelled graphs.
URI: http://hdl.handle.net/1942/14822
DOI: 10.1145/2448496.2448514
ISBN: 978-1-4503-1598-2
Category: C1
Type: Proceedings Paper
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Main article with appendix384.17 kBAdobe PDF

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