Spatial Tree Logics to reason about Semistructured Data
Giovanni Conforti, Giorgio Ghelli · CINECA IRIS Institutial research information system (University of Pisa) · 2003
The Ambient Logic is a modal logic proposed to describe the structural and computational properties of distributed and mobile computations. The static part of the Ambient Logic is, essentially, a spatial logic for unordered labeled trees, hence it turns out to be a good foundation for expressing properties of tree-shaped data (i.e. semistructured data and XML). The Tree Query Language (TQL) is a query language for semistructured data based on the Ambient Logic. TQL uses Ambient Logic formulas to express properties of data that will be collected using a sort of pattern-matching mechanism. Reasoning about constraints for semistructured Data and XML is an active branch of research and has several applications including query optimizations and data integration; it is crucial for validity, type inference, and static type checking. Furthermore the interaction of schema and constraints is both theoretically and practically interesting (in particular for XML), and is currently a largely unexplored area. This paper introduces Spatial Tree Logics (STL, fragments of the logic of TQL) as formalisms for semistructured data constraint, type and query specification and reasoning. As an example, a decidable STL fragment is presented, and it is used to solve some specific decision problems for semistructured data.