A Spatial Logic for Querying Graphs


  • Luca Cardelli
  • Philippa Gardner
  • Giorgio Ghelli


We study a spatial logic for reasoning about labelled directed graphs, and the application of this logic to provide a query language for analysing and manipulating such graphs. We give a graph description using constructs from process algebra. We introduce a spatial logic in order to reason locally about disjoint subgraphs. We extend our logic to provide a query language which preserves the multiset semantics of our graph model. Our approach contrasts with the more traditional set-based semantics found in query languages such as TQL, Strudel and GraphLog.


Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP’02), pp. 597–610

Publication Date

Jul 2002


Source Materials