что такое транзитивная зависимость
Что такое транзитивная зависимость
Третья нормальная форма предполагает, что каждый столбец, не являющийся ключом, должен зависеть только от столбца, который является ключом, то есть должна отсутствовать транзитивная функциональная зависимость (transitive functional dependency)
Транзитивная функциональная зависимость выражается следующим образом: А → В и В → С. То есть атрибут С транзитивно зависит от атрибута А, если атрибут С зависит от атрибута В, а атрибут В зависит от атрибута А (при условии, что атрибут А функционально не зависит ни от атрибута В, ни от атрибута С).
Если столбец зависит не только от первичного ключа, то данный столбец находится не в той таблице, в которой он должен находиться, либо же является производным от других столбцов.
Для нормализации из исходной таблицы те атрибуты, которые находятся в транзитивной зависимости от ключа, выносятся в отдельную таблицу с копией того атрибута, от которого они непосредственно зависят.
При применении третьей нормальной формы таблица должна находиться во второй нормальной форме. 3NF позволяет значительно снизить избыточность данных.
Для примера возьмем сформированную в прошлой теме таблицу Courses, которая содержит информацию о курсах и которая находится во второй нормальной форме:
| CourseId | Course | TeacherId | Teacher |
| 1 | Математика | 1 | Смит |
| 2 | JavaScript | 2 | Адамс |
| 3 | Алгоритмы | 2 | Адамс |
Какие функциональные зависимости здесь можно выделить:
CourseId → Course, TeacherId, Teacher
Course → CourseId, TeacherId, Teacher
Вторая зависимость фактически аналогична первой и говорит о том, что атрибут Course является потенциальным ключом.
Третья зависимость говорит о том, что, зная идентификатор преподавателя, мы можем узнать его фамилию и должность. То есть через атрибут TeacherId атрибут Teacher зависит от CourseId (CourseId→ TeacherId и TeacherId → Teacher). И в данном случае мы можем говорить о транзитивной зависимости Teacher, Position от CourseId.
Для нормализации необходимо вынести в отдельную таблицу атрибуты TeacherId и Teacher. Для этого пусть будет отдельная таблица Teachers:
| TeacherId | Teacher |
| 1 | Смит |
| 2 | Адамс |
А таблица Courses сократится следующим образом:
СОДЕРЖАНИЕ
Компьютерные программы
Зависимости и транзитивные зависимости могут быть разрешены в разное время, в зависимости от того, как компилируется и / или выполняется компьютерная программа : например, у компилятора может быть фаза компоновки, на которой зависимости разрешаются. Иногда система сборки даже позволяет управлять транзитивными зависимостями.
Системы управления базами данных
Пусть A, B и C обозначают три различных (но не обязательно непересекающихся) набора атрибутов отношения. Предположим, что выполнены все три из следующих условий:
Тогда функциональная зависимость A → C (которая следует из 1 и 3 по аксиоме транзитивности ) является транзитивной зависимостью.
Пример
Транзитивная зависимость возникает в следующем отношении:
| Книга | Жанр | Автор | Национальность органа |
|---|---|---|---|
| Двадцать тысяч лье под водой | Научная фантастика | Жюль Верн | Французский |
| Путешествие к центру Земли | Научная фантастика | Жюль Верн | Французский |
| Листья травы | Поэзия | Уолт Уитмен | Американец |
| Анна Каренина | Литературная фантастика | Лев Толстой | русский |
| Признание | Автобиографический рассказ | Лев Толстой | русский |
Действует функциональная зависимость <Книга>→ <Национальность автора>; то есть, если мы знаем книгу, мы знаем национальность автора. Более того:
Следовательно, <Книга>→ <Национальность автора>— это переходная зависимость.
Транзитивная зависимость возникла из-за того, что неключевой атрибут (Автор) определял другой неключевой атрибут (Национальность Органа).
3NF – третья нормальная форма
Вы будете перенаправлены на Автор24
Рассмотрим понятие транзитивная функциональная зависимость.
Транзитивная функциональная зависимость
Другими словами, транзитивная зависимость возникает, когда неключевой атрибут находится в функциональной зависимости от одного или большего числа неключевых атрибутов.
Рассмотрим отношение ХРАНЕНИЕ (ОРГАНИЗАЦИЯ, СКЛАД, ВМЕСТИМОСТЬ), содержащее сведения об организациях, которые получают товары со складов, и о вместимости данных складов. Ключевым является атрибут ОРГАНИЗАЦИЯ. Если каждая организация товар может получать лишь с одного склада, то в рассматриваемом отношении существуют такие функциональные зависимости:
В данной ситуации появляются аномалии:
Для того, чтобы избавиться от указанных аномалий, нужно выполнить разбиение исходного отношения на два:
Третья нормальная форма
Отношение находится в третьей нормальной форме (3NF), если данное отношение находится во второй нормальной форме и каждый неключевой атрибут находится в нетранзитивной зависимости от первичного ключа.
Рассмотрим пример базы данных вуза:
ПРЕПОДАВАТЕЛИ (Таб_Номер_препод, ФИО_препод, Должность);
СТУДЕНТЫ (Номер_зачет_кн, ФИО_ст, Тема_курсовой);
КОНСУЛЬТАЦИЯ (Таб_Номер_препод, Номер_зачет_кн, Дата, Время, Кабинет, Объем).
В последнем отношении существует транзитивная зависимость:
Таким образом, данное отношение не находится в третьей нормальной форме со следующими последствиями:
Для того, чтобы устранить транзитивную зависимость, нужно провести разбиение последнего отношения с удалением из него транзитивно-зависимого атрибута и помещением его и копии того атрибута, от которого он зависит, во вновь созданное отношение.
Следовательно, база данных данного примера без транзитивных зависимостей в третьей нормальной форме будет иметь следующий вид:
ПРЕПОДАВАТЕЛИ (Таб_Номер_препод, ФИО_препод, Должность);
СТУДЕНТЫ (Номер_зачет_кн, ФИО_ст, Тема_курсовой);
КОНСУЛЬТАЦИЯ (Таб_Номер_препод, Номер_зачет_кн, Дата, Время, Кабинет);
КАБИНЕТ (Кабинет, Объем).
Готовые работы на аналогичную тему
В процессе проектирования структуры базы данных считают корректной установку, при которой любая база данных должна пребывать как минимум в третьей нормальной форме. В практической деятельности третью нормальную форму схем отношений считают достаточной в большинстве случаев, и приведение к третьей нормальной форме обычно является заключающим этапом процесса проектирования реляционной базы данных.
Рассмотрим пример, в котором приведем таблицу 1, содержащую набор транзитивных зависимостей, к двум таблицам 2 и 3, которые находятся в третьей нормальной форме. Таблица 1 имеет такие ограничения предметной области:
Получи деньги за свои студенческие работы
Курсовые, рефераты или другие работы
Автор этой статьи Дата написания статьи: 19 09 2016
Разрешение конфликтов в транзитивных зависимостях — Хороший, Плохой, Злой
Вместо предисловия
В ближайшую субботу мы с EvgenyBorisov будем выступать в Питере на JUG.ru. Будет много веселого трэша и интересной инфы (иногда не разберешь, где проходит граница), и одно из моих выступлений будет посвящено WTF-нутости модульной разработки программ. Я расскажу несколько ужастиков, один из которых будет о том, как все пытаются быстро, гибко и корректно описать зависимости в проекте, и что из этого обычно получается. Интересно? Тогда добро пожаловать в ад!
Скорее, конечно, «Хороший, Удобный и WTF-ный».
Чуть-чуть теории.
Что Такое Менеджер Зависимостей и Зачем Он Нужен?
Что такое транзитивные зависимости?
Зачем нужны транзитивные зависимости?
Очевидно, не для компиляции. Но, для всего остального, пожалуй, нужны — эти артефакты должны находиться в сборках архивов, они должны находиться в classpath для запуска тестов, и пути к ним должны быть отданы через API для интеграции с IDE.
Как может образоваться конфликт?
Если мы посмотрим на диаграмму выше, то увидим тот самый конфликт. В classpath проекта A должны находиться и артефакт D версии 1 (от него зависит Е), и артефакт D версии 2 (от него зависит C )!
Почему это плохо?
JVM (и javac) определяет уникальность класса по его имени (и classloader-у, но в нашем простом примере все классы загружаются одним classloader-ом). В случае, когда в classpath встречаются два класса с одинаковым именем, загружен будет только первый. Если предположить, что в D1 и в D2 находятся классы с одинаковым именем (согласитесь, скорее всего, так и есть), то класс из jar-а, который будет прописан в сгенерированном classpath-е вторым просто не будет загружен. Какой из них будет первый? Это зависит от логики менеджера зависимостей и, в общем случае, неизвестно.
Как вы понимаете, это и есть конфликт:
Что делать?
В случае нашего примера, при использовании этой имплементации custom, если предположить что org у D1 и D2 начинается с ‘org.apache’, то в classpath окажется D2, в противном случае, сборка упадет.
Kто во что горазд
Теперь давайте посмотрим, кто из Дер Гроссе Тройки упомянутой выше, что умеет.
Apache Ivy
В плане менеджеров конфликтов Ivy прекрасен. Они подключаемы, оба варианта latest, а так же fail и all идут в коробке. С custom-ом тоже всё красиво. Можно полностью имплементировать свою логику, а можно воспользоваться полуфабрикатом и лишь придумать подходящий regex. По умолчанию работает latest (по версии).
Gradle
В первых версиях Gradle (до 0.6, если мне не изменяет память) использовался Ivy как менеджер зависимостей. Соответственно, всё сказанное выше было верно для Gradle тоже, но ребята из Gradleware написали свой менеджер зависимостей (в основном из за проблем с локальным хранилищем Ivy при параллельной сборкe, одного из главных преимуществ Gradle). В процессе выпуска своего менеджера такие «второстепенные» фичи как замена менеджера конфликтов были задвинуты далеко в roadmap, и довольно долгое время Gradle существовал только с latest. Не нравится latest — отключай транзитивные зависимости, и вперед, перечислять всё в ручную. Но, сегодня всё в порядке. Начиная с 1.0 есть fail, а с 1.4 и custom тоже.
Apache Maven
Ну, ради следующей картинки и был задуман весь пост.
Как вы считаете, какая из версий D попадет в classpath? D1? D2? обе? ни одной? сборка упадет? 
Как вы уже, наверняка, догадались, в classpath попадет D1 (что с огромной вероятностью приведет к проблемам, потому что весь код в C, написанный под новую функциональность, которой не существует в D1, просто упадет). Это тот самый чудесный WTF, который я вам обещал. Maven работает с уникальной стратегией nearest, которая выбирает в classpath тот артефакт, который находится ближе к корню проекта (А) в дереве проектов. 
Как же так? Что за ерунда?
Корень проблемы лежит в трудности исключения зависимости в Maven. Если, например, вы хотите использовать D2, а не D1, то, по хорошему, вы должны сказать Maven-у: Дорогой Maven, никогда не используй D1. Просто для примера, в Gradle мы бы написали вот так:
Проблема в том, что выразить это в Maven нельзя никак. (Опытный, и потому внимательный и вдумчивый пользователь Maven-а воскликнет здесь «А как же enforcer-plugin?!» И будет неправ). Можно сказать конкретно модулю E: «ты думал у тебя есть зависимость на D? Так вот, ее нет». Это хороший выход, конфликта больше нет, D2 в classpath, win. Но это решение совершенно не масштабируемо. Что если от D1 зависят десятки артефактов? На разных уровнях транзитивности?
Ну, и причем тут nearest?
Проблема отсутствия глобального exclude была решена в Maven-е очень «интересным» способом. Было решено, что если вы объявили в вашем проекте А зависимость с определенной версией, то только эта версия и попадет в classpath. То есть практически, это ультимативный nearest — ближе чем в A быть не может (это root), поэтому конфликт решён, не нужно искать все места откуда нужно исключать D. По дороге, правда, мы получили очень странное и трудно-предсказуемое поведение в тех случаях, когда A не объявляет D напрямую (см. наш пример), но что есть, то есть.
Достаточно интересно, что идея «то, что пользователь объявил сам — закон» используется в Gradle тоже, и это не мешает им использовать вменяемые стратегии типа latest и fail для всего остального.
Update: несколько человек в комментах напомнили, что у enforcer-plugin есть функциональность fail Это частично решает проблему. Остается: 1. дикий nearest по умолчанию. 2. варианты решения проблемы — прописывать все конфликтующие зависимости в своем проекте (сносно), либо бесконечные exclude-ы (адово).
А если одинаковая глубина?
Этот прекрасный вопрос (что делать, если бы в нашем примере B зависел от D2) не приходил ребятам из Maven-а в голову на протяжении двух с половиной лет (от релиза 2.0 в октябре 2005 и до версии 2.0.9 в апреле 2008) и какой артефакт будет в classpath было просто неопределенно. В Maven 2.0.9 было принято волевое решение — будет первый!
Как это нам помогает? Правильно, никак. Потому что мы в общем случае не знаем, какой из них будет первый, ведь транзитивные зависимости не проявляют себя пока не случается конфликт (либо пока мы не начинаем расследовать эту загадку). Спасибо, пацаны!
Что такое транзитивная зависимость в базе данных
Избегайте переходных зависимостей, чтобы помочь обеспечить нормализацию
Транзитивная зависимость в базе данных – это косвенная связь между значениями в одной и той же таблице, которая вызывает функциональную зависимость. Чтобы достичь стандарта нормализации третьей нормальной формы (3NF), вы должны устранить любые переходные зависимости.
По своей природе транзитивная зависимость требует трех или более атрибутов (или столбцов базы данных), которые имеют функциональную зависимость между ними, что означает, что столбец A в таблице опирается на столбец B через промежуточный столбец C. Давайте посмотрим, как это может работать.
Пример транзитивной зависимости
АВТОРЫ
| Auth_001 | Орсон Скотт Кард | Игра Эндера | Соединенные Штаты |
| Auth_001 | Орсон Скотт Кард | Игра Эндера | Соединенные Штаты |
| Auth_002 | Маргарет Этвуд | История о горничной | Канада |
В примере АВТОРЫ выше:
Но эта таблица вводит транзитивную зависимость:
Избежание переходных зависимостей
Чтобы обеспечить третью нормальную форму, давайте удалим транзитивную зависимость.
Мы можем начать с удаления столбца Book из таблицы Authors и создания отдельной таблицы Books:
Книги
| Book_001 | Игра Эндера | Auth_001 |
| Book_001 | Дети разума | Auth_001 |
| Book_002 | История о горничной | Auth_002 |
АВТОРЫ
| Auth_001 | Орсон Скотт Кард | Соединенные Штаты |
| Auth_002 | Маргарет Этвуд | Канада |
Это исправило это? Давайте рассмотрим наши зависимости сейчас:
Нам нужно добавить третью таблицу для нормализации этих данных:
Страны
| Coun_001 | Соединенные Штаты |
| Coun_002 | Канада |
АВТОРЫ
| Auth_001 | Орсон Скотт Кард | Coun_001 |
| Auth_002 | Маргарет Этвуд | Coun_002 |
Теперь у нас есть три таблицы, использующие внешние ключи для связи между таблицами:
Почему транзитивные зависимости плохой дизайн базы данных
Какова ценность избегания транзитивных зависимостей, чтобы помочь обеспечить 3NF? Давайте снова рассмотрим нашу первую таблицу и посмотрим на проблемы, которые она создает:
АВТОРЫ
| Auth_001 | Орсон Скотт Кард | Игра Эндера | Соединенные Штаты |
| Auth_001 | Орсон Скотт Кард | Дети разума | Соединенные Штаты |
| Auth_002 | Маргарет Этвуд | История о горничной | Канада |
Такая конструкция может способствовать аномалиям и несоответствиям данных, например:
Это всего лишь несколько причин, по которым нормализация и избежание транзитивных зависимостей защищают данные и обеспечивают согласованность.