Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/8808
Title: | The semijoin algebra | Authors: | LEINDERS, Dirk | Advisors: | VAN DEN BUSSCHE, Jan | Issue Date: | 2008 | Publisher: | UHasselt Diepenbeek | Abstract: | In the 1970s Codd introduced the now standard relational data model, in which a database is a finite collection of relations, where a relation is a finite set of tuples. To express queries in the relational model, Codd introduced the relational algebra (RA) with operators selection (called restriction by Codd), projection, union, difference and join [14]. Since then the relational algebra has been extensively studied [1]. A very important result is that its expressive power is equivalent to the expressive power of f irst-order logic, called relational calculus in database theory [15]. The “semijoin” operator, which is non-primitive in Codd’s relational algebra, selects a set of tuples in one relation that have a joining tuple in another relation. The semijoin operator has also been extensively studied in the past. For example, while computing project-join queries in general is NP-complete in the size of the query and the database, this can be done in polynomial time when the database schema is acyclic [61], a property known to be equivalent to the existence of a semijoin program [11, 13, 12]. Semijoins are often used as part of a query pre-processing phase where dangling tuples are eliminated, i.e., the database is resized to the part that is relevant for answering the query. Another interesting property is that the size of a relation resulting from a semijoin is always linear in the size of the input. Therefore, a query processor will try to use semijoins as often as possible when generating a query plan for a given query (a technique known as “pushing projections” [19]). Also in distributed query processing, semijoins have great importance, because when a database is distributed across several sites, they can help avoid the shipment of many unneeded tuples. | Document URI: | http://hdl.handle.net/1942/8808 | Category: | T1 | Type: | Theses and Dissertations |
Appears in Collections: | PhD theses Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Leinders.pdf | 890.51 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.