Ch 4. Relations
4.3 Pairs and Tuples and Cartesian Products
A collection of two elements written in order is called an ordered pair. For two elements [latex]a[/latex] and [latex]b[/latex], we write [latex](a, b)[/latex]. Note the importance of the order of the elements:
[latex](a, b) \neq (b, a) \quad \text{ unless } a = b[/latex]
The Cartesian product of two sets is the set of all possible ordered pairs from these sets. If the first element comes from the set [latex]A[/latex] and the second element comes from the set [latex]B[/latex], then we write
[latex]A \times B = \{ (a, b) \mid a \in A, b \in B \}[/latex]
Example 4.55
Let [latex]A = \{ 1, 2 \}[/latex] and [latex]B = \{ x, y \}[/latex]. Then [latex]A \times B = \{ (1, x), (1, y), (2, x), (2, y) \}[/latex]. The number of elements in [latex]A \times B[/latex] is [latex]|A| \times |B| = 2 \times 2 = 4[/latex].
If we have a finite ordered list of elements, we refer to it as a tuple. An n-tuple is a tuple with exactly [latex]n[/latex] elements. For example, a 2-tuple is an ordered pair [latex](a, b)[/latex], a 3-tuple is [latex](a, b, c)[/latex], and a 4-tuple is [latex](a, b, c, d)[/latex]. Tuples are used to represent structured data, such as database records or function arguments.
Example 4.56
Properties of Cartesian Products
Non-Commutativity: In general, [latex]A \times B \neq B \times A[/latex], because the order of elements in the pairs is reversed.
Example 4.57
Let [latex]A = \{ 1 \}[/latex] and [latex]B = \{ x \}[/latex]. Then [latex]A \times B = \{ (1, x) \}[/latex] and [latex]B \times A = \{ (x, 1) \}[/latex]. These are not the same.
Distributivity over Union: The Cartesian product distributes over union.
[latex]A \times (B \cup C) = (A \times B) \cup (A \times C)[/latex]
Example 4.58
Let [latex]A = \{ 1 \}[/latex], [latex]B = \{ x \}[/latex], [latex]C = \{ y \}[/latex]. Then
[latex]A \times (B \cup C) = \{ (1, x), (1, y) \}[/latex]
and
[latex](A \times B) \cup (A \times C) = \{ (1, x) \} \cup \{ (1, y) \} = \{ (1, x), (1, y) \}[/latex]
Empty Set: If either set is empty, the Cartesian product is also empty.
[latex]A \times \emptyset = \emptyset, \quad \emptyset \times B = \emptyset[/latex]
Example 4.59
Let [latex]A = \{ 1, 2 \}[/latex] and [latex]B = \emptyset[/latex]. Then [latex]A \times B = \emptyset[/latex].
Cardinality: If [latex]|A| = m[/latex] and [latex]|B| = n[/latex], then [latex]|A \times B| = m \cdot n[/latex].
Example 4.60
If [latex]A = \{ 1, 2, 3 \}[/latex] and [latex]B = \{ x, y \}[/latex], then [latex]|A \times B| = 3 \times 2 = 6[/latex].
Use in Database Schemas and Data Structures
In Example 4.56, we represented a student’s information as a 4-tuple. In a relational database, this 4-tuple would be a row in a table, and the table would be a set of 4-tuples. In general, a row in a table is an n-tuple. The structure of the student’s 4-tuple consists of a 9-digit number, two strings, and a single decimal number, and is defined by a schema. A schema defines the structure of tuples by specifying the number and types of attributes.
Example 4.61
In programming, tuples are used to group related values. For example, in pseudocode:
DECLARE student AS TUPLE
SET student TO (100112345, “Cloud Strife”, “Marketing”, 3.8)
This tuple represents the student record in Example 4.56.
Real-World Example 4.3: E-Commerce Orders
In an online store, each order can be represented as a 4-tuple:
(OrderID, CustomerID, ProductID, Quantity)
This tuple is an element of the Cartesian product
Orders [latex]\subseteq[/latex] OrderIDs x CustomerIDs x ProductIDs x Quantities
