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 Oct 14, 2024
Page view(s)
72
checked on Jul 31, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.