Реляционная модель - Relational model

В реляционная модель (RM) за база данных менеджмент - это подход к управлению данные используя структуру и язык, соответствующие логика предикатов первого порядка, впервые описанный в 1969 году английским ученым-компьютерщиком Эдгар Ф. Кодд,^[1][2] где все данные представлены в виде кортежи, сгруппированы в связи. База данных, организованная в терминах реляционной модели, является реляционная база данных.

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

Большинство реляционных баз данных используют SQL определение данных и язык запросов; эти системы реализуют то, что можно рассматривать как инженерное приближение к реляционной модели. А стол в SQL схема базы данных соответствует предикатной переменной; содержимое таблицы для отношения; ключевые ограничения, другие ограничения и запросы SQL соответствуют предикатам. Однако базы данных SQL отклоняться от реляционной модели во многих деталях, и Кодд яростно выступал против отклонений, которые ставят под угрозу исходные принципы.^[3]

Обзор

Центральная идея реляционной модели - описать базу данных как набор предикаты над конечным набором предикатных переменных, описывающих ограничения о возможных значениях и комбинациях значений. Содержимое базы данных в любой момент времени является конечным (логическим) модель базы данных, то есть набор связи, по одному на каждую переменную предиката, так что все предикаты удовлетворяются. Запрос информации из базы данных ( запрос к базе данных ) также является предикатом.

Понятия реляционной модели.

Альтернативы

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

Выполнение

Было предпринято несколько попыток создать истинную реализацию модели реляционной базы данных, как первоначально определено Кодд и объяснил Дата, Дарвен и другие, но до сих пор ни один из них не пользовался популярностью. По состоянию на октябрь 2015 г.^{[Обновить]} Rel это одна из самых недавних попыток сделать это.

Реляционная модель была первой моделью базы данных, описанной в формальных математических терминах. Иерархические и сетевые базы данных существовали до реляционных баз данных, но их спецификации были относительно неформальными. После определения реляционной модели было много попыток сравнить и сопоставить разные модели, что привело к появлению более строгих описаний более ранних моделей; хотя процедурный характер интерфейсов управления данными для иерархических и сетевых баз данных ограничивал возможности для формализации.^{[нужна цитата ]}

Структурная аналитика баз данных, использующая протоколы реляционной модальности, часто использует дифференциацию последовательностей данных для поддержки обозначений иерархической архитектуры с включением новых входных данных. Эти системы функционально схожи по концепции с альтернативными алгоритмами ретрансляции, которые составляют основу инфраструктуры облачных баз данных.^[4]

История

Реляционная модель была изобретена Эдгар Ф. Кодд в качестве общей модели данных и впоследствии продвигаемой Крис Дата и Хью Дарвен среди прочего. В Третий манифест (впервые опубликовано в 1995 г.) Дэйт и Дарвен пытаются показать, как реляционная модель якобы может приспособиться к определенным «желаемым» объектно-ориентированный Особенности.

Споры

Через несколько лет после публикации своей модели 1970 года Кодд предложил трехзначная логика (Верно, Неверно, Отсутствует /НОЛЬ ) его версия для работы с недостающей информацией, а в его Реляционная модель для управления базами данных версии 2 (1990) он пошел дальше, предложив версию с четырехзначной логикой (Верно, Ложно, Отсутствует, но применимо, Отсутствует, но неприменимо).^[5] Они никогда не были реализованы, по-видимому, из-за сложности обслуживания. Конструкция SQL NULL должна была быть частью трехзначной логической системы, но не соответствовала этому из-за логических ошибок в стандарте и его реализациях.^[6]

Темы

Основное предположение реляционной модели состоит в том, что все данные представлен как математический п-арый связи, п-арное отношение, являющееся подмножество из Декартово произведение из п домены. В математической модели рассуждение о таких данных делается в двузначном логика предикатов, то есть есть два возможных оценки для каждого предложение: либо истинный или же ложный (и, в частности, нет третьего значения, такого как неизвестный, или же непригодный, любой из которых часто ассоциируется с концепцией НОЛЬ ). Данные обрабатываются с помощью реляционное исчисление или же реляционная алгебра, они эквивалентны в выразительная сила.

