  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.
