SD321 (Fall 2024)

What is a set

Sets are the data structures of mathematics. They give us a formal language for math that's like a programming language, but much more flexible, while still being precise. They are tremendously useful for data scientists and the kinds of mathematics they need.

A set is a collection of objects (called elements) with two key properties: the elements are unordered within the set, and there are no duplicates. A set is often defined by listing its elements, comma-delimited, with $ \{\} $s.

So, for example, sets $ \{2,\text{cat},3/5\} $ and $ \{\text{cat},3/5,2\} $ are the same, since the order of elements is not meaningful. Similarly, sets $ \{\text{blue},22,\text{gold}\} $ $ \{\text{blue},\text{gold},22,\text{blue}\} $ are the same, since the duplicate "$ \text{blue} $" element is ignored.

Important! Mathematical objects have "type", just like objects in programs, and a set is a type. So, 4 and $ \{4\} $ are different! The first is the number four, and the second is the set whose only element is the number four. So "$ 4 $" is a number and "$ \{4\} $" is a set. They have different type and therefore cannot be the same. By the same reason, $ \{4\} $ and $ \{\{4\}\} $ are not the same. Also by the same reason, $ 0 $ and $ \emptyset $ and "" are all different, because the first is a number, the second is a set, and the third is a string.

Set basics

Definitions: Defining a set by listing its elements or giving an informal description. Ex: $ A = \{17,2.5,-8\} $ or $ B = \{3,5,7,\ldots\} $. The "..." means "and so on following the pattern". This gives us some flexibility!
Element ($ \in $ ): A set consists of elements, and we write "$ a $ is an element of set $ A $" as $ a \in A $. Ex: $ 3 \in \{1,2,3,4\} $, but $ 42 \notin \{1,2,3,4\} $.
Common Sets: There are certain common sets that we use all the time, and they have special symbols: $ \mathbb{N} $ --- the natural numbers (i.e. non-negative integers), $ \mathbb{Z} $ --- the integers, and $ \mathbb{R} $ --- the real numbers. Finally, we have the ever popular empty set $ \{\ \} $, often denoted $ \emptyset $, i.e. the set with no elements.
Formal Descriptions Often we won't define a set by explicitly listing all of its elements --- after all this isn't possible for infinite sets! Instead we write $ \{x \in A \ \big|\ \mbox{$x$ has property $P$}\} $ to mean the set of all elements of $ A $ that satisfy some property $P$. For example, we could define $ \mathbb{N}$ as $ \{x \in \mathbb{Z}\ \big|\ x \geq 0\}$. Note: read the $|$ as "such that". So we read the above as "the set of all integers $x$ such that $x \geq 0$."
Set operators — $ A\cup B$, $A \cap B$, $\overline{A}$, and $A - B$:
- union: $A \cup B = \{ x \ \big|\ x \in A \vee x \in B\}$ Remember: "$ \vee $" means "or" Ex: $\{3,a,\pi\} \cup \{b,\pi,3,4\} = \{3,a,\pi,b,4\}$
- intersection: $A \cap B = \{ x \ \big|\ x \in A \wedge x \in B\}$ Remember: "$\wedge$" means "and" Ex: $\{3,a,\pi\} \cap \{b,\pi,3,4\} = \{3,\pi\}$
- complement: $\overline{A}$ = "the complement of $A$", which is all elements from the "universe" that are not in $A$. This operation only makes sense if there is some underlying notion of "universe". Ex: If the universe is $\{\clubsuit,\diamondsuit,\heartsuit,\spadesuit\}$ then $\overline{\{\diamondsuit,\heartsuit\}} = \{\clubsuit,\spadesuit\}$
- difference: $A - B = \{ x \ \big|\ x \in A \wedge x \notin B\}$ Ex: $\{3,a,\pi\} - \{b,\pi,3,4\} = \{a\}$
Note: If $A$ is a set with a finite number $n$ of elements, we say that the cardinality of $A$, written $|A|$ is $n$.
Subsets, "$A$ is a subset of $B$" means that every element of $A$ is also an element of $B$. So, for example, $\{2,4\}$ is a subset of $\{1,2,3,4\}$, though the other way round doesn't work!

