Spatial Logics for Querying Data on the Web

The (unofficial) collaborators on this project are Luca Cardelli and Giorgio Ghelli.

Project Aims

Semi-structured data (such as XML) plays an important role in the exchange of information between globally distributed applications. 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 research project focusses on the study of spatial logics for reasoning about semi-structured data, and the application of these logics to provide query languages for manipulating such data. We will introduce a `trees with pointers model', a new data structure for representing data on the Web. Our model focusses on dangling pointers which we believe occur naturally: for example, a link to a webpage that is currently down. Dangling pointers are used by O'Hearn and Reynolds in their work on pointer arithmetic, but are not emphasised by existing semi-structured data models. We will develop a spatial logic for our model, which allows us to reason locally about disjoint substructures. We will design a query language which integrates well with our model and logic, and compare our approach with existing languages such as XML-QL and XDuce. We will extend our models to incorporate dynamically-changing structure, as a step towards understanding the dynamic nature of the Web.

Relevant Papers

  • Manipulating Trees with Hiding (with Luca Cardelli and Giorgio Ghelli), FOSSACS 2003.
  • Querying Trees with Pointers (an unpublished note with Luca Cardelli and Giorgio Ghelli).
  • A Spatial Logic for Querying Graphs , Luca Cardelli, Philippa Gardner and Giorgio Ghelli
  • Several papers on spatial logics by Caires, Calcagno, Cardelli, Gordon, O'Hearn, Pym, Reynolds, see for example here
  • A Query Language Based on the Ambient Logic, Luca Cardelli and Giorgio Ghelli
  • The Fusion Machine, Philippa Gardner, Cosimo Laneve and Lucian Wischik.


  • Cristiano Calcagno, researcher funded by EPSRC
  • Philippa Gardner
  • Sergio Maffeis, PhD student funded by Microsoft
  • Uri Zarfaty, PhD student funded by EPSRC
    Philippa Gardner
    pg @