Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/4137
Title: On the complexity of division and set joins in the relational algebra
Authors: LEINDERS, Dirk 
VAN DEN BUSSCHE, Jan 
Issue Date: 2007
Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE
Source: JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 73(4). p. 538-549
Abstract: We show that any expression of the relational division operator in the relational algebra with union, difference, projection, selection, constant-tagging, and joins, 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), and we link linear relational algebra expressions to expressions using only semijoins instead of joins. (c) 2006 Elsevier Inc. All rights reserved.
Notes: Hasselt Univ, B-3590 Diepenbeek, Belgium. Transnatl Univ Limburg, B-3590 Diepenbeek, Belgium.LEINDERS, D, Hasselt Univ, B-3590 Diepenbeek, Belgium.dirk.leinders@uhasselt.be
Keywords: database; relational algebra; Semijoin algebra; complexity
Document URI: http://hdl.handle.net/1942/4137
ISSN: 0022-0000
e-ISSN: 1090-2724
DOI: 10.1016/j.jcss.2006.10.011
ISI #: 000246813700002
Category: A1
Type: Journal Contribution
Validations: ecoom 2008
Appears in Collections:Research publications

Show full item record

SCOPUSTM   
Citations

11
checked on Sep 2, 2020

WEB OF SCIENCETM
Citations

8
checked on May 21, 2022

Page view(s)

50
checked on May 26, 2022

Google ScholarTM

Check

Altmetric


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