Abstract
When we replace, in the classical relational algebra, the join operator by the semijoin operator, we obtain what we call the semijoin algebra. We will show that, when only equi-joins are used, the semijoin algebra is equivalent with the guarded fragment of first-order logic, and thus it inherits many of the nice properties of the latter logic. When more general theta-joins are used, however, we move outside the realm of guarded logics, and we will show how the notion of guarded bisimilarity can be extended accordingly. Last but not least, we show how the semijoin algebra can be used as a tool to investigate the complexity of queries expressed in the relational algebra, where we are mainly interested in whether or not a relational algebra expression for the query needs to produce intermediate results of nonlinear size. For example, we will show that the division operation cannot be expressed by a linear relational algebra expression.
This talk is a survey of work done in collaboration with Dirk Leinders, Jerzy Tyszkiewicz, and Maarten Marx.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Leinders, D., Marx, M., Tyszkiewicz, J., Van den Bussche, J.: The semijoin algebra and the guarded fragment. Journal of Logic, Language and Information 14, 331–343 (2005)
Leinders, D., Van den Bussche, J.: On the complexity of division and set joins in the relational algebra. In: Proceedings 24th ACM Symposium on Principles of Database Systems, pp. 76–83. ACM Press, New York (2005)
Leinders, D., Tyszkiewicz, J., Van den Bussche, J.: On the expressive power of semijoin queries. Information Processing Letters 91, 93–98 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Van den Bussche, J. (2006). The Semijoin Algebra. In: Dix, J., Hegner, S.J. (eds) Foundations of Information and Knowledge Systems. FoIKS 2006. Lecture Notes in Computer Science, vol 3861. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11663881_1
Download citation
DOI: https://doi.org/10.1007/11663881_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-31782-1
Online ISBN: 978-3-540-31784-5
eBook Packages: Computer ScienceComputer Science (R0)