Реляционная модель данных позволяет разработчику базы данных создавать согласованное, логическое представление Информация. Последовательность достигается за счет включения заявленных ограничения в дизайне базы данных, который обычно называют логическая схема. Теория включает в себя процесс нормализация базы данных посредством чего дизайн с определенными желаемыми свойствами может быть выбран из набора логически эквивалентный альтернативы. В планы доступа и другие детали реализации и работы обрабатываются СУБД двигателя, и не отражены в логической модели. Это контрастирует с обычной практикой для СУБД SQL, в которых настройка производительности часто требует изменения логической модели.

Основным строительным блоком отношений является домен или же тип данных, обычно сокращенно в настоящее время тип. А кортеж заказанный набор из значения атрибутов. An атрибут упорядоченная пара имя атрибута и имя типа. Значение атрибута - это конкретное допустимое значение для типа атрибута. Это может быть скалярное значение или более сложный тип.

Отношение состоит из Заголовок и тело. Заголовок - это набор атрибутов. Тело (из п-арное отношение) представляет собой набор п- пары. Заголовок отношения также является заголовком каждого из его кортежей.

Отношение определяется как набор из п- пары. И в математике, и в модели реляционной базы данных набор - это неупорядоченный сбор уникальных, не повторяющихся элементов, хотя некоторые СУБД устанавливают порядок для своих данных. В математике кортеж имеет заказ и допускает дублирование. Э. Ф. Кодд первоначально определенные кортежи с использованием этого математического определения.^[2] Позже это был один из Э. Ф. Кодд отличное понимание того, что использование имен атрибутов вместо упорядочивания было бы более удобным (в целом) на компьютерном языке, основанном на отношениях^{[нужна цитата ]}. Это понимание все еще используется сегодня. Хотя концепция изменилась, название «кортеж» не осталось. Непосредственным и важным следствием этой отличительной черты является то, что в реляционной модели Декартово произведение становится коммутативный.

А стол это общепринятое визуальное представление отношения; кортеж похож на концепцию ряд.

А relvar - это именованная переменная определенного типа отношения, которой всегда присваивается какое-либо отношение этого типа, хотя отношение может содержать нулевые кортежи.

Основной принцип реляционной модели - это Информационный принцип: все Информация представлен значениями данных в отношениях. В соответствии с этим Принципом реляционная база данных представляет собой набор relvar, и результат каждого запроса представлен в виде отношения.

Согласованность реляционной базы данных обеспечивается не правилами, встроенными в приложения, которые ее используют, а скорее ограничения, объявленный как часть логической схемы и обеспечиваемый СУБД для всех приложений. В общем, ограничения выражаются с помощью операторов сравнения отношений, из которых только один, «является подмножеством» (), теоретически достаточно^{[нужна цитата ]}. На практике ожидается, что будет доступно несколько полезных сокращений, из которых наиболее важными являются кандидат ключ (В самом деле, суперключ ) и иностранный ключ ограничения.

Интерпретация

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

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

Существует индивидуальная переписка между свободными переменными предиката и именами атрибутов заголовка отношения. Каждый кортеж тела отношения предоставляет значения атрибутов для создания экземпляра предиката путем подстановки каждой из его свободных переменных. Результатом является предложение, которое считается истинным из-за появления кортежа в теле отношения. И наоборот, каждый кортеж, заголовок которого соответствует заголовку отношения, но не появляется в теле, считается ложным. Это предположение известно как предположение о закрытом мире: это часто нарушается в практических базах данных, где отсутствие кортежа может означать, что истинность соответствующего предложения неизвестна. Например, отсутствие кортежа («Джон», «Испанский») в таблице языковых навыков не обязательно может рассматриваться как свидетельство того, что Джон не говорит по-испански.

Формальное изложение этих идей см. В разделе Теоретико-множественная формулировка, ниже.

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

А тип данных в типичной реляционной базе данных может быть набор целых чисел, набор символьных строк, набор дат или два логических значения истинный и ложный, и так далее. Соответствующие имена типов для этих типов могут быть строки "int", "char", "date", "boolean" и т. д. Однако важно понимать, что теория отношений не диктует, какие типы должны поддерживаться; действительно, в настоящее время ожидается наличие резервов для определяемые пользователем типы в дополнение к встроенный предоставленные системой.

