

G. H. L. Fletcher, M. Gyssens, D. Leinders, J. Van den Bussche, D. Van Gucht, and S. Vansummeren. Relative Expressive Power of Navigational Querying on Graphs. In Database Theory  ICDT 2011, 14th International Conference, ACM International Conference Proceedings Series, pages 197207. ACM Press, March 2011.
© ACM Press 2011
Abstract
Motivated by the renewed interest in semistructured and graph data models, we study a family of XPathlike query languages over graphs, rather than trees as is done in XML studies. We consider a basic algebra over graphs, i.e., binary relations, consisting of composition, union, and intersection. The empty and identity relations are always assumed to be present. To this, we can add various features: (i) set difference; (ii) converse; (iii) the diversity relation; (iv) projection; and (v) coprojection (inspired by Core XPath). As these features are not all independent, we thus obtain 14 different logics for expressing queries on binary relations. We establish a strict Hasse diagram for their relative expressive power. It is wellknown that the maximal logic is equivalent to the 3variable fragment of firstorder logic over binary relations. We establish a similar characterization for its positive fragment. Also, we discuss the relationship between the 2variable fragment and the logics we consider. We define appropriate notions of bisimilarity or similarity that capture indistinguishability by these logics, and obtain instancecompleteness characterizations in the style of Bancilhon and Paredaens. For some positive languages, we also characterize the graph patterns they can express.




