Переходное закрытие - Transitive closure

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

Например, если Икс это набор аэропортов и xRy означает "есть прямой рейс из аэропорта" Икс в аэропорт у" (за Икс и у в Икс), то транзитивное замыкание р на Икс это отношение р⁺ такой, что х R⁺ у означает "можно вылететь из Икс к у в один или несколько рейсов ". Неофициально переходное закрытие дает вам набор всех мест, куда вы можете добраться из любой точки старта.

Более формально транзитивное замыкание бинарного отношения р на съемочной площадке Икс это переходное отношение р⁺ на съемочной площадке Икс такой, что р⁺ содержит р и р⁺ минимален Лидл и Пильц (1998), п. 337). Если само бинарное отношение транзитивно, то транзитивное замыкание - это то же самое бинарное отношение; в противном случае транзитивное замыкание - это другое отношение.

Переходные отношения и примеры

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

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

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

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

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

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

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

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

${ Displaystyle R ^ {1} = R}$

и для ${ displaystyle i> 0}$,

${ Displaystyle R ^ {я + 1} = R circ R ^ {я}}$

куда ${ displaystyle circ}$ обозначает состав отношений.

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

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

Характеристики

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритмы

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

В более поздних исследованиях изучались эффективные способы вычисления транзитивного замыкания в распределенных системах на основе Уменьшение карты парадигма (Афрати и др., 2011).

Смотрите также

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

Рекомендации

• Lidl, R .; Пильц, Г. (1998), Прикладная абстрактная алгебра, Тексты для бакалавриата по математике (2-е изд.), Springer, ISBN  0-387-98290-6
• Келлер, У., 2004 г., Некоторые замечания об определимости транзитивного замыкания в логике первого порядка и в журнале данных (неопубликованная рукопись)
• Эрих Гредель; Фокион Г. Колайтис; Леонид Либкин; Маартен Маркс; Джоэл Спенсер; Моше Й. Варди; Yde Venema; Скотт Вайнштейн (2007). Теория конечных моделей и ее приложения. Springer. С. 151–152. ISBN  978-3-540-68804-4.
• Либкин Леонид (2004), Элементы теории конечных моделей, Спрингер, ISBN  978-3-540-21202-7
• Хайнц-Дитер Эббингаус; Йорг Флум (1999). Теория конечных моделей (2-е изд.). Springer. стр.123 –124, 151–161, 220–235. ISBN  978-3-540-28787-2.
• Ахо, А. В .; Ульман, Дж. Д. (1979). «Универсальность языков поиска данных». Материалы 6-го симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования - POPL '79. С. 110–119. Дои:10.1145/567752.567763.
• Бенедикт, М .; Сенелларт, П. (2011). «Базы данных». В Blum, Edward K .; Ахо, Альфред В. (ред.). Информатика. Аппаратное и программное обеспечение и его суть. С. 169–229. Дои: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

внешняя ссылка

• "Переходное закрытие и сокращение ", Репозиторий алгоритмов Стоуни-Брук, Стивен Скиена.
• "Апти Алгоритми ", Пример и некоторые реализации C ++ алгоритмов, которые вычисляют транзитивное замыкание данного бинарного отношения, Вреда Питерс.