Атрибут - термин, используемый в теории для обозначения того, что обычно называют столбец. По аналогии, стол обычно используется вместо теоретического термина связь (хотя в SQL этот термин ни в коем случае не является синонимом отношения). Структура данных таблицы определяется как список определений столбцов, каждое из которых указывает уникальное имя столбца и тип значений, разрешенных для этого столбца. An атрибут ценить - это запись в определенном столбце и строке, например «Джон Доу» или «35».

А кортеж в основном то же самое, что и ряд, за исключением СУБД SQL, где значения столбцов в строке упорядочены. (Кортежи не упорядочиваются; вместо этого каждое значение атрибута идентифицируется исключительно имя атрибута и никогда - по порядковому номеру в кортеже.) Имя атрибута может быть «name» или «age».

А связь это стол определение структуры (набор определений столбцов) вместе с данными, появляющимися в этой структуре. Определение структуры - это Заголовок и данные, появляющиеся в нем, являются тело, набор строк. База данных relvar (переменная отношения) широко известна как базовый стол. Заголовок присвоенного ему значения в любое время соответствует указанному в объявлении таблицы, а его тело - это то, что было присвоено ему последним путем вызова некоторых оператор обновления (обычно INSERT, UPDATE или DELETE). Заголовок и тело таблицы, полученной в результате оценки некоторого запроса, определяются определениями операторов, используемых в выражении этого запроса. (Обратите внимание, что в SQL заголовок не всегда является набором определений столбцов, как описано выше, потому что столбец может не иметь имени, а также иметь одно и то же имя для двух или более столбцов. Кроме того, тело не всегда набор строк, потому что в SQL одна и та же строка может появляться более одного раза в одном теле.)

SQL и реляционная модель

SQL, изначально заданный как стандарт язык для реляционные базы данных, отклоняется от реляционной модели в нескольких местах. Электрический ток ISO Стандарт SQL не упоминает реляционную модель и не использует реляционные термины или концепции. Однако можно создать базу данных, соответствующую реляционной модели, с использованием SQL, если не используются определенные функции SQL.

Отмечены следующие отклонения от реляционной модели^{[ВОЗ? ]} в SQL. Обратите внимание, что некоторые серверы баз данных реализуют весь стандарт SQL и, в частности, не допускают некоторых из этих отклонений. В то время как NULL встречается повсеместно, например, разрешение дублирования имен столбцов в таблице или анонимных столбцов встречается редко.

Повторяющиеся строки

Одна и та же строка может появляться в таблице SQL более одного раза. Один и тот же кортеж не может появляться более одного раза в связь.

Анонимные столбцы

Столбец в таблице SQL может быть безымянным, поэтому на него нельзя ссылаться в выражениях. Реляционная модель требует, чтобы каждый атрибут был назван и на него можно было ссылаться.

Повторяющиеся имена столбцов

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

Значение порядка столбцов

Порядок столбцов в таблице SQL определен и важен, одним из следствий которого является то, что реализации декартова произведения и объединения в SQL являются некоммутативными. Реляционная модель требует, чтобы какой-либо порядок атрибутов отношения не имел значения.

Просмотры без CHECK OPTION

Обновления до Посмотреть определенное без CHECK OPTION может быть принято, но результирующее обновление базы данных не обязательно окажет выраженное влияние на его цель. Например, вызов INSERT может быть принят, но не все вставленные строки могут отображаться в представлении, или вызов UPDATE может привести к исчезновению строк из представления. Реляционная модель требует, чтобы обновления представления имели такой же эффект, как если бы представление было базовой относительной переменной.

Таблицы без столбцов не распознаны

SQL требует, чтобы каждая таблица имела хотя бы один столбец, но есть два отношения нулевой степени ( мощность единица и ноль), и они необходимы для представления расширений предикатов, не содержащих свободных переменных.

НОЛЬ