Important! is $\emptyset$ a subset of $\{1,2,3,4\}$? Yes! Think like a mid trying to get out of trouble: can you show me a single element of $\emptyset$ that isn't in $\{1,2,3,4\}$? Nope! Therefore $\emptyset$ must be a subset of $\{1,2,3,4\}$. In fact, for any set $A$, we have $emptyset$ is a subset of $A$. Also note that every set is a subset of itself.
We have nice notations for subset related stuff: $A \subseteq B$ means that $A$ is a subset of $B$. $A \subset B$ means that $A$ is a proper subset of $B$, i.e. $A \neq B$. Ex: $\mathbb{Z} \subset \mathbb{R}$. If $A$ is a set, we denote by $2^A$ the set of all subsets of $A$. Ex: If $A = \{1,2,3\}$, then $2^A = \{ \emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{2,3\}, \{1,3\}, \{1,2,3\} \}$.
Cartesian Product $\times$: One of the most important operations on sets is the "Cartesian Product", which produces the set of all possible pairs of elements from two sets — i.e. all possible ordered pairs whose first component comes from the first set, and second component comes from the second set. Ex: $\mathbb{R} \times \mathbb{R}$ is the set of all ordered pairs of real numbers, i.e. the set of points in the plane! For example, $$\{foo,bar\}\times\{0,1,2\} = \{(foo,0),(bar,0),(foo,1),(bar,1),(foo,2),(bar,2)\}$$ Thus, we compose objects in set theory just like we compose objects in class definitions in Python!!! We use $A^k$ to indicate $A \times A \times \cdots \times A$, $k$-times over. So, for example, 3-diomensional space is $\mathbb{R}^3$.
Operations Over Sets Many operations in mathematics are defined "over a set". For example, if $A = \{1,7,3,5,2\}$ we write $\sum_{x \in A} x^2$ to mean $1^2 + 7^2 + 3^2 + 5^2 + 2^2$. Also, we write $min(A)$ to be the smallest element of $A$. Notice how both of these expressions only make sense because the elments of $A$ are numbers ... after all, if $A$ consisted of characters, then "$+]$" wouldn't make a lot of sense, or if $A$ was a set of people then "smallest" wouldn't make a lot of sense. This is just like Python, where operations (like $+$) only make sense for certain classes. These kinds of operations over sets are like programming, acutally. For example, the cardinality of a set $A$ (denoted $|A|$) can be defined as $|A| = \sum_{x \in A}1$, which is a lot like
```
def cardinality(A):
  k = 0
  for x in A:
    k = k + 1
  return k
```
Unions and Intersections of Many Sets Suppose we have $n$ sets $A_1,\ldots, A_n$. We often write $\bigcup_{i=1}^n A_i$ or $\bigcap_{i=1}^n A_i$ to denote the union or intersection of all of the $A_i$'s. Sometimes we take the union or intersection of an infinite number of objects. For example, let $B_i$ be the set of strings of zeros and ones of length $i$ and with first character one. Then the set of valid representations of binary numbers (so we are not allowing leading zeros here!) is $\{0\} \cup \bigcup_{i=1}^\infty B_i$.
Quantification over the elements of sets: We will be using the quantifiers $\exists$ (there exists) and $\forall$ (for all) a lot in this class. With sets we can restrict the universe from which these quantifiers consider objects. For example, $\forall x \in \mathbb{N}[ x + 1 \gt 0]$ means "for all natural numbers $x$, it holds that $x + 1 \gt 0$", which is (of course) a true statement. However, $\forall x \in \mathbb{Z}[ x + 1 \gt 0]$ is not true. Can you find a counterexample? I.e. a value for $x$ that shows that the formula is not true?

So, how does this relate to databases

A set is a collection of distinct objects. In databases, a set can be thought of as a table and each row represents an element of the set. As an example, a table named Midn where each row contains a student’s information can be considered a set of Midn and each row is an individual element.

Lets now review the results of two SELECT statements.

SELECT Alpha, First, Last FROM Midn;
+--------+--------+-----------+
| Alpha  | First  | Last      |
+--------+--------+-----------+
| 261000 | Eddard | Stark     |
| 261001 | Rob    | Stark     |
| 261002 | Bran   | Stark     |
| 261234 | Tyrian | Lannister |
| 261235 | Cersei | Lannister |
| 261236 | Tywin  | Lannister |
| 261237 | Jaime  | Lannister |
+--------+--------+-----------+
7 rows in set (0.02 sec)

