§ 2.7Module 2

Relational-Algebra Operations by MapReduce

On this page

2.7 Relational-Algebra Operations by MapReduce

Recall first

For a relation R, which operations can be done independently per tuple? Which operations require tuples with the same value to meet at a reducer?

First principles

Treat each input tuple as a key-value record. A MapReduce job implements relational algebra by choosing what the mapper emits as the key and what the reducer combines. The following algorithms follow the MapReduce relational-operations treatment in Mining of Massive Datasets.

Assume set semantics below unless stated; real files often contain duplicates, so add a deduplication step when the algebra requires sets.

Selection: σ_condition(R)

A mapper tests each tuple and emits it only if the predicate is true. No reducer is required:

map(tuple t): if t.price > 100: emit(t, null)

This is embarrassingly parallel and supports data-local filtering.

Projection: π_attributes(R)

A mapper removes unneeded attributes and emits the projected tuple. To enforce set semantics, use the projected tuple as a key and deduplicate in a reducer (or rely on a distinct-capable downstream stage):

map((id, city, amount)): emit(city, null)
reduce(city, values): emit(city)

Union: R ∪ S

Map every tuple from either relation to the tuple itself as key; reduce once per key and emit it. The source relation can be a tag in the value if provenance is needed.

Intersection: R ∩ S

Map a tuple from R as (tuple, R) and from S as (tuple, S). The reducer emits the tuple only if both tags occur.

Difference: R − S

Use the same tags. The reducer emits the tuple only if R occurs and S does not.

Worked trace

Let R={(a,1),(b,2)} and S={(b,2),(c,3)}. For intersection/difference:

map R: ((a,1),R), ((b,2),R)
map S: ((b,2),S), ((c,3),S)

Grouped values:

(a,1) -> [R]
(b,2) -> [R,S]
(c,3) -> [S]

Reducers emit:

R ∪ S = {(a,1),(b,2),(c,3)}
R ∩ S = {(b,2)}
R − S = {(a,1)}

The same “key is the rendezvous” idea powers all three.

Join connection

A join is not explicitly named in this syllabus item, but the same pattern explains it. For R(A,B) joined with S(B,C), map R tuple (a,b) to key b tagged R, and S tuple (b,c) to key b tagged S; the reducer forms compatible pairs. This is a syllabus-aligned supplement, useful because relational operations are often examined together.

Assumptions and trade-offs

Exercise — revealed answer

Exercise: Implement S − R for the trace above using tags. Which grouped keys survive?

Answer: Emit from S only when the grouped values contain S but not R; (c,3) survives. (b,2) is removed because it has both tags, and (a,1) is absent from S.

Exam lens

Use a table: selection = filter in map; projection = reshape (plus deduplicate if needed); union = key tuple, emit; intersection = require both tags; difference = require left tag and reject right tag. State the set/bag assumption.

Rapid revision checklist

Key takeaways

  1. Relational algebra maps cleanly to key design and reducer predicates.
  2. Independent tuple filtering is cheap; cross-tuple equality requires grouping.
  3. Correct answers state whether duplicates are allowed and what tuple equality means.

Sources