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 | 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 |
Files in This Item:
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 |
SCOPUSTM
Citations
15
checked on Sep 2, 2020
Page view(s)
64
checked on Sep 7, 2022
Download(s)
110
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.