The semijoin algebra

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.