University of Cambridge

Logic
&
Semantics

A Spatial Logic for Querying Graphs

By Luca Cardelli, Philippa Gardner (Department of Computing, Imperial College), and Giorgio Ghelli.

The recent emergence of XML as a universally agreed standard for `net data' is challenging both traditional data base models and traditional programming languages. While the shape of this new net data is familiar (labelled graphs, or trees with graphical links), the type systems and query languages needed to handle it are drastically different from conventional ones. New research is needed on how to describe and manipulate this new kind of data.

This talk focuses on the study of 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 description of graphs using constructs from process algebra, which has a natural multiset semantics. We introduce a spatial logic for reasoning about graphs, which integrates well with our graphical models and allows us 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 work contrasts with the more traditional set-based semantics found in logic-based query languages such as TQL, a query language for trees based on a spatial logic, and Strudel and GraphLog, query languages for graphs.