Переходное замыкание

В математике, переходное замыкание бинарного отношения . R в наборе X - наименьшее отношение в X, которое содержит R и является транзитивным.

. Например, если X - это набор аэропортов, а xRy означает, что "существует прямой рейс из аэропорта x в аэропорт y "(для x и y в X), тогда транзитивное замыкание R на X - это отношение R, такое, что x R y означает, что" можно лететь из x в y в одном или нескольких полеты ». Неформально транзитивное замыкание дает вам набор всех мест, куда вы можете добраться из любой точки старта.

Более формально транзитивное замыкание бинарного отношения R на множестве X - это транзитивное отношение R на множестве X, такое что R содержит R, а R минимально Lidl Pilz (1998, стр. 337). Если само бинарное отношение транзитивно, то транзитивное замыкание - это то же самое бинарное отношение; в противном случае транзитивное замыкание - это другое отношение.

• 1 Переходные отношения и примеры
• 2 Существование и описание
• 3 Свойства
• 4 В теории графов
• 5 В логике и вычислительной сложности
• 6 В языках запросов к базам данных
• 7 Алгоритмы
• 8 См. Также
• 9 Ссылки
• 10 Внешние ссылки

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

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

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

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

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

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

где $R\; i\; \{\backslash \; displaystyle\; R\; ^\; \{i\}\}$- это i-я степень R, индуктивно определяемая как

$R\; 1\; =\; R\; \{\backslash \; displaystyle\; R\; ^\; \{1\}\; =\; R\}$

, а для $i>0\; \{\backslash \; displaystyle\; i>0\}$

$р\; я\; +\; 1\; знак\; равно\; р\; \circ \; р\; я\; \{\backslash \; displaystyle\; R\; ^\; \{i\; +\; 1\}\; =\; R\; \backslash \; circ\; R\; ^\; \{i\}\}$

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

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

• $R\; \subseteq \; R\; +\; \{\backslash \; displaystyle\; R\; \backslash \; substeq\; R\; ^\; \{+\}\}$: $R\; +\; \{\backslash \; displaystyle\; \backslash \; displaystyle\; R\; ^\; \{+\}\}$содержит все $R\; я\; \{\backslash \; displaystyle\; \backslash \; displaystyle\; R\; ^\; \{i\}\}$, поэтому, в частности, $R\; +\; \{\backslash \; displaystyle\; \backslash \; displaystyle\; R\; ^\; \{+\}\}$co ntains $R\; \{\backslash \; displaystyle\; \backslash \; displaystyle\; R\}$.
• $R\; +\; \{\backslash \; displaystyle\; \backslash \; displaystyle\; R\; ^\; \{+\}\}$транзитивен: Если $(s\; 1,\; s\; 2),\; (\; s\; 2,\; s\; 3)\; \in \; R\; +\; \{\backslash \; Displaystyle\; (s\_\; \{1\},\; s\_\; \{2\}),\; (s\_\; \{2\},\; s\_\; \{3\})\; \backslash \; in\; R\; ^\; \{+\}\}$, тогда $(s\; 1,\; s\; 2)\; \in \; R\; j\; \{\backslash \; displaystyle\; (s\_\; \{1\},\; s\_\; \{2\})\; \backslash \; in\; R\; ^\; \{j\}\}$и $(s\; 2,\; s\; 3)\; \in \; R\; K\; \{\backslash \; displaystyle\; (s\_\; \{2\},\; s\_\; \{3\})\; \backslash \; in\; R\; ^\; \{k\}\}$для некоторых $j,\; k\; \{\backslash \; displaystyle\; j,\; k\}$по определению $R\; +\; \{\backslash \; displaystyle\; R\; ^\; \{+\}\}$. Поскольку композиция ассоциативна, $R\; j\; +\; k\; =\; R\; j\; \circ \; R\; k\; \{\backslash \; displaystyle\; R\; ^\; \{j\; +\; k\}\; =\; R\; ^\; \{j\}\; \backslash \; circ\; R\; ^\; \{k\}\}$; следовательно, $(s\; 1,\; s\; 3)\; \in \; R\; j\; +\; k\; \subseteq \; R\; +\; \{\backslash \; displaystyle\; (s\_\; \{1\},\; s\_\; \{3\})\; \backslash \; in\; R\; ^\; \{j\; +\; k\}\; \backslash \; substeq\; R\; ^\; \{+\}\}$по определению $\circ \; \{\backslash \; displaystyle\; \backslash \; circ\}$и $R\; +\; \{\backslash \; displaystyle\; R\; ^\; \{+\}\}$.
• $R\; +\; \{\backslash \; displaystyle\; R\; ^\; \{+\}\}$минимально, то есть если $T\; \{\backslash \; displaystyle\; T\}$- любое транзитивное отношение, содержащее $R\; \{\backslash \; displaystyle\; R\}$, затем $R\; +\; \subseteq \; T\; \{\backslash \; displaystyle\; R\; ^\; \{+\}\; \backslash \; substeq\; T\}$: для любого такого $T\; \{\backslash \; displaystyle\; T\}$, индукции на $i\; \{\backslash \; displaystyle\; i\}$можно использовать для отображения $R\; i\; \subseteq \; T\; \{\backslash \; displaystyle\; R\; ^\; \{i\}\; \backslash \; substeq\; T\}$для всех $i\; \{\backslash \; displaystyle\; i\}$следующим образом: Base: $R\; 1\; =\; R\; \subseteq \; T\; \{\backslash \; displaystyle\; R\; ^\; \{1\}\; =\; R\; \backslash \; substeq\; T\}$по предположению. Шаг: если выполняется $R\; i\; \subseteq \; T\; \{\backslash \; displaystyle\; R\; ^\; \{i\}\; \backslash \; substeq\; T\}$и $(s\; 1,\; s\; 3)\; \in \; R\; i\; +\; 1\; =\; R\; \circ \; R\; я\; \{\backslash \; displaystyle\; (s\_\; \{1\},\; s\_\; \{3\})\; \backslash \; in\; R\; ^\; \{i\; +\; 1\}\; =\; R\; \backslash \; circ\; R\; ^\; \{i\}\}$, затем $(s\; 1,\; s\; 2)\; \in \; R\; \{\backslash \; displaystyle\; (s\_\; \{1\},\; s\_\; \{2\})\; \backslash \; in\; R\}$и $(s\; 2,\; s\; 3)\; \in \; R\; i\; \{\backslash \; displaystyle\; (s\_\; \{2\}),\; s\_\; \{3\})\; \backslash \; in\; R\; ^\; \{i\}\}$для некоторого $s\; 2\; \{\backslash \; displaystyle\; s\_\; \{2\}\}$, по определению $\circ \; \{\; \backslash \; Displaystyle\; \backslash \; circ\}$. Следовательно, $(s\; 1,\; s\; 2),\; (s\; 2,\; s\; 3)\; \in \; T\; \{\backslash \; displaystyle\; (s\_\; \{1\},\; s\_\; \{2\}),\; (s\_\; \{2\},\; s\_\; \{3\})\; \backslash \; in\; T\}$по предположению и по предположению индукции. Следовательно, $(s\; 1,\; s\; 3)\; \in \; T\; \{\backslash \; displaystyle\; (s\_\; \{1\},\; s\_\; \{3\})\; \backslash \; in\; T\}$по транзитивности $T\; \{\backslash \; displaystyle\; T\}$; это завершает индукцию. Наконец, $R\; я\; \subseteq \; T\; \{\backslash \; displaystyle\; R\; ^\; \{i\}\; \backslash \; substeq\; T\}$для всех $i\; \{\backslash \; displaystyle\; i\}$подразумевает $R\; +\; \subseteq \; T\; \{\backslash \; displaystyle\; R\; ^\; \{+\}\; \backslash \; substeq\; T\}$по определению $R\; +\; \{\backslash \; displaystyle\; R\; ^\; \{+\}\}$.

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

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

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

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

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

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

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

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

