Please use this identifier to cite or link to this item:
Title: Definability problems for graph query languages
Authors: NEVEN, Frank 
SERVAIS, Frederic 
Issue Date: 2013
Publisher: ACM
Source: 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.
Keywords: Graph queries; Databases
Document URI:
ISBN: 978-1-4503-1598-2
DOI: 10.1145/2448496.2448514
Rights: Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the ACM. To copy otherwise, or to republish, to post on servers or to redistribute to lists, requires a fee and/or special permissions from the publisher, ACM. EDBT/ICDT 2013, Genoa, Italy. Copyright 2013 ACM.
Category: C1
Type: Proceedings Paper
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
ANSicdt2013.pdfMain article with appendix384.17 kBAdobe PDFView/Open
Show full item record


checked on Sep 2, 2020

Page view(s)

checked on May 26, 2022


checked on May 26, 2022

Google ScholarTM



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