The impact of transitive closure on the Boolean expressiveness of navigational query languages on graphs

G.H.L. Fletcher, M. Gyssens, D. Leinders, J. Van den Bussche, D. Van Gucht, S. Vansummeren, Y. Wu

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationFoundations of Information and Knowledge Systems (7th International Symposium, FoIKS 2012, Kiel, Germany, March 5-9, 2012. Proceedings)
EditorsT. Lukasiewicz, A. Sali
Place of PublicationBerlin
PublisherSpringer
Pages124-143
ISBN (Print)978-3-642-28471-7
DOIs
Publication statusPublished - 2012

Publication series

NameLecture Notes in Computer Science
Volume7153
ISSN (Print)0302-9743

Fingerprint

Query languages
Chemical analysis

Cite this

Fletcher, G. H. L., Gyssens, M., Leinders, D., Van den Bussche, J., Van Gucht, D., Vansummeren, S., & Wu, Y. (2012). The impact of transitive closure on the Boolean expressiveness of navigational query languages on graphs. In T. Lukasiewicz, & A. Sali (Eds.), Foundations of Information and Knowledge Systems (7th International Symposium, FoIKS 2012, Kiel, Germany, March 5-9, 2012. Proceedings) (pp. 124-143). (Lecture Notes in Computer Science; Vol. 7153). Berlin: Springer. https://doi.org/10.1007/978-3-642-28472-4_8
Fletcher, G.H.L. ; Gyssens, M. ; Leinders, D. ; Van den Bussche, J. ; Van Gucht, D. ; Vansummeren, S. ; Wu, Y. / The impact of transitive closure on the Boolean expressiveness of navigational query languages on graphs. Foundations of Information and Knowledge Systems (7th International Symposium, FoIKS 2012, Kiel, Germany, March 5-9, 2012. Proceedings). editor / T. Lukasiewicz ; A. Sali. Berlin : Springer, 2012. pp. 124-143 (Lecture Notes in Computer Science).
@inproceedings{fcc164d3630c497181e8c537538a456e,
title = "The impact of transitive closure on the Boolean expressiveness of navigational query languages on graphs",
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.",
author = "G.H.L. Fletcher and M. Gyssens and D. Leinders and {Van den Bussche}, J. and {Van Gucht}, D. and S. Vansummeren and Y. Wu",
year = "2012",
doi = "10.1007/978-3-642-28472-4_8",
language = "English",
isbn = "978-3-642-28471-7",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "124--143",
editor = "T. Lukasiewicz and A. Sali",
booktitle = "Foundations of Information and Knowledge Systems (7th International Symposium, FoIKS 2012, Kiel, Germany, March 5-9, 2012. Proceedings)",
address = "Germany",

}

Fletcher, GHL, Gyssens, M, Leinders, D, Van den Bussche, J, Van Gucht, D, Vansummeren, S & Wu, Y 2012, The impact of transitive closure on the Boolean expressiveness of navigational query languages on graphs. in T Lukasiewicz & A Sali (eds), Foundations of Information and Knowledge Systems (7th International Symposium, FoIKS 2012, Kiel, Germany, March 5-9, 2012. Proceedings). Lecture Notes in Computer Science, vol. 7153, Springer, Berlin, pp. 124-143. https://doi.org/10.1007/978-3-642-28472-4_8

The impact of transitive closure on the Boolean expressiveness of navigational query languages on graphs. / Fletcher, G.H.L.; Gyssens, M.; Leinders, D.; Van den Bussche, J.; Van Gucht, D.; Vansummeren, S.; Wu, Y.

Foundations of Information and Knowledge Systems (7th International Symposium, FoIKS 2012, Kiel, Germany, March 5-9, 2012. Proceedings). ed. / T. Lukasiewicz; A. Sali. Berlin : Springer, 2012. p. 124-143 (Lecture Notes in Computer Science; Vol. 7153).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - The impact of transitive closure on the Boolean expressiveness of navigational query languages on graphs

AU - Fletcher, G.H.L.

AU - Gyssens, M.

AU - Leinders, D.

AU - Van den Bussche, J.

AU - Van Gucht, D.

AU - Vansummeren, S.

AU - Wu, Y.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-28472-4_8

DO - 10.1007/978-3-642-28472-4_8

M3 - Conference contribution

SN - 978-3-642-28471-7

T3 - Lecture Notes in Computer Science

SP - 124

EP - 143

BT - Foundations of Information and Knowledge Systems (7th International Symposium, FoIKS 2012, Kiel, Germany, March 5-9, 2012. Proceedings)

A2 - Lukasiewicz, T.

A2 - Sali, A.

PB - Springer

CY - Berlin

ER -

Fletcher GHL, Gyssens M, Leinders D, Van den Bussche J, Van Gucht D, Vansummeren S et al. The impact of transitive closure on the Boolean expressiveness of navigational query languages on graphs. In Lukasiewicz T, Sali A, editors, Foundations of Information and Knowledge Systems (7th International Symposium, FoIKS 2012, Kiel, Germany, March 5-9, 2012. Proceedings). Berlin: Springer. 2012. p. 124-143. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-28472-4_8