Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/1426

Title: The Semijoin algebra
Issue Date: 2006
Publisher: Springer-Verlag Berlin
Citation: Dix, J. & Hegner, S.J. (Ed.) Foundations of Information and Knowledge Systems, Proceedings. p. 1-1.
Series/Report: Lecture Notes in Computer Science, 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.
URI: http://hdl.handle.net/1942/1426
DOI: 10.1007/11663881_1
ISI #: 000235837300001
ISBN: 0302-9743
ISSN: 0302-9743
Category: C1
Type: Proceedings Paper
Validation: ecoom, 2007
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Postprint27.04 kBAdobe PDF

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