Department of Computing
Imperial College
4pm Tuesday 29th January 2002
Room 2511, JCMB, King's Buildings
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 directed 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.
This talk describes joint work with Luca Cardelli and Giorgio Ghelli.