Relation - Data Operator (Relational Algebra)

1 - About

Relational algebra defines the relational database through a set of data operators (select, filter, join, sort, union, etc.) that defines an intermediate format for query planning/optimization.

Merge with Sql Engine - Relational Operator (Data operations|Execution Plan Steps) ?

Relational algebra is an extension to mathematical set theory, it was devised by E.F. Code (IBM) in 1970.


Programs that manipulate tabular data exhibit an algebraic structure allowing reasoning and manipulation independently of physical data representation.

All operations on a table return a table. The operation can then be chained together.

Relational algebra expressions dictate how to achieve an answer by giving what operations to do and in what order to do them. A declarative language only expresses conditions that must be met in order for a result to be an answer, not how to get that answer.

For instance, SQL is the what not the how. It's clear what we want unclear how to get it

Every query returns a table. The language is “algebraically closed” A view is stored as an algebraic closure so it can be optimized when used with queries.

3 - Order

By design, query results in relational algebra are unordered. Repeating the same query multiple times is not guaranteed to return results in the same order. Similarly, database-backed relational data also do not guarantee row order.

4 - Relation Operator Algebra

Type Name Symbol Sql Operator
Normal select, Selection <math>\sigma</math> of s
Normal project <math>\pi</math>
Normal join <math>\Join</math>
Normal union <math>\cup</math> union (without duplicates)
of union all (with duplicates)
Normal intersection <math>\cap</math>
Normal difference - except, minus
Extended Grouping and aggregating g
Extended Duplicate elimination d
Extended Sorting t

4.1 - Intersection

  • Derived operator using minus

<math> R1 \cap R2 = R1 - ( R1 - R2 ) </math>

This expression <math>( R1 - R2 )</math> returns anything that is only in R1

  • Derived using join

<math> R1 \cap R2 = R1 x R2 </math>

4.2 - Selection

condition: =, <, >, =<, >=, <>, …

4.3 - Project

A project operator keeps only a set of columns (in other words eliminates the others).

4.4 - Cross Product

<math>R1 x R2</math>

The size of this cross-join is then the size of R1 multiplied by the size of R2.

Find all pairs of similar images/tweets/songs: Compute the cross product, then compute a similarity function f(x,,x2) for every possible pair

4.5 - Equi-join

Equi-join is a join where the condition is an equality.

Equality Notation:

ON R1.A = R2.A

Cross product notation:

R1.A = R2.A

4.6 - Theta-join

A theta-join is a difficult join where generally the condition is not a equality. Band join or range join.

It's not because you don't have any join key in the sql that you don't have a join physically.

  • Example 1: Find all the hospitals within 5 miles of a school

FROM hospitals h, schools s
distance(h.location,s.location) < 5
  • Example 2: Find all user clicks made within 5 seconds of page load

FROM Clicks c, PageLoads p
abs(c.click_time - p.load_time) < 5

5 - Bag vs Set

Relational Algebra has two semantics:

  • Set semantics = standard Relational Algebra
  • Bag semantics = extended Relational Algebra

Rule of thumb:

  • Every paper will assume set semantics
  • Every implementation will assume bag semantics

6 - Algebraic Optimization

7 - Equivalent logical expressions with different costs

8 - Documentation / Reference

data/type/relation/operator/operator.txt · Last modified: 2018/06/30 11:25 by gerardnico