A Spatial Logic for Querying Graphs
Venue
Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP’02), pp. 597–610
Publication Year
2002
Identifiers
Authors
- Luca Cardelli
- Philippa Gardner
- Giorgio Ghelli
Abstract
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.