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

Реляционная модель ( RM ) для базы данных управления является подход к управлению данными с использованием структуры и языка в соответствии с предикатной логики первого порядка , впервые была описана в 1969 году английский ученый Кодд , где все данные представлены в терминах кортежей , сгруппированные в отношения . База данных, организованная в терминах реляционной модели, является реляционной базой данных .

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

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

Обзор

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

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

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

Реализация

Там было несколько попыток получить истинную реализацию модели реляционной базы данных , как это изначально было определенно Коддом и объясняется Дата , Darwen и другими, но ни один из них популярных успехов до сих пор. По состоянию на октябрь 2015 года Rel - одна из последних попыток сделать это.

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

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

История

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

Споры

Через несколько лет после публикации своей модели 1970 года Кодд предложил ее версию с трехзначной логикой (True, False, Missing / NULL ) для работы с отсутствующей информацией, и в своей Реляционной модели для управления базами данных версии 2 (1990) он пошел шаг вперед с версией с четырехзначной логикой (Истина, Ложь, Отсутствует, но применимо, Отсутствует, но неприменимо). Они никогда не были реализованы, по-видимому, из-за сложности обслуживания. Конструкция SQL NULL должна была быть частью трехзначной логической системы, но не соответствовала этому из-за логических ошибок в стандарте и его реализациях.

Темы

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

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

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

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

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

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

Relvar является именованным переменным некоторым определенным типа отношения, к которым во все времена некоторого отношение этого типа присваивается, хотя отношение может содержать ноль кортежи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Просмотры без ПРОВЕРИТЬ ВАРИАНТ

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

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

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

НУЛЕВОЙ

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

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

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

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

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

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

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

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

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

Примеры

База данных

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

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

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

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

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

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

Пользовательский ИД	ИНН	Имя	Адрес	[Дополнительные поля…]
1234567890	555-5512222	Рамеш	Южный проспект, 323	…
2223344556	555-5523232	Адам	1200 Main Street	…
3334445563	555-5533323	Светлана	871 Rani Jhansi Road	…
4232342432	555-5325523	Сарфараз	123 Маулана Азад Сарани	…

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

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

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

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

OrderInvoice (Order No, Invoice No)

Теперь относительная переменная 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, a \ in A \}}$

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

Связь

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

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

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

Юниверс отношений над заголовком - это непустой набор отношений с заголовком .${\ 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 K \ substeq H}$ а также
• не существует двух различных кортежей, таких что .${\ displaystyle t_ {1}, t_ {2} \ in B}$${\ displaystyle t_ {1} [K] = t_ {2} [K]}$

Суперключ сохраняется во вселенной отношений, если он выполняется во всех отношениях в .${\ displaystyle U}$${\ displaystyle U}$

Теорема: суперключ имеет место во вселенной отношений тогда и только тогда, когда и выполняется .${\ displaystyle K}$${\ displaystyle U}$${\ displaystyle H}$${\ displaystyle K \ substeq H}$${\ displaystyle K \ rightarrow H}$${\ displaystyle U}$

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

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

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

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

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

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

Функциональная зависимость сохраняется в отношении, если: ${\ displaystyle X \ rightarrow Y}$${\ displaystyle (H, B)}$

• ${\ displaystyle X, Y \ substeq H}$ а также
• ${\ displaystyle \ forall}$кортежи ,${\ displaystyle t_ {1}, t_ {2} \ in B}$${\ Displaystyle t_ {1} [X] = t_ {2} [X] ~ \ Rightarrow ~ t_ {1} [Y] = t_ {2} [Y]}$

Функциональная зависимость сохраняется во вселенной отношений, если она сохраняется во всех отношениях в .${\ displaystyle X \ rightarrow Y}$${\ displaystyle U}$${\ displaystyle U}$

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

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

Теорема: ФД тривиальна под заголовком тогда и только тогда, когда .${\ displaystyle X \ rightarrow Y}$${\ displaystyle H}$${\ Displaystyle Y \ substeq X \ substeq H}$

Закрытие

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

• ${\ displaystyle Y \ substeq X \ substeq H ~ \ Rightarrow ~ X \ rightarrow Y \ in S ^ {+}}$ (рефлексивность)
• ${\ Displaystyle X \ rightarrow Y \ in S ^ {+} \ land Y \ rightarrow Z \ in S ^ {+} ~ \ Rightarrow ~ X \ rightarrow Z \ in S ^ {+}}$ (транзитивность) и
• ${\ Displaystyle X \ rightarrow Y \ in S ^ {+} \ land Z \ substeq H ~ \ Rightarrow ~ (X \ cup Z) \ rightarrow (Y \ cup Z) \ in S ^ {+}}$ (увеличение)

Теорема: аксиомы Армстронга верны и полны; задан заголовок и набор FD, которые содержат только подмножества , если и только если они выполняются во всех взаимосвязанных вселенных, в которых все FD удерживаются.${\ displaystyle H}$${\ displaystyle S}$${\ displaystyle H}$${\ Displaystyle X \ rightarrow Y \ in S ^ {+}}$${\ displaystyle X \ rightarrow Y}$${\ displaystyle H}$${\ displaystyle S}$

Завершение

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

• ${\ displaystyle Y \ rightarrow Z \ in S \ land Y \ substeq X ^ {+} ~ \ Rightarrow ~ Z \ substeq X ^ {+}}$

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

Теорема: дан набор ФД тогда и только тогда, когда .${\ displaystyle S}$${\ Displaystyle X \ rightarrow Y \ in S ^ {+}}$${\ Displaystyle Y \ substeq X ^ {+}}$

Несократимое покрытие

Неприводимое покрытие набора FD - это набор FD, такой что: ${\ displaystyle S}$${\ displaystyle T}$

• ${\ Displaystyle S ^ {+} = Т ^ {+}}$
• не существует такого, что${\ Displaystyle U \ подмножество T}$${\ Displaystyle S ^ {+} = U ^ {+}}$
• ${\ Displaystyle X \ rightarrow Y \ in T ~ \ Rightarrow Y}$ это одноэлементный набор и
• ${\ Displaystyle X \ rightarrow Y \ in T \ land Z \ subset X ~ \ Rightarrow ~ Z \ rightarrow Y \ notin S ^ {+}}$.

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

algorithm derive candidate keys from functional dependencies is
    input: a set S of FDs that contain only subsets of a header H
    output: the set C of superkeys that hold as candidate keys in
            all relation universes over H in which all FDs in S hold

    C := ∅         // found candidate keys
    Q := { H }      // superkeys that contain candidate keys
    while Q <> ∅ do
        let K be some element from Q
        Q := Q – { K }
        minimal := true
        for each X->Y in S do
            K' := (K – Y) ∪ X   // derive new superkey
            if K' ⊂ K then
                minimal := false
                Q := Q ∪ { K' }
            end if
        end for
        if minimal and there is not a subset of K in C then
            remove all supersets of K from C
            C := C ∪ { K }
        end if
    end while

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

использованная литература

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

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

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

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