Транзитивное замыкание

показывать Транзитивные   бинарные отношения
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Total, Semiconnex Anti- reflexive Equivalence relation Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Preorder (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Partial order ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Total preorder ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Total order ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Prewellordering ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Well-quasi-ordering ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Well-ordering ✗ Y Y Y ✗ ✗ Y ✗ ✗ Lattice ✗ Y ✗ ✗ Y Y Y ✗ ✗ Join-semilattice ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Meet-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Strict partial order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict weak order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict total order ✗ Y Y ✗ ✗ ✗ ✗ Y Y Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Definitions, for all $a,b$ and $S\neq \varnothing :$ ${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$ ${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$ ${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}$ ${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$ $aRa$ ${\text{not }}aRa$ ${\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}$
Y indicates that the column's property is always true the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively. All definitions tacitly require the homogeneous relation $R$ be transitive: for all $a,b,c,$ if $aRb$ and $bRc$ then $aRc.$ A term's definition may require additional properties that are not listed in this table.

Эта статья о транзитивном замыкании бинарного отношения. Чтобы узнать о транзитивном замыкании набора, см. транзитивное множество § Транзитивное замыкание .

В математике транзитивное замыкание R ⁺ однородного бинарного отношения R на множестве X — это наименьшее отношение на X , содержащее R и транзитивное . Для конечных множеств «наименьший» можно понимать в его обычном смысле, когда имеется наименьшее количество связанных пар; для бесконечных множеств R ⁺ единственным минимальным транзитивным надмножеством R является .

Например, если X — набор аэропортов и x R y означает «есть прямой рейс из аэропорта x в аэропорт y » (для x и y в X ), то транзитивное замыкание R на X — это отношение R ⁺ такой, что x R ⁺ y означает «можно перелететь из x в y за один или несколько рейсов».

Более формально, транзитивное замыкание бинарного отношения R на множестве X — это наименьшее (по отношению к ⊆) транзитивное отношение R ⁺ на X такой, что R ⊆ R ⁺ ; см. Lidl & Pilz (1998 , стр. 337). У нас есть Р ⁺ = R тогда и только тогда, когда сам R транзитивен.

И наоборот, транзитивная редукция выводит минимальное отношение S из данного отношения R такое, что они имеют одно и то же замыкание, то есть S ⁺ = Р ⁺ ; однако может существовать много разных S с этим свойством.

И транзитивное замыкание, и транзитивная редукция также используются в тесно связанной области теории графов .

и

Отношение R на множестве X является транзитивным, если для всех x , y , z в X всякий раз, когда x R y и y R z, тогда x R z . Примеры транзитивных отношений включают отношение равенства на любом множестве, отношение «меньше или равно» на любом линейно упорядоченном множестве и отношение « x родился раньше y » на множестве всех людей. Символически это можно обозначить так: если x < y и y < z , то x < z .

Одним из примеров нетранзитивного отношения является «до города x можно добраться прямым рейсом из города y » на множестве всех городов. Тот факт, что существует прямой рейс из одного города во второй город и прямой рейс из второго города в третий, не означает, что существует прямой рейс из первого города в третий. Транзитивным замыканием этого отношения является другое отношение, а именно: «существует последовательность прямых рейсов, которая начинается в городе x и заканчивается в городе y ». Каждое отношение может быть расширено аналогично транзитивному отношению.

Примером нетранзитивного отношения с менее значимым транзитивным замыканием является « x — день недели после y ». Транзитивное замыкание этого отношения таково: «когда-нибудь день x наступает после дня y в календаре», что тривиально верно для всех дней недели x и y (и, таким образом, эквивалентно декартову квадрату , который гласит: « x и y суть оба дня недели»).

Существование и описание

Для любого отношения R транзитивное замыкание R. всегда существует Чтобы убедиться в этом, заметим, что пересечение любого семейства транзитивных отношений снова транзитивно. Более того, существует хотя бы одно транзитивное отношение, содержащее , а именно тривиальное: X × X. R Транзитивное замыкание R тогда задается пересечением всех транзитивных отношений, содержащих R .

Для конечных множеств мы можем построить транзитивное замыкание шаг за шагом, начиная с R и добавляя транзитивные ребра. Это дает представление об общей конструкции. Для любого множества X мы может доказать, что транзитивное замыкание задается следующим выражением

$R^{+}=\bigcup _{i=1}^{\infty }R^{i}.$

где $R^{i}$ - i -я степень R , определяемая индуктивно формулой

$R^{1}=R$

и для $i>0$,

$R^{i+1}=R\circ R^{i}$

где $\circ$ обозначает композицию отношений .

Чтобы показать, что приведенное выше определение R ⁺ является наименее транзитивным отношением, содержащим R , мы показываем, что оно содержит R , что оно транзитивно и что это наименьшее множество с обеими этими характеристиками.

• $R\subseteq R^{+}$: $R^{+}$ содержит все $R^{i}$, так что в частности $R^{+}$ содержит $R$.
• $R^{+}$ транзитивен: если $(s_{1},s_{2}),(s_{2},s_{3})\in R^{+}$, затем $(s_{1},s_{2})\in R^{j}$ и $(s_{2},s_{3})\in R^{k}$ для некоторых $j,k$ по определению $R^{+}$. Поскольку композиция ассоциативна, $R^{j+k}=R^{j}\circ R^{k}$; следовательно $(s_{1},s_{3})\in R^{j+k}\subseteq R^{+}$ по определению $\circ$ и $R^{+}$.
• $R^{+}$ минимально, то есть если $T$ — любое транзитивное отношение, содержащее $R$, затем $R^{+}\subseteq T$: При наличии любого такого $T$, индукция по $i$ можно использовать, чтобы показать $R^{i}\subseteq T$ для всех $i$ следующим образом: База: $R^{1}=R\subseteq T$по предположению. Шаг: Если $R^{i}\subseteq T$ держится, и $(s_{1},s_{3})\in R^{i+1}=R\circ R^{i}$, затем $(s_{1},s_{2})\in R$ и $(s_{2},s_{3})\in R^{i}$ для некоторых $s_{2}$, по определению $\circ$. Следовательно, $(s_{1},s_{2}),(s_{2},s_{3})\in T$по предположению и по гипотезе индукции. Следовательно $(s_{1},s_{3})\in T$ транзитивностью $T$; это завершает индукцию. Окончательно, $R^{i}\subseteq T$ для всех $i$ подразумевает $R^{+}\subseteq T$ по определению $R^{+}$.

Свойства

Пересечение двух транзитивных отношений транзитивно.

Объединение . двух транзитивных отношений не обязательно должно быть транзитивным Чтобы сохранить транзитивность, необходимо использовать транзитивное замыкание. Это происходит, например, при объединении двух отношений эквивалентности или двух предпорядков . Чтобы получить новое отношение эквивалентности или предпорядок, необходимо использовать транзитивное замыкание (рефлексивность и симметрия - в случае отношений эквивалентности - являются автоматическими).

В теории графов

Транзитивное замыкание создает выходной граф из входного графа.

В информатике концепцию транзитивного замыкания можно рассматривать как построение структуры данных, позволяющей отвечать на вопросы о достижимости . То есть можно ли перейти от узла a к узлу d за один или несколько переходов? Бинарное отношение сообщает вам только, что узел a соединен с узлом b , а узел b соединен с узлом c и т. д. После построения транзитивного замыкания, как показано на следующем рисунке, в операции O(1) можно определить, что узел d достижим из узла a . Структура данных обычно хранится в виде логической матрицы, поэтому, если матрица[1][4] = true, тогда узел 1 может достичь узла 4 через один или несколько переходов.

Транзитивное замыкание отношения смежности ориентированного ациклического графа (DAG) — это отношение достижимости DAG и строгий частичный порядок .

Кластерный граф , транзитивное замыкание неориентированного графа.

Транзитивное замыкание неориентированного создает кластерный граф , несвязное объединение клик . графа Построение транзитивного замыкания является эквивалентной постановкой задачи нахождения компонент графа.

По логике и вычислительной сложности

Транзитивное замыкание бинарного отношения, вообще говоря, не может быть выражено в логике первого порядка (ФО). Это означает, что нельзя написать формулу с использованием символов-предикатов R и T , которая будет выполняться в любая модель тогда и только тогда, когда T является транзитивным замыканием R . В теории конечных моделей логика первого порядка (FO), расширенная с помощью оператора транзитивного замыкания, обычно называется логикой транзитивного замыкания и сокращенно FO(TC) или просто TC. TC — это подтип логики с фиксированной точкой . Тот факт, что FO(TC) строго более выразителен, чем FO, был открыт Рональдом Феджином в 1974 году; результат был затем заново открыт Альфредом Ахо и Джеффри Уллманом в 1979 году, которые предложили использовать логику фиксированных точек в качестве языка запросов к базе данных . С учетом более поздних концепций теории конечных моделей доказательство того, что FO(TC) является строго более выразительным, чем FO, немедленно следует из того факта, что FO(TC) не является локальным по Гейфману .

В теории сложности вычислений класс сложности NL точно соответствует множеству логических предложений, выражаемых в TC. Это связано с тем, что свойство транзитивного замыкания тесно связано с NL-полной задачей STCON для поиска направленных путей в графе. Аналогично, класс L представляет собой логику первого порядка с коммутативным транзитивным замыканием. добавляется транзитивное замыкание Когда вместо этого к логике второго порядка , мы получаем PSPACE .

На языках запросов к базе данных

Дополнительная информация: Иерархические и рекурсивные запросы в SQL.

С 1980-х годов в базе данных Oracle реализовано собственное SQL . расширение CONNECT BY... START WITHэто позволяет вычислить транзитивное замыкание как часть декларативного запроса. Стандарт SQL 3 (1999 г.) добавил более общий подход. WITH RECURSIVEконструкция, также позволяющая вычислять транзитивные замыкания внутри процессора запросов; по состоянию на 2011 год последний реализован в IBM Db2 , Microsoft SQL Server , Oracle , PostgreSQL и MySQL (v8.0+). SQLite выпустил поддержку этого в 2014 году.

Datalog также реализует вычисления транзитивного замыкания.

MariaDB реализует рекурсивные общие табличные выражения, которые можно использовать для вычисления транзитивных замыканий. Эта функция была представлена ​​в версии 10.2.2 от апреля 2016 г.

Алгоритмы

Эффективные алгоритмы вычисления транзитивного замыкания отношения смежности графа можно найти в Nuutila (1995) . Сведение задачи к умножению матриц смежности позволяет достичь временной сложности умножения матриц , $O(n^{2.3728596})$. Однако этот подход непрактичен, поскольку как постоянные факторы, так и потребление памяти для разреженных графов высоки ( Nuutila 1995 , стр. 22–23, раздел 2.3.3). Эту задачу также можно решить с помощью алгоритма Флойда–Уоршалла в $O(n^{3})$или повторным поиском в ширину или поиском в глубину, начиная с каждого узла графа.

Для ориентированных графов алгоритм Пердома решает проблему, сначала вычисляя его конденсационный DAG и его транзитивное замыкание, а затем поднимая его до исходного графа. Время его выполнения $O(m+\mu n)$, где $\mu$ — число ребер между его сильно связными компонентами .

Более поздние исследования изучали эффективные способы вычисления транзитивного замыкания в распределенных системах на основе парадигмы MapReduce .

См. также

• Родовые отношения
• Дедуктивное замыкание
• Рефлексивное закрытие
• Симметричное закрытие
• Транзитивная редукция (наименьшее отношение, имеющее транзитивное замыкание R в качестве транзитивного замыкания)

Ссылки

• Фото Н. Афрати, Винаяк Боркар, Майкл Кэри, Неоклис Полизотис, Джеффри Д. Ульман, Расширения Map-Reduce и рекурсивные запросы , EDBT 2011, 22–24 марта 2011 г., Уппсала, Швеция, ISBN   978-1-4503-0528-0
• Ахо, А.В.; Ульман, JD (1979). «Универсальность языков поиска данных». Материалы 6-го симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования - POPL '79 . стр. 110–119. дои : 10.1145/567752.567763 .
• Бенедикт, М.; Сенелларт, П. (2011). «Базы данных». В Блюме, Эдвард К.; Ахо, Альфред В. (ред.). Информатика. Аппаратное обеспечение, программное обеспечение и его суть . стр. 169–229. дои : 10.1007/978-1-4614-1168-0_10 . ISBN  978-1-4614-1167-3 .
• Хайнц-Дитер Эббингауз; Йорг Флюм (1999). Теория конечных моделей (2-е изд.). Спрингер. стр. 123–124 , 151–161, 220–235. ISBN  978-3-540-28787-2 .
• Фишер, MJ; Мейер, Арканзас (октябрь 1971 г.). «Умножение булевых матриц и транзитивное замыкание» (PDF) . В Рэймонде Э. Миллере и Джоне Э. Хопкрофте (ред.). Учеб. 12-я Энн. Симп. по теории коммутации и автоматов (SWAT) . Компьютерное общество IEEE. стр. 129–131. дои : 10.1109/SWAT.1971.4 .
• Эрих Градель; Фокион Г. Колит; Леонид Либкин; Мартин Маркс; Джоэл Спенсер; Моисей Ю. Варди; Иде Венема; Скотт Вайнштейн (2007). Теория конечных моделей и ее приложения . Спрингер. стр. 100-1 151–152. ISBN  978-3-540-68804-4 .
• Келлер, У., 2004, Некоторые замечания по поводу определяемости транзитивного замыкания в логике первого порядка и журнале данных (неопубликованная рукопись)* Либкин, Леонид (2004), Элементы теории конечных моделей , Springer, ISBN  978-3-540-21202-7
• Лидл, Р.; Пильц, Г. (1998), Прикладная абстрактная алгебра , Тексты для бакалавров по математике (2-е изд.), Springer, ISBN  0-387-98290-6
• Манро, Ян (январь 1971 г.). «Эффективное определение транзитивного замыкания ориентированного графа». Письма об обработке информации . 1 (2): 56–58. дои : 10.1016/0020-0190(71)90006-8 .
• Нуутила, Эско (1995). Эффективное вычисление транзитивных замыканий в больших орграфах . Финская технологическая академия. ISBN  951-666-451-2 . OCLC   912471702 .
• Авраам Зильбершац; Генри Корт; С. Сударшан (2010). Концепции системы баз данных (6-е изд.). МакГроу-Хилл. ISBN  978-0-07-352332-3 . Приложение C (только онлайн)

Внешние ссылки

• « Транзитивное замыкание и редукция », Репозиторий алгоритмов Стоуни-Брук, Стивен Скиена.