Learning the foundations of any profession will help you better understand your job and in turn further your career—and database administration is no exception. Database professionals who write a lot of T-SQL code should explore T-SQL’s foundations. SQL Server’s T-SQL is based on standard SQL, which is based on the relational model, which in turn is based on mathematical foundations (i.e., set theory and predicate logic). In this article I discuss a fundamental topic in set theory: the properties of relations on sets. I present T-SQL code that you can use to identify those properties; however, I encourage you to write your own T-SQL code to determine whether a relation has a particular property, before you use my code.
Sets and Relations
Georg Cantor, the creator of set theory, defines a set as “any collection M into a whole of definite, distinct objects m (which are called the “elements” of M) of our perception or of our thought.” The elements of a set can be anything: people, numbers—even sets themselves. The symbols ∈ and ∉ are operators that express set membership and nonmembership, respectively. So the notation x ∈ V means that x is a member of V, and the notation x ∉ V means that x isn’t a member of V.
A binary relation on a set is a collection of ordered pairs of elements of the set. That is, for a set of elements V = {a, b, c}, a binary relation R on the set V is any subset of the ordered pairs in the Cartesian product V × V = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}. So, for example, say that R = {(a, b), (b, c), (a, c)}. R is a valid relation on V. You can say that a is related to b by R. Suppose that R = {(a, b), (b, c), (c, d)}. R isn’t a valid relation on V because the ordered pair (c, d) isn’t a member of the Cartesian product V × V. Note that the order of elements in a set isn’t important. V can be expressed as {a, b, c} as well as {b, a, c}, and so on. However, the order of an ordered pair—for example, (a, b)—is important, so (a, b) ≠ (b, a).
As a more tangible example of a binary relation on a set, suppose that F is the set of my family members {Itzik, Mickey, Ina, Mila, Gabi}. Mickey is my twin brother; Ina is my elder sister; Mila is my mom; and Gabi is my dad. An example of a relation R on the set F would be “is a brother of.” The members of this relation are {(Itzik, Mickey), (Mickey, Itzik), (Itzik, Ina), (Mickey, Ina)}. Observe that the ordered pair (Itzik, Ina) appears in R, but (Ina, Itzik) doesn’t. Although I’m a brother of Ina, she’s not my brother.
Properties of Relations on Sets
Now that we have some background about sets and relations, let’s proceed to the focus of the article—properties of relations on sets. For sample data, use the code in Listing 1 to create the tables V and R. V represents a set, and R represents a binary relation on V. Use the code in Listing 2 to create the procedure ClearTables, which you can use to clear both tables before populating them with new sample data. Use the code in Listing 3, Listing 4, and Listing 5 to populate the tables with different sets of sample data for your tests (call the sets Sample Data 1, 2, and 3, respectively).
Reflexive. A relation R on a set V is reflexive if whenever v ∈ V (meaning, v is a member of V), then (v, v) ∈ R (meaning, (v, v) belongs to R). A relation R on a set V is not reflexive if there exists some v ∈ V, such that (v, v) ∉ R. Consider again the set of my family members F. The relation “has the same age as” on F is reflexive because every person in the set has the same age as himself or herself. The members of this relation are {(Itzik, Itzik), (Itzik, Mickey), (Mickey, Mickey), (Mickey, Itzik), (Ina, Ina), (Mila, Mila), (Gabi, Gabi)}.
Let’s proceed to writing a T-SQL query against the tables V and R (representing a set and a relation on the set) to check whether the relation R on the set V is reflexive:
SELECT
CASE
WHEN EXISTS
(SELECT v, v FROM dbo.V
EXCEPT
SELECT r1, r2 FROM dbo.R)
THEN 'no'
ELSE 'yes'
END AS reflexive
The first query in the EXCEPT set operation returns a set with an ordered pair (v, v) for every row in V. The second query returns a set with an ordered pair (r1, r2) for every row in R. The EXCEPT set operation returns all ordered pairs that appear in the first set but not the second. The EXISTS predicate checks whether at least one row exists in the result of the set operation. If at least one such row exists, the CASE expression returns 'no' (not reflexive), otherwise 'yes' (reflexive).