ConceptDBISAI-written · not yet proofread

Cartesian Product

Also Cross-Product · Cross Product

The Cartesian product of two tables is the table of all concatenations of a row of the first with a row of the second, so its columns add up and its rows multiply.

Know these firstRelational Model

Definition

For tables $T_1 = (C_1, D_1, R_1)$ and $T_2 = (C_2, D_2, R_2)$ of the Relational Model, the Cartesian product cartesian-product(T1, T2) $= T_1 \times T_2$ is the table $T = (C, D, R)$ with

C = (C_1, C_2), \qquad D = (D_1, D_2), \qquad R = R_1 \times R_2 = \{(r_1, r_2) : r_1 \in R_1,\ r_2 \in R_2\},

where $(X, Y)$ denotes the concatenation of tuples. Hence $|C| = |C_1| + |C_2|$ and $|R| = |R_1| \cdot |R_2|$ (counted with multiplicity).

It lifts the Cartesian product of sets, $S_1 \times \dots \times S_k := \{(s_1, \ldots, s_k) : s_1 \in S_1, \ldots, s_k \in S_k\}$ , to tables. “Cross-product” is used synonymously.

Formula#

For $k$ tables $T_1, \ldots, T_k$ :

\#\mathrm{cols}(T_1 \times \dots \times T_k) = \sum_{i=1}^{k} \#\mathrm{cols}(T_i), \qquad \#\mathrm{rows}(T_1 \times \dots \times T_k) = \prod_{i=1}^{k} \#\mathrm{rows}(T_i).

Cost estimate for query planning, with $T_i$ having $n_i$ rows and $k_i$ columns:

\text{cost}(T_1 \times T_2) \sim n_1 \cdot n_2 \cdot (k_1 + k_2), \qquad \text{rows} = n_1 n_2, \qquad \text{cols} = k_1 + k_2.

This estimate is accurate, since the result of that size has to be written anyway.

Properties#

SQL: the FROM clause with several comma-separated tables denotes their Cartesian product; WHERE then selects rows of it (SQL Query Structure). Without a WHERE clause the full product really must be computed.
Order of products: associative and commutative up to a permutation of the columns, but the cost of intermediate products differs. Combine small tables first, and push selections and projections below the product (Relational Algebra > Equivalences used in query planning).
Empty input: if $|R_1| = 0$ , then $|R_1 \times R_2| = 0$ and the product costs 0.
Join: a selection with an equality between one column of each table on top of a product is a Join, which is computed without materialising the product (hash join, Merge Join). With an arbitrary join condition the worst case falls back to the full product.
Disconnected patterns: a SPARQL query whose triples fall into groups that share no variable translates to a SQL query whose result is the Cartesian product of the groups’ results (SPARQL to SQL Translation).

Example#

ExampleTables

CREATE TABLE gender(id INT, what TEXT);   -- 3 rows: female, male, other
CREATE TABLE handed(id INT, what TEXT);   -- 2 rows: lefty, righty
SELECT * FROM gender, handed;

Result: $2 + 2 = 4$ columns and $3 \cdot 2 = 6$ rows, one per (gender, handedness) pair. Cost estimate $3 \cdot 2 \cdot 4 = 24$ .

Sources#

Slides 03, p. 29–32 (FROM as cross-product, sets)
Slides 04, p. 13–14 (definition, example), p. 26 (cost estimate)
Slides 05, p. 9 (product + select vs. join)
DBIS_VL03 > FROM: the cross-product, DBIS_VL04 > Cartesian product, DBIS_VL04 > Cost and size estimates, DBIS_VL05 > Join operation

Connections

Prerequisites know first1

Relational Model

Mentioned in inline links8

Merge Join
Worst case: if all join values are equal, $n = n_1 n_2$ and the merge join is as expensive as the Cartesian Product. §
Relational Algebra
Cartesian Product $T_1 \times T_2$ : the table $((C_1, C_2), (D_1, D_2), \{(r_1, r_2) : r_1 \in R_1, r_2 \in R_2\})$ . §
Relational Model
The operations on tables (Relational Algebra: projection, selection, Cartesian Product, Join, Grouping) take tables and return a table, so they can be composed into query plans. SQL references columns by name $c_j$ ; the formal operations r… §
SQL Query Structure
| FROM | 1 | the Cartesian Product of all listed tables (or their Join with JOIN … ON) | $\times$ , $\bowtie$ | §
VL03 – Database Basics
Cross-product (Cartesian product) — semantics of the FROM clause; $\#\mathrm{cols}$ add up, $\#\mathrm{rows}$ multiply §
VL04 – Query Planning Basics
Cartesian Product — all row combinations of two tables; $\#\mathrm{cols}$ add up, $\#\mathrm{rows}$ multiply, so plans avoid it §
VL05 – Joins and more SQL
Cartesian Product — all row combinations of two tables, the basis of the join-free formulation §
SQL and Query Planning
Cartesian Product — all row combinations; semantics of FROM, columns add up and rows multiply §
From a query to a result. A query SELECT … FROM … WHERE … is defined by a chain of operations on tables: the FROM tables are combined by the Cartesian Product, the WHERE expression selects rows ( $\sigma$ ), the SELECT list projects columns… §

Search in these mentions →