Эта специальная метка может появляться вместо значения везде, где значение может появляться в SQL, в частности, вместо значения столбца в некоторой строке. Отклонение от реляционной модели возникает из-за того, что реализация этого для этого случая концепция в SQL предполагает использование трехзначная логика, при котором сравнение NULL с самим собой не дает истинный но вместо этого дает третий значение истины, неизвестный; аналогично сравнение NULL с чем-то другим, кроме самого себя, не дает ложный но вместо этого дает неизвестный. Именно из-за такого поведения при сравнении NULL описывается как отметка, а не как значение. Реляционная модель зависит от закон исключенного среднего при котором все, что не является ложным, является ложным, а все, что не является ложным, является истинным; он также требует, чтобы каждый кортеж в теле отношения имел значение для каждого атрибута этого отношения. Некоторые оспаривают это конкретное отклонение хотя бы потому, что Э. Сам Ф. Кодд в конечном итоге выступал за использование специальных знаков и четырехзначной логики, но это было основано на его наблюдении о том, что есть две различные причины, по которым можно использовать специальный знак вместо значения, что привело противников использование такой логики для обнаружения более отчетливых причин, и было отмечено по крайней мере 19, что потребовало бы 21-значной логики.^{[нужна цитата ]} Сам SQL использует NULL для нескольких целей, кроме представления «неизвестного значения». Например, сумма пустого набора равна NULL, что означает ноль, среднее значение пустого набора равно NULL, что означает undefined, а NULL, появляющийся в результате LEFT JOIN, может означать «нет значения, потому что нет соответствующей строки в правый операнд ". Есть способы создавать таблицы, чтобы избежать необходимости в NULL, обычно это может рассматриваться или напоминать высокие степени нормализация базы данных, но многие находят такое непрактичным. Это может быть горячо обсуждаемая тема.

Реляционные операции

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

В ответ на запрос база данных возвращает набор результатов, который представляет собой просто список строк, содержащих ответы. Самый простой запрос - просто вернуть все строки из таблицы, но чаще строки каким-то образом фильтруются, чтобы вернуть только нужный ответ.

Часто данные из нескольких таблиц объединяются в одну, выполняя присоединиться. Концептуально это делается путем взятия всех возможных комбинаций строк ( Декартово произведение ), а затем отфильтровав все, кроме ответа. На практике системы управления реляционными базами данных переписывают ("оптимизировать ") запросы для более быстрого выполнения с использованием различных методов.

В дополнение к соединению существует ряд реляционных операций. К ним относятся проект (процесс удаления некоторых столбцов), ограничение (процесс удаления некоторых строк), объединение (способ объединения двух таблиц с похожими структурами), разность (который перечисляет строки в одной таблице, которые являются не найдено в другой), пересечение (в котором перечислены строки, найденные в обеих таблицах) и продукт (упомянутый выше, который объединяет каждую строку одной таблицы с каждой строкой другой). В зависимости от того, с какими другими источниками вы обращаетесь, существует ряд других операторов, многие из которых могут быть определены в терминах тех, что перечислены выше. К ним относятся полусоединение, внешние операторы, такие как внешнее соединение и внешнее объединение, а также различные формы разделения. Затем есть операторы для переименования столбцов, а также операторы суммирования или агрегирования, и если вы разрешите связь значения как атрибуты (атрибут со значением отношения), затем такие операторы, как группировка и разгруппировка. Оператор SELECT в SQL служит для обработки всего этого, за исключением операторов группировки и разгруппировки.

Гибкость реляционных баз данных позволяет программистам писать запросы, которые не ожидались разработчиками баз данных. В результате реляционные базы данных могут использоваться несколькими приложениями способами, не предусмотренными первоначальными разработчиками, что особенно важно для баз данных, которые могут использоваться в течение длительного времени (возможно, несколько десятилетий). Это сделало идею и реализацию реляционных баз данных очень популярными в бизнесе.

Нормализация базы данных

связи классифицируются по типам аномалий, которым они уязвимы. База данных, которая находится в первая нормальная форма уязвима для всех типов аномалий, в то время как база данных в нормальной форме домен / ключ не имеет аномалий модификации. Нормальные формы имеют иерархический характер. То есть самый нижний уровень - это первая нормальная форма, и база данных не может удовлетворить требования для нормальных форм более высокого уровня, не выполнив сначала все требования меньших нормальных форм.^[7]

Примеры

База данных

Идеализированный, очень простой пример описания некоторых relvar (связь переменные) и их атрибуты:

