Ordered tuples, Cartesian product and its size; a relation as a set of tuples

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. A = {1,2,3,4}, B = {3,4,5}. What is A ∩ B and A − B? from Lesson 0.2.1
2. How many subsets does a 4-element set have? from Lesson 0.2.1
3. What is the difference between the conceptual and the internal schema? from Lesson 0.1.3

1 · The Hook

A set does not care about order: {Asha, CS} = {CS, Asha}. But a student record must care: "name = Asha, dept = CS" is not the same as "name = CS, dept = Asha". To build tables we need ordered collections, called tuples, and a way to build every possible combination of values, called the Cartesian product. With these two ideas we can say exactly what a table is.

2 · Predict First

Names = {Asha, Bhavin, Chirag} and Depts = {CS, EE}. How many different (name, dept) pairs can be formed? Is (Asha, CS) the same pair as (CS, Asha)?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

6 pairs: 3 names × 2 depts. And no: in a pair, order matters, so (Asha, CS) ≠ (CS, Asha).

Ordered tuples

An ordered pair (a, b) has a first and a second component. (a, b) = (c, d) only if a = c and b = d. So (1, 2) ≠ (2, 1).

An n-tuple (a₁, a₂, …, aₙ) has n components in a fixed order. (1, Asha, CS, 9.1) is a 4-tuple. Unlike a set, a tuple may repeat values: (CS, CS) is a valid pair.

Cartesian product

The Cartesian product A × B is the set of all ordered pairs whose first component comes from A and second from B:

A × B = {(a, b) | a ∈ A and b ∈ B}

Example: {1, 2} × {x, y} = {(1, x), (1, y), (2, x), (2, y)}.

Size: |A × B| = |A| × |B|. For n sets: |D₁ × D₂ × … × Dₙ| = |D₁| × |D₂| × … × |Dₙ|.

A × B ≠ B × A in general (the pairs are reversed), though both have the same size. If either set is empty, the product is empty.

A relation is a set of tuples

A domain is a set of allowed values for one column: Rolls = {1, 2, 3}, Names = {Asha, Bhavin, Chirag}, Depts = {CS, EE}.

Rolls × Names × Depts contains every possible (roll, name, dept) triple: 3 × 3 × 2 = 18 of them. The college's actual student data is only some of these triples, for example {(1, Asha, CS), (2, Bhavin, EE), (3, Chirag, CS)}.

So mathematically, a relation on domains D₁, …, Dₙ is a subset of D₁ × D₂ × … × Dₙ. This is the formal definition of a table that Phase 2 builds on. Because a relation is a set, it has no duplicate tuples and no order of tuples. Because each element is a tuple, the order of components (columns) is fixed by the schema.

Counting relations

How many different relations are possible on given domains? Each of the N = |D₁| × … × |Dₙ| possible tuples is either in or out of the relation, so the number of possible relations is the number of subsets: 2^N.

4 · Visual

{1, 2} × {x, y, z}                      |A × B| = 2 × 3 = 6

          x        y        z
   1   (1,x)    (1,y)    (1,z)
   2   (2,x)    (2,y)    (2,z)

A relation is a chosen subset of this grid, for example {(1,x), (2,z)}.

STUDENT as a set of 3 triples chosen from the 18 triples of Rolls × Names × Depts.

5 · Worked Examples

Example 1 Easy

A = {a, b, c}, B = {1, 2}. List A × B and give |A × B| and |B × A|.

Solution

A × B = {(a,1), (a,2), (b,1), (b,2), (c,1), (c,2)}; |A × B| = 3 × 2 = 6; |B × A| is also 6, but its pairs are reversed, e.g. (1, a).

Example 2 Medium

Domains: roll ∈ {1..10}, dept ∈ {CS, EE, ME}, year ∈ {1, 2, 3, 4}. How many distinct (roll, dept, year) tuples are possible?

Solution

10 × 3 × 4 = 120.

Example 3 GATE

How many different relations can be defined on attribute domains of sizes 2 and 3 (two columns)? Include the empty relation.

Solution

Possible tuples: 2 × 3 = 6. Each is in or out: 2⁶ = 64 relations.

8 · Connect the Dots

Lesson 0.2.1 gave sets; this lesson made their elements ordered and defined a relation as a subset of a Cartesian product. Next: the logic used to describe which tuples are ticked (AND, OR, NOT, "for all", "there exists"), the language of WHERE clauses and of relational calculus.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Cartesian product

Numerical answer: ________

Q2 · MCQ · 1 mark(s) — Tuples

Which is true?

1. (A) (1, 1) is not a valid pair
2. (B) {1, 2} = {2, 1}
3. (C) {1, 1} has two elements
4. (D) (1, 2) = (2, 1)

Q3 · NAT · 2 mark(s) — Counting relations

Two attributes have domains of sizes 2 and 2. How many relations (subsets of the product, including empty) are possible?

Numerical answer: ________

Q4 · MCQ · 1 mark(s) — Relation definition

A relation on domains D₁, D₂, D₃ is:

1. (A) a list of tuples that may contain repeats
2. (B) any subset of D₁ × D₂ × D₃
3. (C) D₁ ∪ D₂ ∪ D₃
4. (D) exactly D₁ × D₂ × D₃

Q5 · NAT · 1 mark(s) — Product size

D₁ = {1,2,3}, D₂ = {x,y}, D₃ = ∅. What is |D₁ × D₂ × D₃|?

Numerical answer: ________

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

ordered pairn-tupleCartesian product ×|A × B| = |A|·|B|domain (set of allowed values)relation as a subset of a productnumber of relations 2^N