SELECT Alpha, AcYr, Course, EndOfTerm FROM Grades;
+--------+------+--------+-----------+
| Alpha  | AcYr | Course | EndOfTerm |
+--------+------+--------+-----------+
| 261001 | 2023 | NL110  | C         |
| 261002 | 2023 | NL110  | A         |
| 261234 | 2023 | HE111  | B         |
| 261234 | 2023 | HH104  | A         |
| 261234 | 2023 | NL110  | A         |
| 261234 | 2023 | NS101  | B         |
| 261234 | 2023 | SC111  | C         |
+--------+------+--------+-----------+
7 rows in set (0.01 sec)

You can consider any queries we make against a table to be a subset of the table, remember a subset can be the entire table or any smaller combination of the possible elements. If we had performed a query like SELECT * FROM Grades WHERE Course='NL110', then this would have created a subset of the table Grades only showing elements related to NL110.

Remember each row is an element of the larger set (table), and each element is also a subset of the larger set. A single element in our case would be:

+--------+------+--------+-----------+
| Alpha  | AcYr | Course | EndOfTerm |
+--------+------+--------+-----------+
| 261001 | 2023 | NL110  | C         |
+--------+------+--------+-----------+

If we were to JOIN the two tables without specifying what columns we wanted to use, our results would be Cartesian Product (as described above) where the results would be a new set of all possible pairs of the elements of the original two sets.

SELECT Midn.Alpha, First, Last, AcYr, Course, EndOfTerm FROM Midn, Grades;
+--------+--------+-----------+------+--------+-----------+
| Alpha  | First  | Last      | AcYr | Course | EndOfTerm |
+--------+--------+-----------+------+--------+-----------+
| 261237 | Jaime  | Lannister | 2023 | NL110  | C         |
| 261236 | Tywin  | Lannister | 2023 | NL110  | C         |
| 261235 | Cersei | Lannister | 2023 | NL110  | C         |
| 261234 | Tyrian | Lannister | 2023 | NL110  | C         |
| 261002 | Bran   | Stark     | 2023 | NL110  | C         |
| 261001 | Rob    | Stark     | 2023 | NL110  | C         |
| 261000 | Eddard | Stark     | 2023 | NL110  | C         |
| 261237 | Jaime  | Lannister | 2023 | NL110  | A         |
| 261236 | Tywin  | Lannister | 2023 | NL110  | A         |
| 261235 | Cersei | Lannister | 2023 | NL110  | A         |
| 261234 | Tyrian | Lannister | 2023 | NL110  | A         |
| 261002 | Bran   | Stark     | 2023 | NL110  | A         |
| 261001 | Rob    | Stark     | 2023 | NL110  | A         |
| 261000 | Eddard | Stark     | 2023 | NL110  | A         |
| 261237 | Jaime  | Lannister | 2023 | HE111  | B         |
| 261236 | Tywin  | Lannister | 2023 | HE111  | B         |
| 261235 | Cersei | Lannister | 2023 | HE111  | B         |
| 261234 | Tyrian | Lannister | 2023 | HE111  | B         |
| 261002 | Bran   | Stark     | 2023 | HE111  | B         |
| 261001 | Rob    | Stark     | 2023 | HE111  | B         |
| 261000 | Eddard | Stark     | 2023 | HE111  | B         |
| 261237 | Jaime  | Lannister | 2023 | HH104  | A         |
| 261236 | Tywin  | Lannister | 2023 | HH104  | A         |
| 261235 | Cersei | Lannister | 2023 | HH104  | A         |
| 261234 | Tyrian | Lannister | 2023 | HH104  | A         |
| 261002 | Bran   | Stark     | 2023 | HH104  | A         |
| 261001 | Rob    | Stark     | 2023 | HH104  | A         |
| 261000 | Eddard | Stark     | 2023 | HH104  | A         |
| 261237 | Jaime  | Lannister | 2023 | NL110  | A         |
| 261236 | Tywin  | Lannister | 2023 | NL110  | A         |
| 261235 | Cersei | Lannister | 2023 | NL110  | A         |
| 261234 | Tyrian | Lannister | 2023 | NL110  | A         |
| 261002 | Bran   | Stark     | 2023 | NL110  | A         |
| 261001 | Rob    | Stark     | 2023 | NL110  | A         |
| 261000 | Eddard | Stark     | 2023 | NL110  | A         |
| 261237 | Jaime  | Lannister | 2023 | NS101  | B         |
| 261236 | Tywin  | Lannister | 2023 | NS101  | B         |
| 261235 | Cersei | Lannister | 2023 | NS101  | B         |
| 261234 | Tyrian | Lannister | 2023 | NS101  | B         |
| 261002 | Bran   | Stark     | 2023 | NS101  | B         |
| 261001 | Rob    | Stark     | 2023 | NS101  | B         |
| 261000 | Eddard | Stark     | 2023 | NS101  | B         |
| 261237 | Jaime  | Lannister | 2023 | SC111  | C         |
| 261236 | Tywin  | Lannister | 2023 | SC111  | C         |
| 261235 | Cersei | Lannister | 2023 | SC111  | C         |
| 261234 | Tyrian | Lannister | 2023 | SC111  | C         |
| 261002 | Bran   | Stark     | 2023 | SC111  | C         |
| 261001 | Rob    | Stark     | 2023 | SC111  | C         |
| 261000 | Eddard | Stark     | 2023 | SC111  | C         |
+--------+--------+-----------+------+--------+-----------+
49 rows in set (0.00 sec)