• Покупатель (Пользовательский ИД, Налоговый номер, имя, адрес, город, штат, почтовый индекс, телефон, электронная почта, пол)
• Заказ (№ заказа, Пользовательский ИД, Счет-фактура №, Дата размещения, дата обещания, условия, статус)
• Строка заказа (№ заказа, Номер строки заказа, Код продукта, Кол-во)
• Выставленный счет (Счет-фактура №, Пользовательский ИД, № заказа, Дата, Статус)
• Строка счета-фактуры (Счет-фактура №, Номер строки счета-фактуры, Код продукта, Количество отправлено)
• Товар (Код продукта, Описание товара)

В этом дизайн у нас есть шесть релеваров: клиент, заказ, строка заказа, счет-фактура, строка счета-фактуры и продукт. Атрибуты, выделенные жирным шрифтом, подчеркнуты ключи-кандидаты. Атрибуты, не выделенные жирным шрифтом, подчеркнуты: внешние ключи.

Обычно один кандидат ключ выбран, чтобы называться первичный ключ и используется в предпочтение над другими ключами-кандидатами, которые затем вызываются альтернативные ключи.

А кандидат ключ уникальный идентификатор обеспечение того, что нет кортеж будет продублирован; это сделало бы связь во что-то другое, а именно мешок, нарушая основное определение набор. И внешние ключи, и суперключи (включая ключи-кандидаты) могут быть составными, то есть состоять из нескольких атрибутов. Ниже приводится табличное изображение отношения нашего примера Customer relvar; отношение можно рассматривать как значение, которое может быть приписано relvar.

Отношения с клиентами

Если бы мы попытались вставлять новый клиент с идентификатором 1234567890, это нарушило бы конструкцию relvar, поскольку Пользовательский ИД это первичный ключ и у нас уже есть заказчик 1234567890. В СУБД должен отклонить сделка такие как это, что сделало бы база данных несовместимы с нарушением ограничение целостности.

Внешние ключи находятся ограничения целостности обеспечение того, чтобы ценить из набор атрибутов взят из кандидат ключ в другой связь. Например, в отношении «Порядок» атрибут Пользовательский ИД это внешний ключ. А присоединиться это операция это опирается на Информация сразу от нескольких родственников. Объединив relvar из приведенного выше примера, мы могли бы запрос база данных для всех клиентов, заказов и счетов-фактур. Если бы нам нужны были только кортежи для определенного клиента, мы бы указали это, используя условие ограничения.

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

В нашем дизайн базы данных над. Относительная переменная Invoice содержит атрибут Order No. Таким образом, каждый кортеж в relvar Invoice будет иметь один номер заказа, что означает, что существует ровно один заказ для каждого счета-фактуры. Но на самом деле счет-фактура может быть выставлен по многим заказам или даже по любому конкретному заказу. Кроме того, relvar «Заказ» содержит атрибут «Номер счета-фактуры», подразумевающий, что каждому Заказу соответствует соответствующий счет-фактура. Но опять же, это не всегда верно в реальном мире. Иногда заказ оплачивается несколькими счетами, а иногда - без счета. Другими словами, может быть много счетов-фактур на заказ и много заказов на счет-фактуру. Это многие-ко-многим связь между Заказом и Счетом-фактурой (также называемая неспецифические отношения). Чтобы представить эту взаимосвязь в базе данных, необходимо ввести новую относительную переменную, чья роль - указать соответствие между Заказами и Счетами:

Счет-фактура (№ заказа, Счет-фактура №)

Теперь у relvar Order есть отношения один ко многим в таблицу OrderInvoice, как и относительная переменная Invoice. Если мы хотим получить каждый счет-фактуру для определенного заказа, мы можем запросить все заказы, где № заказа в отношении порядка равно № заказа в OrderInvoice, а где Счет-фактура № в OrderInvoice равно Счет-фактура № в счете-фактуре.

Теоретико-множественная формулировка

Основные понятия в реляционной модели: связь имена и имена атрибутов. Мы будем представлять их в виде строк, таких как «Человек» и «имя», и обычно будем использовать переменные ${displaystyle r, s, t, ldots}$ и ${displaystyle a, b, c}$ пробегать по ним. Еще одно базовое понятие - это набор атомарные значения который содержит такие значения, как числа и строки.

Наше первое определение касается понятия кортеж, который формализует понятие строки или записи в таблице:

Кортеж

Кортеж - это частичная функция от имен атрибутов до атомарных значений.

Заголовок

Заголовок - это конечный набор имен атрибутов.

Проекция

