Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/4137
Full metadata record
DC FieldValueLanguage
dc.contributor.authorLEINDERS, Dirk-
dc.contributor.authorVAN DEN BUSSCHE, Jan-
dc.date.accessioned2007-12-11T08:40:40Z-
dc.date.available2007-12-11T08:40:40Z-
dc.date.issued2007-
dc.identifier.citationJOURNAL OF COMPUTER AND SYSTEM SCIENCES, 73(4). p. 538-549-
dc.identifier.issn0022-0000-
dc.identifier.urihttp://hdl.handle.net/1942/4137-
dc.description.abstractWe 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.-
dc.language.isoen-
dc.publisherACADEMIC PRESS INC ELSEVIER SCIENCE-
dc.subject.otherdatabase; relational algebra; Semijoin algebra; complexity-
dc.titleOn the complexity of division and set joins in the relational algebra-
dc.typeJournal Contribution-
dc.identifier.epage549-
dc.identifier.issue4-
dc.identifier.spage538-
dc.identifier.volume73-
local.format.pages12-
local.bibliographicCitation.jcatA1-
dc.description.notesHasselt Univ, B-3590 Diepenbeek, Belgium. Transnatl Univ Limburg, B-3590 Diepenbeek, Belgium.LEINDERS, D, Hasselt Univ, B-3590 Diepenbeek, Belgium.dirk.leinders@uhasselt.be-
local.type.refereedRefereed-
local.type.specifiedArticle-
dc.bibliographicCitation.oldjcatA1-
dc.identifier.doi10.1016/j.jcss.2006.10.011-
dc.identifier.isi000246813700002-
item.fullcitationLEINDERS, Dirk & VAN DEN BUSSCHE, Jan (2007) On the complexity of division and set joins in the relational algebra. In: JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 73(4). p. 538-549.-
item.validationecoom 2008-
item.accessRightsClosed Access-
item.fulltextNo Fulltext-
item.contributorLEINDERS, Dirk-
item.contributorVAN DEN BUSSCHE, Jan-
crisitem.journal.issn0022-0000-
crisitem.journal.eissn1090-2724-
Appears in Collections:Research publications
Show simple item record

SCOPUSTM   
Citations

15
checked on Dec 4, 2025

WEB OF SCIENCETM
Citations

9
checked on Dec 6, 2025

Google ScholarTM

Check

Altmetric


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