Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/954
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | LEINDERS, Dirk | - |
dc.contributor.author | VAN DEN BUSSCHE, Jan | - |
dc.date.accessioned | 2006-05-12T11:49:45Z | - |
dc.date.available | 2006-05-12T11:49:45Z | - |
dc.date.issued | 2005 | - |
dc.identifier.citation | Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. p. 76-83. | - |
dc.identifier.isbn | 1-59593-062-0 | - |
dc.identifier.uri | http://hdl.handle.net/1942/954 | - |
dc.description.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. | - |
dc.format.extent | 152097 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.language.iso | en | - |
dc.publisher | ACM | - |
dc.title | On the complexity of division and set joins in the relational algebra | - |
dc.type | Proceedings Paper | - |
local.bibliographicCitation.conferencedate | 2005 | - |
local.bibliographicCitation.conferencename | Symposium on Principles of Database Systems | - |
local.bibliographicCitation.conferenceplace | Baltimore, Maryland | - |
dc.identifier.epage | 83 | - |
dc.identifier.spage | 76 | - |
local.bibliographicCitation.jcat | C1 | - |
local.type.specified | Proceedings Paper | - |
dc.bibliographicCitation.oldjcat | C2 | - |
dc.identifier.url | http://doi.acm.org/10.1145/1065167.1065178 | - |
local.bibliographicCitation.btitle | Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems | - |
item.accessRights | Open Access | - |
item.contributor | LEINDERS, Dirk | - |
item.contributor | VAN DEN BUSSCHE, Jan | - |
item.fulltext | With Fulltext | - |
item.fullcitation | LEINDERS, Dirk & VAN DEN BUSSCHE, Jan (2005) On the complexity of division and set joins in the relational algebra. In: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. p. 76-83.. | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
onthecomplexity.pdf | 148.53 kB | Adobe PDF | View/Open |
Page view(s)
90
checked on Nov 7, 2023
Download(s)
394
checked on Nov 7, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.