Проекция кортежа ${displaystyle t}$ на конечный набор атрибутов ${displaystyle A}$ является ${displaystyle t [A] = {(a, v) :( a, v) in t, ain A}}$.

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

Связь

Отношение - это кортеж ${displaystyle (H, B)}$ с ${displaystyle H}$, заголовок и ${displaystyle B}$, тело, набор кортежей, каждый из которых имеет домен ${displaystyle H}$.

Такое отношение близко соответствует тому, что обычно называют расширением предиката в логика первого порядка за исключением того, что здесь мы идентифицируем места в предикате с именами атрибутов. Обычно в реляционной модели a схема базы данных как говорят, состоит из набора имен отношений, заголовков, связанных с этими именами, и ограничения это должно выполняться для каждого экземпляра схемы базы данных.

Вселенная отношений

Вселенная отношений ${displaystyle U}$ над заголовком ${displaystyle H}$ непустой набор отношений с заголовком ${displaystyle H}$.

Схема отношения

Схема отношения ${displaystyle (H, C)}$ состоит из заголовка ${displaystyle H}$ и предикат ${displaystyle C (R)}$ что определено для всех отношений ${displaystyle R}$ с заголовком ${displaystyle H}$. Отношение удовлетворяет схеме отношения ${displaystyle (H, C)}$ если у него есть заголовок ${displaystyle H}$ и удовлетворяет ${displaystyle C}$.

Ключевые ограничения и функциональные зависимости

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

Суперключ

Суперключ - это набор заголовков столбцов, для которых значения этих объединенных столбцов уникальны для всех строк. Формально:

Суперключ записывается как конечный набор имен атрибутов.

Супер ключ ${displaystyle K}$ выполняется в отношении ${displaystyle (H, B)}$ если:

• ${displaystyle Ksubseteq H}$ и
• не существует двух разных кортежей ${displaystyle t_ {1}, t_ {2} в B}$ такой, что ${displaystyle t_ {1} [K] = t_ {2} [K]}$.

Суперключ держится во вселенной отношений ${displaystyle U}$ если это верно во всех отношениях в ${displaystyle U}$.

Теорема: Супер ключ ${displaystyle K}$ имеет место во вселенной отношений ${displaystyle U}$ над ${displaystyle H}$ если и только если ${displaystyle Ksubseteq H}$ и ${displaystyle Kightarrow H}$ держит в ${displaystyle U}$.

Ключ кандидата

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

Супер ключ ${displaystyle K}$ используется как кандидатный ключ для вселенной отношений ${displaystyle U}$ если он используется как суперключ для ${displaystyle U}$ и нет правильное подмножество из ${displaystyle K}$ который также является суперключом для ${displaystyle U}$.

Функциональная зависимость

Функциональная зависимость - это свойство, согласно которому значение в кортеже может быть получено из другого значения в этом кортеже.

Функциональная зависимость (сокращенно FD) записывается как ${displaystyle Xightarrow Y}$ за ${displaystyle X, Y}$ конечные наборы имен атрибутов.

Функциональная зависимость ${displaystyle Xightarrow Y}$ выполняется в отношении ${displaystyle (H, B)}$ если:

• ${displaystyle X, Ysubseteq H}$ и
• ${displaystyle forall}$ кортежи ${displaystyle t_ {1}, t_ {2} в B}$, ${displaystyle t_ {1} [X] = t_ {2} [X] ~ Стрелка вправо ~ t_ {1} [Y] = t_ {2} [Y]}$

Функциональная зависимость ${displaystyle Xightarrow Y}$ держится во вселенной отношений ${displaystyle U}$ если это верно во всех отношениях в ${displaystyle U}$.

Тривиальная функциональная зависимость

Функциональная зависимость тривиальна под заголовком ${displaystyle H}$ если это верно во всех взаимосвязанных вселенных над ${displaystyle H}$.

Теорема: ФД ${displaystyle Xightarrow Y}$ тривиально под заголовком ${displaystyle H}$ если и только если ${displaystyle Ysubseteq Xsubseteq H}$.

Закрытие

Аксиомы Армстронга: Замыкание набора ФД ${displaystyle S}$ под заголовком ${displaystyle H}$, записанный как ${displaystyle S ^ {+}}$, является наименьшим надмножеством ${displaystyle S}$ такой, что:

