Свойства отношений на множествах

Язык T-SQL в SQL Server базируется на стандартном языке SQL, основанном на реляционной модели, которая, в свою очередь, базируется на математических основаниях, таких как теория множеств и логика предикатов. В данной статье рассматривается фундаментальная тема из теории множеств: свойства отношений на множествах. Предлагаемые коды T-SQL читатели смогут использовать для проверки наличия определенных свойств тех или иных отношений. Но можно еще попробовать написать собственные версии сценариев (чтобы определить, обладает ли отношение конкретным свойством), прежде чем применять описанные в статье решения.

Множества и отношения

Георг Кантор, создатель теории множеств, определяет множество как «объединение в некое целое M совокупности определенных хорошо различимых объектов m нашего созерцания или мышления (которые будут называться элементами множества M)». Элементами множества могут быть объекты произвольной природы: люди, цифры и даже сами множества. Символы ∈ и ∉ обозначают, соответственно операторы, отражающие принадлежность (вхождение, членство) и непринадлежность элемента множеству. Так, запись x ∈ V означает, что x является элементом множества V, а запись x ∉ V — что x не является элементом V.

Бинарным отношением на множестве называется множество упорядоченных пар элементов исходного множества. Так, для множества элементов V = {a, b, c}, бинарным отношением R на данном множестве V будет произвольное подмножество множества всех упорядоченных пар декартова произведения V × V = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}. Отношение R = {(a, b), (b, c), (a, c)} является допустимым бинарным отношением на V. Можно сказать, что a соотносится с b посредством R. Предположим, что R = {(a, b), (b, c), (c, d)}. Такое R не является допустимым отношением на V, поскольку пара (c, d) не принадлежит декартову произведению V × V. Заметим, что порядок указания элементов, входящих во множество, не важен. Множество V может быть задано как {a, b, c} или как {b, a, c} и так далее. Однако порядок в упорядоченных парах, например в (a, b) бинарного отношения, важен; таким образом (a, b) ≠ (b, a).

В качестве более реального примера бинарного отношения рассмотрим множество F членов семьи: {Ицик, Микки, Инна, Мила, Габи}. Микки — брат-близнец Ицика, Инна — его старшая сестра, Мила — мама, а Габи — отец. Примером отношения R на множестве F будет: «является братом». Элементы этого отношения суть {(Ицик, Микки), (Микки, Ицик), (Ицик, Инна), (Микки, Инна)}. Отмечаем, что упорядоченная пара (Ицик, Инна) появляется в R, а пара (Инна, Ицик) — нет. Хотя Ицик — брат Инны, она ему братом не приходится.

Свойства отношений на множествах

Теперь, когда мы освежили наши представления о множествах и отношениях, приступим к теме статьи — свойствам отношений на множествах. В качестве данных для примера обратимся к кодам листинга 1, чтобы создать таблицы V и R. V будет представлять множество, а R — бинарное отношение на нем. Используйте код листинга 2 для создания процедуры ClearTables, с помощью которой сможете очистить от записей обе эти таблицы перед их заполнением новыми образцами данных. Наконец, используйте коды листингов 3, 4 и 5 для наполнения таблиц V и R различными наборами данных для тестирования (будем их называть примерами данных 1, 2 и 3 соответственно).

Рефлексивность. Отношение R на множестве V является рефлексивным, если для любого элемента v множества V, v ∈ V, следует, что (v, v) ∈ R, то есть пара (v, v) всегда принадлежит R. А отношение R на V не рефлексивно, если найдется такой элемент v ∈ V, что пара (v, v) ∉ R. Вновь рассмотрим пример множества F — членов моей семьи.

Отношение «иметь одинаковый возраст с» на F, очевидным образом, рефлексивно. Элементами отношения будут следующие пары: {(Ицик, Ицик), (Ицик, Микки), (Микки, Микки), (Микки, Ицик), (Инна, Инна), (Мила, Мила), (Габи, Габи)}.

