Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/14912
Title: | Walk logic as a framework for path query languages on graph databases | Authors: | HELLINGS, Jelle KUIJPERS, Bart VAN DEN BUSSCHE, Jan ZHANG, Xiaowang |
Issue Date: | 2013 | Publisher: | ACM | Source: | Tan, Wang-Chiew; Guerrini, Giovanna; Catania, Barbara; Gounaris, Anastasios (Ed.). Proceedings of the 16th International Conference on Database Theory, p. 117-128 | Series/Report: | International Conference on Database Theory | Series/Report no.: | 16 | Abstract: | Motivated by the current interest in languages for expressing path queries to graph databases, this paper proposes to investigate Walk Logic (WL): the extension of first-order logic on finite graphs with the possibility to explicitly quantify over walks. WL can serve as a unifying framework for path query languages. To support this claim, WL is compared in expressive power with various established query languages for graphs, such as first-order logic extended with reachability; the monadic second-order logic of graphs; hybrid computation tree logic; and regular path queries. WL also serves as a framework to investigate the following natural questions: Is quantifying over walks more powerful than quantifying over paths (walks without repeating nodes) only? Is quantifying over infinite walks more powerful than quantifying over finite walks only? WL model checking is decidable, but determining the precise complexity remains an open problem. | Keywords: | Logic; Databases | Document URI: | http://hdl.handle.net/1942/14912 | ISBN: | 978-1-4503-1598-2 | DOI: | 10.1145/2448496.2448512 | Rights: | ACM | Category: | C1 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
icdt2013_paper.pdf | Peer-reviewed author version | 418.07 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
12
checked on Sep 7, 2020
Page view(s)
106
checked on Sep 5, 2022
Download(s)
268
checked on Sep 5, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.