• ${displaystyle Ysubseteq Xsubseteq H ~ Rightarrow ~ Xightarrow Yin S ^ {+}}$ (рефлексивность)
• ${displaystyle Xightarrow Yin S ^ {+} land Yightarrow Zin S ^ {+} ~ Rightarrow ~ Xightarrow Zin S ^ {+}}$ (транзитивность) и
• ${displaystyle Xightarrow Yin S ^ {+} land Zsubseteq H ~ Rightarrow ~ (Xcup Z) ightarrow (Ycup Z) in S ^ {+}}$ (увеличение)

Теорема: Аксиомы Армстронга верны и полны; учитывая заголовок ${displaystyle H}$ и набор ${displaystyle S}$ FD, которые содержат только подмножества ${displaystyle H}$, ${displaystyle Xightarrow Yin S ^ {+}}$ если и только если ${displaystyle Xightarrow Y}$ имеет место во всех отношениях вселенных над ${displaystyle H}$ в котором все ФД в ${displaystyle S}$ держать.

Завершение

Завершение конечного набора атрибутов ${displaystyle X}$ при конечном множестве ФД ${displaystyle S}$, записанный как ${displaystyle X ^ {+}}$, является наименьшим надмножеством ${displaystyle X}$ такой, что:

• ${displaystyle Yightarrow Zin Sland Ysubseteq X ^ {+} ~ Rightarrow ~ Zsubseteq X ^ {+}}$

Завершение набора атрибутов можно использовать для вычисления, есть ли определенная зависимость в замыкании набора FD.

Теорема: Учитывая набор ${displaystyle S}$ ФО, ${displaystyle Xightarrow Yin S ^ {+}}$ если и только если ${displaystyle Ysubseteq X ^ {+}}$.

Неснижаемая крышка

Неприводимое покрытие множества ${displaystyle S}$ ФД - это набор ${displaystyle T}$ таких ФД, что:

• ${displaystyle S ^ {+} = T ^ {+}}$
• не существует ${displaystyle Usubset T}$ такой, что ${displaystyle S ^ {+} = U ^ {+}}$
• ${displaystyle Xightarrow Yin T ~ Rightarrow Y}$ это одноэлементный набор и
• ${displaystyle Xightarrow Yin Tland Zsubset X ~ Rightarrow ~ Zightarrow Yotin S ^ {+}}$.

Алгоритм получения ключей-кандидатов из функциональных зависимостей

алгоритм получить ключи-кандидаты из функциональных зависимостей является    Вход: множество S FD, которые содержат только подмножества заголовка ЧАС    выход: набор C суперключей, которые используются в качестве ключей-кандидатов во всех взаимосвязанных вселенных ЧАС в котором все ФД в S держать C : = ∅ // найдены ключи-кандидаты Q := { ЧАС } // суперключи, содержащие ключи-кандидаты пока Q <> ∅ делать        позволять K быть каким-то элементом из Q        Q := Q – { K }        минимальный := истинный        для каждого X-> Y в S делать            K ' := (K – Y) ∪ Икс   // получить новый суперключ если K ' ⊂ K тогда                минимальный := ложный                Q := Q ∪ { K ' }            конец, если        конец для        если минимальный и нет подмножества K в C тогда            удалить все надмножества K из C            C := C ∪ { K }        конец, если    конец пока

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

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

дальнейшее чтение

• Date, C.J .; Дарвен, Хью (2000). Основа для будущих систем баз данных: третий манифест; подробное исследование влияния теории типов на реляционную модель данных, включая комплексную модель наследования типов (2-е изд.). Чтение, MA: Аддисон-Уэсли. ISBN  978-0-201-70928-5.
• ——— (2007). Введение в системы баз данных (8-е изд.). Бостон: образование Пирсона. ISBN  978-0-321-19784-9.

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

• Чайлдс (1968), Возможности теоретико-множественной структуры данных: общая структура, основанная на восстановленном определении отношения (исследование), ручка, HDL:2027.42/4164 цитируется в статье Кодда 1970 года.
• Дарвен, Хью, Третий манифест (ТТМ).
• Реляционные базы данных в Керли
• «Реляционная модель», C2.
• Бинарные отношения и кортежи по сравнению с семантической сетью (Всемирная паутина журнал), вс.