+1 Recommend
0 collections
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Querying for Paths in Graphs using Context-Free Path Queries


      Read this article at

          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.


          Navigational queries for graph-structured data, such as the regular path queries and the context-free path queries, are usually evaluated to a relation of node-pairs \((m, n)\) such that there is a path from \(m\) to \(n\) satisfying the conditions of the query. Although this relational query semantics has practical value, we believe that the relational query semantics can only provide limited insight in the structure of the graph data. To address the limits of the relational query semantics, we introduce the all-path query semantics and the single-path query semantics. Under these path-based query semantics, a query is evaluated to all paths satisfying the conditions of the query, or, respectively, to a single such path. While focusing on context-free path queries, we provide a formal framework for evaluating queries on graphs using both path-based query semantics. For the all-path query semantics, we show that the result of a query can be represented by a finite context-free grammar annotated with node-information relevant for deriving each path in the query result. For the single-path query semantics, we propose to search for a path of minimum length. We reduce the problem of finding such a path of minimum length to finding a string of minimum length in a context-free language, and for deriving such a string we propose a novel algorithm. Our initial results show that the path-based query semantics have added practical value and that query evaluation for both path-based query semantics is feasible, even when query results grow very large. For the single-path query semantics, determining strict worst-case upper bounds on the size of the query result remains the focus of future work.

          Related collections

          Author and article information


          Databases, Data structures & Algorithms


          Comment on this article