Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/954
Title: On the complexity of division and set joins in the relational algebra
Authors: LEINDERS, Dirk 
VAN DEN BUSSCHE, Jan 
Issue Date: 2005
Publisher: ACM
Source: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. p. 76-83.
Abstract: We show that any expression of the relational division operator in the relational algebra with union, difference, projection, selection, and equijoins, must produce intermediate results of quadratic size. To prove this result, we show a dichotomy theorem about intermediate sizes of relational algebra expressions (they are either all linear, or at least one is quadratic); we link linear relational algebra expressions to expressions using only semijoins instead of joins; and we link these semijoin algebra expressions to the guarded fragment of first-order logic.
Document URI: http://hdl.handle.net/1942/954
Link to publication: http://doi.acm.org/10.1145/1065167.1065178
ISBN: 1-59593-062-0
Category: C1
Type: Proceedings Paper
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
onthecomplexity.pdf148.53 kBAdobe PDFView/Open
Show full item record

Page view(s)

62
checked on May 18, 2022

Download(s)

196
checked on May 18, 2022

Google ScholarTM

Check

Altmetric


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