Operational and abstract semantics of the query language G-Log

The amount and variety of data available electronically have dramatically increased in the last decade; however, data and documents are stored in different ways and do not usually show their internal structure. In order to take full advantage of the topological structure of digital documents, and particularly web sites, their hierarchical organization should be exploited by introducing a notion of query similar to the one used in database systems. A good approach, in that respect, is the one provided by graphical query languages, originally designed to model object bases and later proposed for semistructured data, like G-Log. The aim of this paper is to provide suitable graph-based semantics to this language, supporting both data structure variability and topological similarities between queries and document structures. A suite of operational semantics based on the notion of bisimulation is introduced both at the concrete level (instances) and at the abstract level (schemata), giving rise to a semantic framework that benefits from the cross-fertilization of tools originally designed in quite different research areas (databases, concurrency, logics, static analysis).