This talk describes joint work with Luca Cardelli 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.