Of course this is not what we want to retrieve from the database as all of our students grades were mixed, but it is the effect of what happens when we don't properly join the tables. In reality this is a CROSS JOIN that would be the result of something similar to SELECT * FROM Midn CROSS JOIN Grades;.

What we really wanted to find was the intersection between the two tables, but a traditional set intersection would only show elements of the set (rows in our case) that were identical between the two queries. If we only wanted to find the Alphas this could be accomplished by using INTERSECT in MySQL.

SELECT Alpha FROM Midn INTERSECT SELECT Alpha FROM Grades;
+--------+
| Alpha  |
+--------+
| 261001 |
| 261002 |
| 261234 |
+--------+
3 rows in set (0.00 sec)

In our case, we want to define what fields (or columns) to compare, in essense we are performing a MySQL intersection by running a operation over sets with our two tables.

SELECT Midn.Alpha, First, Last, AcYr, Course, EndOfTerm FROM Midn INNER JOIN Grades USING(Alpha);
+--------+--------+-----------+------+--------+-----------+
| Alpha  | First  | Last      | AcYr | Course | EndOfTerm |
+--------+--------+-----------+------+--------+-----------+
| 261001 | Rob    | Stark     | 2023 | NL110  | C         |
| 261002 | Bran   | Stark     | 2023 | NL110  | A         |
| 261234 | Tyrian | Lannister | 2023 | HE111  | B         |
| 261234 | Tyrian | Lannister | 2023 | HH104  | A         |
| 261234 | Tyrian | Lannister | 2023 | NL110  | A         |
| 261234 | Tyrian | Lannister | 2023 | NS101  | B         |
| 261234 | Tyrian | Lannister | 2023 | SC111  | C         |
+--------+--------+-----------+------+--------+-----------+
7 rows in set (0.00 sec)

We can think of our INNER JOIN as the intersection over our two resulting sets above, $A$ and $B$, and their respective rows $x$ and $y$, performed by the operation over the appropriate columns. $$ C = \sum_{x \in A} \sum_{y \in B} f(x,y,*columns) $$ Again, this action is really just the intersection of the rows of the tables as we are allowing ourselves a bit of leeway in the requirements for the elements (or comparison of the elements) in the set to support intersection, or if you dislike that concept, imagine that the database is finding the proper intersection using the identical columns and then adding the additionally requested columns.

Continuing this thought, when we are comparing these two tables via the Alpha column, it is as if the other columns in the respective tables are dependent on this particular column as if the remaining columns support this column or could be defined by it. This is actually the concept of functional dependency that we will begin exploring in the next lecture.

Problems

Let $A = \{x1, x3, x5, \ldots\}$. Give an element of $A$ other than $x1$, $x3$, and $x5$.
Let $B = \{\{0\},\{1\},\{2\}\}$. True or false, the elements of $B$ are numbers.
Let $U = \{\ a,\ \{a\},\ \{\ \}\ \}$. Write out all the subsets of $U$. Hint: there are eight subsets. Why? $|U|=3$ and for each of the three elements you have two choices: put the element in the subset, or leave it out. This gives $2\cdot 2\cdot 2 = 8$ possible outcomes.
What is the difference between the following:
- INNER JOIN
- OUTER JOIN
- LEFT JOIN
- JOIN
What are the following NATURAL JOIN, CROSS JOIN, and RIGHT JOIN, and why should we avoid these?