Datalog также реализует вычисления транзитивного замыкания (Silberschatz et al. 2010: C.3.6).

Эффективные алгоритмы для вычисления транзитивного замыкания отношения смежности графа можно найти в Nuutila (1995). Самые быстрые методы наихудшего случая, которые непрактичны, сводят проблему к умножению матриц. Проблема также может быть решена с помощью алгоритма Флойда – Уоршалла или повторного поиска в ширину или поиска в глубину, начиная с каждого узла графа..

В более поздних исследованиях изучались эффективные способы вычисления транзитивного замыкания в распределенных системах на основе парадигмы MapReduce (Afrati et al. 2011).

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

• Lidl, R.; Пильц, Г. (1998), Прикладная абстрактная алгебра, Тексты для студентов по математике (2-е изд.), Springer, ISBN 0-387-98290-6
• Келлер, У., 2004, Некоторые замечания об определяемости транзитивного замыкания в логике первого порядка и журнале данных (неопубликованная рукопись)
• Эрих Гредель; Фокион Г. Колайтис; Леонид Либкин; Маартен Маркс; Джоэл Спенсер; Моше Й. Варди; Yde Venema; Скотт Вайнштейн (2007). Теория конечных моделей и ее приложения. Springer. С. 151–152. ISBN 978-3-540-68804-4.
• Либкин, Леонид (2004), Элементы теории конечных моделей, Springer, ISBN 978-3-540-21202-7
• Хайнц-Дитер Эббингаус; Йорг Флум (1999). Теория конечных моделей (2-е изд.). Springer. С. 123 –124, 151–161, 220–235. ISBN 978-3-540-28787-2.
• Aho, A. V.; Ульман, Дж. Д. (1979). «Универсальность языков поиска данных». Материалы 6-го симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования - POPL '79. С. 110–119. doi : 10.1145 / 567752.567763.
• Benedikt, M.; Сенелларт, П. (2011). «Базы данных». В Blum, Edward K.; Ахо, Альфред В. (ред.). Информационные технологии. Аппаратное обеспечение, программное обеспечение и его суть. С. 169–229. DOI : 10.1007 / 978-1-4614-1168-0_10. ISBN 978-1-4614-1167-3.
• Нуутила, Э., Эффективное вычисление переходного замыкания в больших орграфах. Acta Polytechnica Scandinavica, Математика и вычисления в инженерии Серия № 74, Хельсинки, 1995 г., 124 стр. Издано Финской технологической академией. ISBN 951-666-451-2, ISSN 1237-2404, УДК ​​681.3.
• Авраам Зильбершатц; Генри Корт; С. Сударшан (2010). Концепции системы баз данных (6-е изд.). Макгроу-Хилл. ISBN 978-0-07-352332-3.Приложение C (только онлайн)
• Фотография Н. Афрати, Винаяк Боркар, Майкл Кэри, Неоклис Полизотис, Джеффри Д. Уллман, Расширения Map-Reduce и рекурсивные запросы, EDBT 2011, 22–24 марта 2011 г., Упсала, Швеция, ISBN 978-1 -4503-0528-0

• "Транзитивное закрытие и сокращение ", The Stony Brook Algorithm Repository, Стивен Скиена.
• "Apti Algoritmi ", Пример и некоторые реализации алгоритмов C ++ которые вычисляют транзитивное замыкание данного бинарного отношения, Вреда Питерс.