Please use this identifier to cite or link to this item:
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:
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 SizeFormat 
VDBUJ_bu.pdfPostprint27.04 kBAdobe PDFView/Open
Show full item record

Page view(s)

checked on May 17, 2022


checked on May 17, 2022

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.