Приступим к написанию T-SQL запроса к таблицам V и R (представляющим множество и отношение на этом множестве), проверяющего, обладает ли R свойством рефлексивности:

SELECT
   CASE
      WHEN EXISTS
         (SELECT v, v FROM dbo.V
         EXCEPT
         SELECT r1, r2 FROM dbo.R)
      THEN 'Нет'
      ELSE 'Да',
   END AS reflexive

Первый подзапрос в операции EXCEPT возвращает набор всех упорядоченных пар (v, v) для всех строк таблицы V. Второй подзапрос возвращает набор упорядоченных пар (r1, r2) — всех строк таблицы R. Операция EXCEPT, таким образом, вернет все упорядоченные пары, встречающиеся в первом и отсутствующие во втором наборе. Предикат EXISTS нужен для проверки существования хотя бы одной записи в результирующем наборе. Если найдется хотя бы одна такая запись, то выражение CASE возвратит нам «Нет» (нет рефлексивности), но и «Да» — в противном случае (есть рефлексивность).

Взгляните на три примера наборов данных в листингах 3, 4 и 5 и попытайтесь определить без запуска запроса, в каких из них отношение будет рефлексивным. Ответы даются далее в тексте статьи.

Иррефлексивнось. Отношение R на множестве V называется иррефлексивным (не путать с нерефлексивностью), если для каждого элемента v ∈ V следует, что (v, v) ∉ R. Отношение не иррефлексивно, если найдется элемент v ∈ V, для которого (v, v) ∈ R. Примером иррефлексивного отношения на множестве F членов моей семьи служит отношение «быть родителем», так как никакой человек не может быть родителем самому себе. Членами этого отношения на F будут следующие пары: {(Мила, Ицик), (Мила, Микки), (Мила, Инна), (Габи, Ицик), (Габи, Микки), (Габи, Инна)}.

Следующий запрос является проверочным — будет ли отношение R на V иррефлексивным:

SELECT
   CASE
      WHEN EXISTS
         (SELECT * FROM dbo.R
         WHERE r1 = r2)
   THEN 'Нет'
   ELSE 'Да'
END AS irreflexive

Внешние ключи в определении таблицы R были введены для обеспечения того, что лишь элементы V смогут составить атрибуты r1 и r2 записи R. Таким образом, остается только проверить, нет ли в R записей с совпадающими атрибутами r1 и r2. Если такая запись найдется, отношение R не иррефлексивно, если записи нет, оно иррефлексивно.

Симметричность. Отношение R на множестве V называется симметричным, если вместе с (r1, r2) ∈ R всегда выполняется и (r2, r1) ∈ R. Отношение не симметрично, если найдется некоторая пара (r1, r2) ∈ R, для которой (r2, r1) ∉ R. На множестве F членов семьи Бен-Ган отношение «является братом или сестрой (is a sibling of)» будет примером симметричного отношения. Парами этого отношения будут следующие наборы: {(Ицик, Микки), (Ицик, Инна), (Микки, Ицик), (Микки, Инна), (Инна, Ицик), (Инна, Микки)}.

Следующий запрос является проверочным — будет ли отношение R на V симметричным:

SELECT
   CASE
      WHEN EXISTS
         (SELECT r1, r2 FROM dbo.R
         EXCEPT
        SELECT r2, r1 FROM dbo.R)
   THEN 'Нет'
   ELSE 'Да'
END AS symmetric

Код запроса использует операцию EXCEPT. Первый подзапрос операции EXCEPT возвращает набор упорядоченных пар (r1, r2) — записей таблицы R, а второй — набор упорядоченных пар (r2, r1) по каждой записи R. Если отношение R на множестве V не симметрично, то операция EXCEPT вернет непустой результирующий набор, а предикат EXISTS, соответственно, значение TRUE и, наконец, выражение CASE вернет «Нет».

Если отношение симметрично, то выражение CASE даст «Да».

