The graph structured data model has a broad range of applications including applications in the social sciences, bio-informatics, the semantic web, geographical data, and in formal verification. Also frequently used data models such as the XML data model and the RDF data model are variants of the graph structured data model. These practical applications ask for a broad understanding on the theoretical side of graph structured databases. A key subject therein is the study of query languages for graph structured data. Graph structured data can be represented by traditional relational structures. For querying we thus can fall back to traditional first-order relational query languages. First-order logic is however not always the best choice for querying graph structured data. The main reason is that first-order logic is restricted to `local' reasoning: first-order logic cannot reason about graph-concepts such as paths and reachability. We propose to study what we call Walk Logic: the extension of first-order logic with explicit quantifiers over the walks in a graph and over the positions on these walks. Walk Logic is not only intended as a query language; it is also intended as a yardstick to understand the expressiveness of path queries on graphs.