Document Server@UHasselt >
Research >
Research publications >

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
Citation: 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.
URI: http://hdl.handle.net/1942/14912
DOI: 10.1145/2448496.2448512
ISBN: 978-1-4503-1598-2
Category: C1
Type: Proceedings Paper
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
author version418.07 kBAdobe PDF

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