Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/1426
Title: | The Semijoin algebra | Authors: | VAN DEN BUSSCHE, Jan | Issue Date: | 2006 | Publisher: | Springer-Verlag Berlin | Source: | Dix, J. & Hegner, S.J. (Ed.) Foundations of Information and Knowledge Systems, Proceedings. p. 1-1. | Series/Report: | Lecture Notes in Computer Science | Series/Report no.: | 3861 | 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. | Keywords: | relational algebra, join, semijoin | Document URI: | http://hdl.handle.net/1942/1426 | ISBN: | 0302-9743 | DOI: | 10.1007/11663881_1 | ISI #: | 000235837300001 | Category: | C1 | Type: | Proceedings Paper | Validations: | ecoom 2007 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
VDBUJ_bu.pdf | Peer-reviewed author version | 27.04 kB | Adobe PDF | View/Open |
Page view(s)
14
checked on Sep 7, 2022
Download(s)
20
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.