Deﬁnability problems for graph query languages

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

Title:	Deﬁnability problems for graph query languages
Authors:	NEVEN, Frank ANTONOPOULOS, Timos 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:	http://hdl.handle.net/1942/14822
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

File	Description	Size	Format
ANSicdt2013.pdf	Peer-reviewed author version	384.17 kB	Adobe PDF	View/Open
2448496.2448514.pdf Restricted Access	Published version	308.14 kB	Adobe PDF	View/Open Request a copy

15

checked on Sep 2, 2020

64

checked on Sep 7, 2022

110

checked on Sep 7, 2022

Check