Асимметричность. Отношение R на множестве V асимметрично (не следует путать это свойство с несимметричностью), если для каждого набора (r1, r2) ∈ R, в котором r1 ≠ r2, справедливо, что (r2, r1) ∉ R. Примером асимметричного отношения на множестве F членов семьи автора будет отношение «являться родителем», которое было описано выше. В качестве упражнения постарайтесь придумать пример отношения на непустом множестве, которое одновременно является симметричным и асимметричным. Проверьте пример данных в этой статье в качестве решения.

SELECT
   CASE
      WHEN EXISTS
         (SELECT r1, r2 FROM dbo.R WHERE r1 <> r2
         INTERSECT
         SELECT r2, r1 FROM dbo.R WHERE r1 <> r2)
   THEN 'Нет'
   ELSE 'Да'
END AS asymmetric

В коде используется операция INTERSECT. Первый подзапрос в этой операции возвращает упорядоченную пару (r1, r2) для каждой записи таблицы R, в которой r1 <> r2.

Второй подзапрос операции INTERSECT возвращает упорядоченную пару (r2, r1) для каждой записи таблицы R, в которой r1 <> r2. Если в результирующий набор (результат пересечения этих множеств) входит хотя бы одна запись, это будет означать, что R не асимметрично; в противном случае R асимметрично.

Транзитивность. Отношение R на множестве V является транзитивным, если из включений (a, b) ∈ R и (b, c) ∈ R, всегда вытекает, что и (a, c) ∈ R. Примером транзитивного отношения на множестве членов семьи F будет отношение «является братом или сестрой», которое было рассмотрено выше.

Приведенный ниже код проверяет транзитивность отношения R:

SELECT
   CASE
      WHEN EXISTS
         (SELECT *
         FROM dbo.R AS RA
           INNER JOIN dbo.R AS RB
             ON RA.r2 = RB.r1
           LEFT OUTER JOIN dbo.R AS RC
             ON RA.r1 = RC.r1 AND RB.r2 = RC.r2
           WHERE RC.r1 IS NULL)
   THEN 'Нет'
   ELSE 'Да'
END AS transitive

В коде, во‑первых, используется внутренняя связь (inner join) между двумя экземплярами R, для того чтобы отбирать лишь те строки, в которых r2 в первом экземпляре совпадает с r1 на втором экземпляре. Во‑вторых, в коде применяется левая внешняя связь (left outer join) с третьим экземпляром таблицы R, в соответствии с которой r1 первого экземпляра R совпадает с r1 третьего экземпляра, а r2 второго экземпляра совпадает с r2 третьего. Если существует хотя бы одна результирующая строка во внутреннем подзапросе (условие отбора для третьего экземпляра: r1 есть Null), это означает, что отношение не транзитивно; в противном случае отношение R транзитивно.

Отношение эквивалентности. Отно­ше­нием эквивалентности является такое отношение, которое одновременно обладает свойствами рефлексивности, симметричности и транзитивности. Можно использовать запросы, предложенные выше для раздельной проверки наличия каждого свойства: если отношение обладает всеми тремя, то следует заключить, что имеет место отношение эквивалентности. Кроме того, вы можете использовать коды листинга 6 для проверки всех свойств отношения R на множестве V, которые ранее обсуждались в статье, в том числе проверку свойства быть отношением эквивалентности. Если провести прогонку листинга 6 для примеров данных 1, 2 и 3 (полученных на основе листингов 3, 4 и 5 соответственно), то получатся результаты, приведенные в таблицах 1, 2 и 3 соответственно.

Возвращаясь к основам T-SQL

Таким образом, мы рассмотрели фундаментальную тему из математической теории множеств: свойства отношений на множествах. Я предложил проверочные коды T-SQL для контроля свойств некоторого отношения, представленного таблицей R (упорядоченных пар элементов), на множестве элементов, представленных таблицей V.

Использование основных конструкций T-SQL помогло нам правильно настроить и применить средства этого языка для лучшего понимания свойств отношений на множествах.

Ицик Бен-Ган (Itzik@SolidQ.com) — преподаватель и консультант, автор книг по T-SQL, имеет звание SQL Server MVP