A BRICS Mini-Course
May 14 and 16, 2002
Lectures by
Philippa Gardner, pg@doc.ic.ac.uk
Imperial College, London, UK
Semi-structured data plays an important role in the exchange of information between globally distributed applications: examples include BibTex files and XML documents. Whilst the research community mostly agree on defining semi-structured data using labelled directed graphs or trees with `graphical' links, the study of how to query, modify and manipulate such data is still very active.
This series of talks focuses on the study of spatial logics for reasoning about semi-structured data, and the application of these logics to provide query languages for analysing and manipulating such data. Cardelli and Ghelli were the first to apply spatial logic reasoning to this application. They introduced the query language TQL, based on a spatial logic for reasoning about labelled trees. The power of the spatial (structural) reasoning is that it provides local reasoning about disjoint substructures. This means that we can analyse the horizonal structure of trees, as well as the more usual vertical path structure.
The labelled tree model has its limitations however as a model for data on the Web: there are no graphical links (such as back-pointers), and the underlying multiset semantics is unable to identify different locations (subtrees) precisely. Cardelli, Gardner and Ghelli have adapted the TQL research to labelled directed graphs, although the ability to cluster information is lost. Our on-going research introduces the `trees with pointers' model, a new data structure based on trees with additional graphical links and a set-based semantics with unique location descriptions. Unlike the current models of semi-structured data, our model emphasises the notion of dangling pointer. Dangling pointers occur naturally on the Web. They also form an essential ingredient of O'Hearn, Pym and Reynolds' recent work on using a spatial logic for reasoning about pointer diagrams. Their model is a degenerate case of our model.
The following people have contributed to work presented in these talks: Luis Caires, Luca Cardelli, Giorgio Ghelli, Andy Gordon, Sergio Maffeis, Peter O'Hearn, David Pym and John Reynolds.