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, S. Vansummeren, and Y. Wu. The Impact of Transitive Closure on the Boolean Expressiveness of Navigational Query Languages on Graphs. In Proceedings of the 7th International Symposium on Foundations of Information and Knowledge Systems, volume 7153 of Lecture Notes in Computer Science, pages 124-143. Springer, 2012.
© Springer 2012

Abstract

Several established and novel applications motivate us to study the expressive power of navigational query languages on graphs, which represent binary relations. Our basic language has only the operators union and composition, together with the identity relation. Richer languages can be obtained by adding other features such as other set operators, projection and coprojection, converse, and the diversity relation. In this paper, we show that, when evaluated at the level of boolean queries with an unlabeled input graph (i.e., a single relation), adding transitive closure to the languages with coprojection adds expressive power, while this is not the case for the basic language to which none, one, or both of projection and the diversity relation are added. In combination with earlier work, these results yield a complete understanding of the impact of transitive closure on the languages under consideration.


Updated: 2017-03-27