CoDE Publications CoDE Publications
IRIDIA Publications IRIDIA Publications
SMG Publications
WIT Publications
WIT Publications
SMG Publications
Home People Research Activities Publications Teaching Resources
By Class By Topic By Year
By Class By Topic By Year
login
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 Proceedings of the 14th International Conference on Database Theory, ICDT 2011, ACM International Conference Proceedings Series, pages 197-207. ACM Press, March 2011.
© ACM Press 2011

Abstract

Motivated by the renewed interest in semistructured and graph data models, we study a family of XPath-like 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 well-known that the maximal logic is equivalent to the 3-variable fragment of first-order logic over binary relations. We establish a similar characterization for its positive fragment. Also, we discuss the relationship between the 2-variable fragment and the logics we consider. We define appropriate notions of bisimilarity or similarity that capture indistinguishability by these logics, and obtain instance-completeness characterizations in the style of Bancilhon and Paredaens. For some positive languages, we also characterize the graph patterns they can express.


Updated: 2017-03-27