Path Constraints from a Modal Logic Point of View
Natasha Alechina, Stéphane P. Demri, Maarten de Rijke · UvA-DARE (University of Amsterdam) · 2001
We analyse several classes of path constraints for semistructured data in a unified framework and prove some decidability results for them by embedding them in Propositional Dynamic Logic [Pra76]. Some of these results are new, while others are already known [AV97], but we hope that our proof sheds some additional light on the reasons for decidability. 1 Introduction In recent years, a lot of interesting work has been done to extend database techniques to semistructured collections of data, in particular the World Wide Web or fragments of it. A general overview of this work can be found in [Abi97], see also [MMM96, BDFS97, AQM97]. In this paper, we build on the results in [AV97] and [BFW98]. It is generally agreed that the appropriate data model for semistructured data is an edge-labelled graph. In particular, the WWW can be seen as a set of objects linked by labelled edges. An object represents a page, and the labelled edges represent hypertext links (see Figure 1). Query languages p...