[Functional dependencies with null markers](https://arxiv.org/pdf/1404.4963.pdf)
# ФУНКЦИОНАЛЬНЫЕ ЗАВИСИМОСТИ С NULL МАРКЕРАМИ

Антонио Бадиа, Даниел Лемир

*Функциональные зависимости (ФЗ) являются неотъемлемой частью дизайна баз данных (БД). ФЗ можно задавать только, когда исключены null маркеры. Однако, null маркеры используются на практике. Чтобы преодолеть этот разрыв между теорией и практикой, исследователи предложили расширения определения ФЗ над отношениями с null маркерами. Несмотря на логичность построений, этим определениям не хватает важных качеств. Например, некоторые их них не удовлетворяют аксиомам Армстронга, являющимися частью фундамента общих методологий БД. Мы описываем набор свойств, которыми должны обладать любые расширения над отношениями с null маркерами. Далее предлагаются два новых расширения ФЗ с этими свойства. Эти расширения позволяют использовать null маркеры там, где они имеют смысл для практиков. Оба удовлетворяют аксиомам Армстронга и обеспечивают реализуемые null маркеры: в любой момент некоторые или все null маркеры могут быть заменены значениями, не вызывая аномалии. Наши предложения могут улучшить дизайн БД.*

[TOC]

## 1. Введение

Функциональные зависимости (ФЗ) являются основой хорошего дизайна реляционной БД. Дизайнеры БД используют ФЗ для определения и обеспечения согласованности; например, если у каждой учетной записи пользователя есть только один cоответствующий основной адрес электронной почты, мы говорим, что учетная запись пользователя однозначно определяет адрес электронной почты (учетная запись пользователя $\rightarrow$ электронная почта).

Надо заметить, что дизайнеры БД не всегда работают напрямую с ФЗ - почти все работают с нормальными формами, которые существуют для поддержки ФЗ.

Между тем, реляционные БД используют null маркеры чтобы справиться с неполной информацией. Действительно, Кодд ввел null маркеры в реляционную модель вместе с 3-значной логикой: сравнение между значением и null маркером имеет "неизвестное значение истинности" ("unknown") [1]. null маркер может отображать что угодно от допустимого, но неизвестного значения, до неприменимого атрибута; может даже указать, что у нас нет информации [2, 3, 4]. Мы советуем читателю обратиться к работе Либкина [5] за обзором прошлых исследований неполной информации в БД.

К сожалению, концепция функциональной зависимости, хоть и занимает центральное место в проектировании реляционных баз данных, не входит в стандарт SQL. Таким образом, ФЗ напрямую не поддерживаются реляционными БД. Примечательно, что при использовании процедурных расширений стандарта SQL, этот язык становится вычислительно полным и, следовательно, может обеспечить ФЗ, используя проверки и триггеры. При этом вся тяжесть обеспечения ФЗ в БД ложится на программиста. Тем не менее, проблема более фундаментальна: **ФЗ не определены при null маркерах**. Таким образом, с теоретической точки зрения, нет существует четкой семантики при наличии ФЗ и null маркеров.

Мы считаем, что тот факт, что ФЗ не определены при наличии null маркеров подрывает роль ФЗ в проектировании БД [6]. Хотя и существуют предложенные определения ФЗ в отношении null маркеров, они оказываются непрактичными.

Наша работа организована следующим образом. В следующем разделе мы выявляем минимальный набор требуемых свойств, которыми должны обладать ФЗ в отношении null маркеров для практического использования. После краткого представления наших условных обозначений в §3, мы рассмотрим два существующих расширения ФЗ на null маркеры в §4: *слабые* и *сильные ФЗ*. Мы покажем, что ни одно из расширений нас не удовлетворяет в данном контексте, поскольку они не обладают желаемыми свойствами. В §5 мы введем два новых расширения: литеральное и суперрефлексивные функциональные зависимости, и покажем, что они обладают нашими свойствами. В §6 мы сравним наши расширения с определениями слабых и сильных ФЗ, чтобы представить читателю контекст для интерпретации. Далее в §7 рассматривается вопрос о том, могут ли новые концепты быть эффективно реализованиы и поддержаны. В §8 мы покажем как расширить стадию логического дизайна БД при помощи одного из предложенных расширений для возможного использования null маркеров . И в финале мы завершим §9 некоторыми комментариями и обсуждением дальнейших исследований.

КОММЕНТАРИЙ: *В первом разделе читатель ознакомился с постановкой проблемы. Несмотря на то, что стандарт SQL остается вычислительно полным, авторы статьи анонсируют исследование проблемы того, что поскольку ФЗ не определены при null маркерах, проектирование БД оказывается непрактичным с точки зрения поступления информации, которая зачастую бывает неполной.*

Примеры таблиц с неполной информацией:
<p>
ТАБЛИЦА 1: Пример отношения с атрибутами профессор, заведующий и кафедра.
</p>
<table>
<tr><th>professor</th><th>chair</th><th>department</th><tr>
<tr><td>Joe</td><td> null </td><td> Mathematic</td></tr>
<tr><td>Joe </td><td> Jill </td><td>Computer Science</td></tr>
<tr><td> Bill </td><td>Arthur</td><td> Mathematics</td></tr>
</table>

ТАБЛИЦА 2: Пример отношения с атрибутами SSN, доход и налогообложение

<table>
<tr><th>SSN</th><th>income</th><th>taxation</th><tr>
<tr><td>1112233</td><td> null </td><td> 15%</td></tr>
<tr><td>1112233 </td><td> null</td><td>25%</td></tr>
</table>

## 2. Желаемые свойства
Стандарт SQL допускает null маркеры, но не ссылается на ФЗ [7]. Можно было бы утверждать, что раз концепции ключевых полей и внешних ключей явно присутствуют в стандарте SQL и, учитывая, что понятие ключей и ФЗ тесно связаны, может показаться, что таким образом ФЗ поддерживаются механизмами ограничений на ключи [8]. Однако, когда мы реализуем ФЗ с помощью ограничений на ключи (первичные и внешние), мы должны быть уверены, что совокупность таблиц БД приведена к нормальной форме Бойса-Кодда (НФБК). Важно отметить, что такая нормальная форма *исключает* часто используемые на практике null маркеры.
Кодд был хорошо осведомлен о предполагаемых проблемах с null маркерами. Но он не уделял внимание проблеме невозможности поддержки ФЗ при наличии null маркеров. Он считал, что такие понятия, как ключи, нормализация и ФЗ применяются только тогда, когда null маркеры заменены фактическими значениями:

*Должно быть ясно, что поскольку nulls (или, как они теперь называются, метки) НЕ значения БД, правила функциональной зависимости — и многозначной зависимости - к ним не применяются... (Э. Ф. Кодд [1])*

Рассмотрим соотношение в таблице 1 с учетом заданных ФЗ: `профессор → заведующий` (professor→chair) и `кафедра → заведующий` (department→chair). Зная, что Джилл и Артур разные люди, заменить null маркер фактическим значением невозможно (но знает ли об этом программист, реализующий ФЗ с помощью проверок и триггеров?). Возврашаясь к варианту Кодда, имеем, что *ключи, нормализация и ФЗ* никогда не будут применимы ко всем строкам такого информационно неполного отношения. Это будет считаться *аномалией*.

Чтобы избежать подобных проблем, мы устанавливаем в качестве *первой цели*, что если ФЗ применяется в отношении с null маркерами, то всегда должна быть возможность заменить некоторые или все null маркеры фактическими значениями без нарушения ФЗ (Ц1). В таком случае мы утверждаем, что такие *ФЗ реализуемы при null маркерах*. Более того, поскольку мы рассматриваем множества ФЗ для проектирования (в отличие от единичных табличных и эмпирических ФЗ), мы утверждаем, что ФЗ должны быть определены так, что если множество ФЗ применяется в отношении с null маркерами, то должна быть возможность заменить некоторые или все null маркеры, не нарушая ни одного из ФЗ в наборе, (**сильная Ц1**).

Для определения ФЗ при наличии null маркеров нас также интересуют *три аксиомы Армстронга* и, в первую очередь, транзитивность:
1. Рефлексивность: если $Y ⊆ X$, то $X → Y$ .
2. Дополнение: имеем, что $X → Y$ влечет $XZ → YZ$.
3. Транзитивность: если $X → Y$ и $Y → Z$, то $X → Z$.

Например, мы можем сказать, что (согласно естественным требованиям учета финансов в заданном отчетном периоде) ваш номер социального страхования (SSN) определяет ваш доход (`SSN → income`), и что ваш доход (в период действия текущих налоговых условий) определяет вашу налоговую категорию (`income → taxation`). Если транзитивность сохраняется, то ваш SSN *должен* определять вашу налоговую категорию (`SSN → taxation`).
Интерпретация Кодда (утверждающая, что ФЗ не применяется, когда есть null маркеры) не удовлетворяет аксиоме транзитивности в следующем смысле: пусть даны ФЗ `SSN → income` и `income → taxation`, тогда, хотя каждая из строк в Таблице 2 допустима по отдельности, не следовало бы увидеть такие совокупные данные в БД. Это означает, что транзитивная ФЗ `SSN → taxation` не выполняется в целом (хотя должна была бы выполняться по аксиоме транзитивности, если БД корректно поддерживает ФЗ). Обратите внимание на то, что в значениях атрибутов `SSN` и `taxation` нет null маркеров!
Кодд, несомненно, ответил бы, что нет нарушения транзитивности, так как ФЗ не применяются при наличии null маркеров. Но мы хотим рассмотреть *нулевые маркеры как неотъемлемую часть БД*.
Несоблюдение аксиом Армстронга имело значительные последствия. Во-первых, без этих аксиом нормализации уже недостаточно для обеспечения соблюдения ФЗ. С точки зрения практики, любые переопределения ФЗ, которые не удовлетворяют аксиомам Армстронга, не могут быть обеспечены только нормализацией. Действительно, для базы данных $D$ и множества ФЗ $F$ на $D$, перед тем как мы сможем использовать $F$ для определения нормальной формы для отношений в $D$, мы должны убедиться, что $F$ находится в минимальной или канонической форме [9]. Но минимализация $F$ значительно зависит от ФЗ, учитывающих транзитивность, как описано в стандартных учебниках по БД.

Можно было бы отказаться от нормализации и обеспечивать выполнение ФЗ другими способами. В таком случае может показаться, что аксиомы Армстронга больше не являются необходимыми. Например, мы могли бы подумать, что можно проектировать структуру БД без предположения, что ФЗ являются транзитивными (что на самом деле очень опасно). Однако такие ослабленные ФЗ не практичны и по другим причинам. Первая проблема с которым мы сталкиваемся, это то, что методологии стандартного дизайна БД, такие как модель «сущность-связь», неявно предполагают аксиомы Армстронга и в частности транзитивность [10].

Мы считаем, что разработчики баз данных столкнутся с трудностями, справляясь с отсутствием транзитивности (см., например, Таблицу 2, где интуитивно можно было бы ожидать увидеть для одного и того же SSN одно и то же налогообложение), и, следовательно, мы требуем, чтобы аксиомы Армстронга выполнялись, хотя такое требование может показаться слишком сильным. Конечно, мы могли бы помочь дизайнерам с дополнительными инструментами и методологиями (например, [11]), чтобы компенсировать ослабление ограничений аксиом Армстронга. Тем не менее, при прочих равных, мы считаем желательным, чтобы **новое определение ФЗ при наличии null маркеров учитывало аксиомы Армстронга (Ц2)**, а также позволяло применять реализуемые null маркеры.

Конечно, наши цели на данный момент могут быть достигнуты путем ограничения использования null маркеров. Может даже показаться, что null маркеры должны всегда запрещаться (смотри, например, [12]). Но *мы хотим разрешить обычное использование null маркеров*, часто наблюдаемое в реальных приложениях.
Например, мы заметили, что многие схемы БД позволяют null маркеры для атрибутов, которые не определяют другие атрибуты. Таким образом, еще одна цель (Ц3) этого исследования - **разрешить null маркеры тогда, когда это можно, не нарушая других целей дизайна**. Как минимум, мы должны разрешить null маркеры, избегая необходимости придумывать контрпримеры.

Наконец, любая проверка и поддержка ФЗ будет рассматривается, с точки зрения транзакции или обработки запросов, как дополнительные ограничения — точно так же, как применение ограничений первичного и внешнего ключа. Таким образом, **любое определение ФЗ для null маркеров должно быть вычислительно недорогим (Ц4)**. На практике это означает, что мы исключаем изящные, но сложные модели, такие как v-таблицы ([13]). Например, мы должны быть в состоянии определить, выполняется ли ФЗ $X → Y$ при рассмотрении исключительно атрибутов в $X$ и $Y$.
Подводя итог, мы стремимся расширить ФЗ, включив в него null маркеры таким образом, что:

1. Ц1: ФЗ допускают реализуемые null маркеры. Дальше это должно выполняться для наборов ФЗ (сильный Ц1).
2. Ц2: аксиомы Армстронга выполняются.
3. Ц3: ФЗ не должны ограничивать использование null маркеров без особой необходимости.
4. Ц4: Обеспечение соблюдения ФЗ должно быть вычислительно практичным.

КОММЕНТАРИЙ: *Во втором разделе были сформулированы цели, которые авторы ставят перед собой. Были выявлены и обоснованы изъяны логики Кодда. Он был убежден в том, что нормализация или ФЗ применяются только тогда, когда null маркеры заменены на фактические значения. Однако оказывается, что, пользуясь таким ограничением, для некоторых отношений ключи, нормализация или ФЗ оказываются неприменимыми. Авторы статьи утверждают, что это является проблемой. Таким образом, первой целью в формулировке свойств ФЗ становится возможность заменять null маркеры на фактические значения без нарушения ФЗ. Усилением цели будет аналогичный результат для множества ФЗ.
Кроме того, авторы обращают внимание на то, что мы хотим выполнимости аксиом Армстронга. Даже сделав предположение об их кажущимся излишестве в дизайне БД, авторы объясняют, что мы всё равно получим неявную необходимость аксиом. Авторы обращают внимание на то, что нам важно сформулировать свойства практичными: их использование должно быть вычислительно дешевым. Также заметим, что мы не хотим ограничивать возможности использования null маркеров ради выполнения наших свойств.*

## 3. Основные концепции
Пусть отношение $r$ такое, как в SQL: конечное мультимножество строк над заданой схемой $sch(r)$, с оговоркой, что строка может содержать null маркеры. Будем называть две строки дублирующими, если все ненулевые атрибуты равны и любой null маркер в одной строке соответствует null маркеру в другой строке; в противном случае строки различны.
Мы предполагаем, что существует бесконечное множество V значений, из которого взяты все значения в любом отношении. Эти значения имеют отношение '$=$', определенное на них,
которое является рефлексивным, симметричным и транзитивным: для любого $x, y, z ∈ V$ , имеем, что $x = x, (x = y) ⇒ (y = x) и (х = у, у = z) ⇒ х = z$. Следовательно, отношение «=» является отношением эквивалентности.

Пусть дан атрибут $A$ в схеме отношения $r$ и строка $t$. Мы обычно используем $t[A]$ для обозначения значения $t$ для $A$. Это распространяется на наборы атрибутов $X ⊆ sch(r)$. Затем скажем, что для двух строк $t$ и $t' t[A] = t'[A]$ истинно, если оба $t[A]$ и $t'[А]$ равны не-null значения; ложно, если и $t[A]$, и $t'[А]$ являются различными значениями; и иначе неизвестно
(т. е. если одно из значений $t[A]$ или $t'[A]$, а возможно и оба, равны null маркеру). Еще раз, это распространяется на наборы атрибутов $X ⊆ sch(r)$ обычным образом: для двух строк $t, t' t[Х] = t'[X]$ истинно, если $t[A] = t'[А]$ истинно для каждого $А ∈ Х$; ложно, если $t[A] = t[A]$ ложно для некоторого $A ∈ X$, и иначе неизвестно.
Для сокращения мы пишем $t = t'$ для $t[sch (r)] = t'[sch (г)]$. Обозначим через $π_{X}(r)$ проекцию всех строк в $r$ на $X$: начиная с {$t[X]|t ∈ r$}, все дублирующие строки удалены.
Пусть $r$ — фиксированное отношение. Если мы запретим null маркеры по $r$, то ФЗ $X → Y$ выполняется, если $t[Y] = t'[Y]$ когда две строки $t, t'$ такие, что $t[X] = t'[Х]$. В этом контексте (где null маркеры запрещены), ФЗ удовлетворяют аксиомам Армстронга. Мы также можем формализовать понятие ключа, если в r нет null маркера. Множество атрибутов K является суперключом тогда и только тогда, когда $K → A$ выполняется для любого атрибута $A ∈ sch(r)$; и ключ, если он минимальный суперключ. Первичные ключи в SQL — это ключи с атрибутами, где null маркеры запрещены; SQL допускает null маркеры в других ключах.
Мы говорим, что атрибут A не-null в отношении $r$, если для всех $t ∈ r$ имеем, что $t[A]$ не-null. Пусть дан набор атрибутов $X$, мы говорим, что null маркер, появляющийся в строке $t$ в атрибуте $A (t[A] = null)$, находится в $X$, если $А ∈ Х$.

## 4. Слабые и сильные ФЗ

Левен и Луазу [14] предлагают одно из немногих расширений ФЗ над null маркерами. Мы формализуем их определения следующим образом. Оценка $ϕ$ для отношения $r$ присваивает каждому null маркеру в строке значение из $V$ — каждый null маркер может получить другое значение, при этом оставляя не-null значения из V без изменений. Для заданного отношения $r$ каждое $ϕ(r)$ называется возможным миром для $r$. Семантика ФЗ с mull маркерами, как это определено Левеном и Луазу, следует идее модальной логики [15]: у нас есть два разных прочтения, в зависимости от того, выполняется ли ФЗ в некоторых или во всех возможных мирах.

**Определение 4.1.** ФЗ $F$ выполняется слабо в отношении $r$ тогда и только тогда, когда F выполняется в возможном мире для $r$, т. е. существует нормирование $ϕ$ такое, что $F$ выполняется в $ϕ(r)$. F называется слабой ФЗ (СлФЗ).
**Определение 4.2.** ФЗ $F$ сильно выполняется в отношении
$r$ тогда и только тогда, когда $F$ выполняется во всех возможных мирах для $r$, т. е. для каждой оценки $ϕ$ для $r$, $F$ выполняется в $ϕ(r)$. $F$ называется сильной ФЗ (СФЗ).

Возвращаясь к таблице 1, рассмотрим следующие ФЗ:
кафедра → профессор и профессор → заведующий. Оба выполняются
слабо, в то время как ни то, ни другое не выполняется сильно (см. табл. 3).

ТАБЛИЦА 3: Различные ФЗ, применяемые к отношению
из Таблицы 1 и Выполняются ли они сильно, слабо, суперрефлексивно или литерально.

<table>
<tr><th></th><th>SFD</th><th>WFD</th><th>SRFD</th><th>LFD</th> </tr>
<tr><td>chair → professor</td><td>no</td><td>yes</td><td>no</td><td>yes</td></tr>
<td>professor → chair</td><td>no</td><td>yes</td><td>yes</td><td>no</td>
</table>

Сильная ФЗ всегда является также и слабой ФЗ. Сильные ФЗ удовлетворяют аксиомам Армстронга, а слабые ФЗ — нет. Когда ФЗ сильно соблюдается, мы можем заменить любой null маркер на значение, и ФЗ остается в силе. Фактически, сильные ФЗ обеспечивают реализуемые null маркеры. Модель Левена и Луазу имеет значительные формальные недостатки, но она также имеет некоторые недостатки с прагматической точки зрения:

• Слабые ФЗ могут быть слишком слабыми. Даже если каждая ФЗ в множестве $F$ ФЗ выполняется слабо, может не быть ни одного мира $ϕ(r)$, в котором все ФЗ в множестве F выполняются. См. в Таблице 1 контрпример: оба ФЗ (профессор → заведующий и заведующий → профессор) выполняются слабо, но нет возможного мира, где они оба выполняются. То есть мы можем заменить некоторые значеная null маркера для удовлетворения первой ФЗ, и подставить другое значение, чтобы удовлетворить второе ФЗ, но ни одно значение не делает обе ФЗ истинными одновременно (таким образом, $F$ не обладает свойством сильной Ц1). Это верно даже когда каждый атрибут появляется только один раз в правой части ФЗ: пусть дана схема $A, B, C$ и ФЗ $A → B$ и $B → C,$ набор строк (a, null, b) и (a, null, c) удовлетворяет оба ФЗ слабо, но нет мира, где бы они оба выполнялись. Этот последний пример также иллюстрирует, что слабые ФЗ не транзитивны: $A → B$ и $B → C$
может выполняться слабо, а $A → C$ — нет. То есть, слабые ФЗ не удовлетворяют аксиомам Армстронга (таким образом не достигается Ц2). Мы могли бы исправить слабые ФЗ, чтобы гарантировать, что они обеспечивают, например, null маркеры, требуя существание оценки, соответствующей совокупности всех ФД. Однако это может оказаться вычислительно сложно (следовательно, не достигается Ц4).

• Сильные ФЗ могут быть слишком сильными (таким образом, несостоятельность Ц3). Действительно, кажется ненужным всегда требовать, чтобы ФЗ выполнялись во всех возможных мирах. Например, рассмотрим схемы $A, B, C$ и ФЗ $A → B$ и $B → C$, а набор строк (a, b, null) и (c, b, null). Хотя это похоже на разумное соотношение, ФЗ $B → C$ не выполняется сильно.

В каком-то смысле слабые и сильные ФЗ это две крайности, тогда как правильное решение может быть где-то между. Действительно, для любой формы ФЗ, что поддерживает реализуемые null маркеры (Ц1) на каждом базисе ФЗ, будет эквивалентна или сильнее, чем слабая ФЗ. Между тем, сильные ФЗ обладают свойствами, которые мы ищем, за исключением того, что они слишком ограничительны (Ц3).

КОММЕНТАРИЙ: *В четвертом разделе мы рассмотрели некоторые существующие расширения ФЗ на null маркеры, предложеные Левеном и Луазу. Однако выяснилось, что оба расширения не удовлетворяют поставленные нами цели. Слабая ФЗ не удовлетворяет аксиомам Армстронга (транзитивность). Кроме того, она нам не позволяет достичь сильной Ц1, поскольку предлагает заменять null маркеры различными значениями на разных ФЗ. Предложение сильных Фз, в свою очередь, оказывается излишне ограничивающим, т.е. не удовлетворяет Ц3.*

## 5. Литеральные и суперрефлексивные ФЗ
Мы предлагаем два альтернативных определения понятия
ФЗ в присутствии null маркеров. Первый является естественным расширением трехзначной логики, предложенное Коддом и использующееся в SQL.

**Определение 5.1.** ФЗ $X → Y$ выполняется суперрефлексивно, если для любых двух строк $t, t'$, когда $t[X] = t'[X]$ не ложно (т. е. либо истинно, либо неизвестно), то $t[Y]=t'[Y]$ также не является ложным. Мы говорим, что X → Y является суперрефлексивной ФЗ (СРФЗ).

В этом первом определении null маркер приранивается любому другому значению (т.е. null = a рассматривается как
истина для любого значения а), отсюда и термин "суперрефлексивный" (СР).
В качестве иллюстрации рассмотрим табл. 1. Имеем, что профессор → заведующий выполняется суперрефлексивно, тогда как заведующий→профессор нет (см. табл. 3).
Наше второе определение напоминает о том, как такие языки как JavaScript, обрабатывают null маркеры. Как первое приближение, они считают null как обычное значение, для которого null = null всегда истинно (т. е. «=» остается рефлексивным отношением), но null = $a$ всегда ложно для любого не-null $а$.
Мы говорим, что $t[A]$ и $t'[A]$ идентичны, если оба содержат null или оба содержат одно и то же значение; это также распространяется на набор атрибутов X и на целые строки обычным образом: $t[X]$ идентично $t'[X]$ тогда и только тогда, когда $t[A]$ и $t'[A]$ одинаковы для всех $A ∈ X$.

**Определение 5.2.** ФЗ $X → Y$ выполняется литерально, если для любых двух наборов $t, t',$ если $t[X]$ и $t'[Х]$ идентичны, то $t[Y]$ и $t'[Y]$ также идентичны. Мы говорим, что $X → Y$ является литеральным ФЗ (ЛФЗ).

Рассмотрим еще раз табл. 1. В отличие от суперрефлексивного случая, мы имеем, что ФЗ заведующий → профессор выполняется литерально, тогда как профессор → заведующий - нет. (См. снова Таблица 3.)
Есть альтернативные определения, которые мы могли бы использовать. Например, мы могли бы определить, что ФЗ $X → Y$ выполняется, если при истинном $t[X] = t'[X]$ (согласно 3-значной логике Кодда) $t[Y] = t'[Y]$ должно быть истинным. Или мы могли бы определить, что ФЗ $X → Y$ выполняется, если при $t[X] = t'[Х]$ не ложном $t[Y] = t'[Y]$ должно быть истинным; или если когда $t[Х] = t'[X]$ верно, тогда $t[Y] = t'[Y]$ не должно быть ложным.
Однако эти альтернативные определения неудовлетворительны: они не удовлетворяют аксиомам Армстронга (Ц2) или не разрешают null маркеры там, где они обычно используются (Ц4). Напротив, определения 5.1 и 5.2 имеют свойства, которые мы требовали в §2, начиная с аксиом Армстронга (которые следуют путем проверки). Например, что касается транзитивности, рассмотрим две ФЗ $X → Y$ и $Y → Z$, которые выполняются суперрефлексивно (соотв. литерально). Пусть даны две строки $t, t'$ такие, что $t[X]=t'[Х]$ не является ложным (соответственно $t[X]$ и $t'[X]$ одинаковы), тогда $t[Y] = t'[Y]$ не является ложным (соответственно $t[Y]$ и $t'[Y]$ являются идентичными), откуда следует, что $t[Z] = t'[Z]$ не является ложным (соответственно $t[Z]$ и $t'[Z]$ идентичны). Таким образом, мы имеем это $X → Z$, что и доказывает транзитивность.

**Лемма 5.1.** *Сверхрефлексивные и буквальные FD выполняют аксиомы Армстронга (Ц2).*

Прежде чем мы перейдем к установлению других свойств,
нам нужен технический результат, который делает другие доказательства полегче. Во-первых, мы можем проверить, что все ФЗ можно разложить на ФЗ, где правая часть содержит один атрибут. Например, ФЗ профессор → {заведующий, кафедра} эквивалентна следующим двум ФЗ:

• профессор → кафедра, и
• профессор → заведующий.

**Лемма 5.2.** Мы имеем, что $X → Y$ для $Y = \{А_{1}, . . . A_{n}\}$ эквивалентно $(X − \{A_{1}\} → \{A_{1}\})∧ · · · ∧ (X − \{A_{n}\} → \{A_{n}\})$ рассматриваем ли мы слабые, сильные, литеральные или суперрефлексивные ФЗ.

Доказательство этой леммы следует из проверки. Следовательно, достаточно рассмотреть ФЗ $X → Y$, где $Y$ — одноэлементное множество, непересекающееся с $X$. Во-первых, мы должны показать, что СРФЗ и ЛФЗ удовлетворяют условию Ц1: null маркеры реализуемы. Мы начали с СРФЗ. Покажем, что для СРФЗ $X → Y$, все null маркеры в $X ∪ Y$ реализуемы относительно $Х → Y$.
Чтобы показать этот результат, рассмотрим Таблицу 1.
где профессор → заведующий выполняется сверхрефлексивно: мы можем заменить Jill на null маркер, не нарушая ФЗ.

**Лемма 5.3.** Рассмотрим СРФЗ $X → Y$ в отношении такое, что $X$ и $Y$ не пересекаются, а $Y$ является одноэлементным.
1. Мы можем заменить любой null маркер в X на любое фактическое значение без нарушения СРФЗ $X → Y$.
2. Мы можем заменить любой null маркер в $r$ в $Y$ на хотя бы одно фактическое значение без нарушения СРФЗ $X → Y$, предполагая, что атрибуты в $X$ не-null.

Доказательство. Предположим, что СРФЗ изначально удовлетворяется в $r$.
(1) Предположим, мы заменили null маркер в атрибуте
$B ∈ X$. Что касается СРФЗ $X → Y$, то следующее может произойти для двух строк $t, t'$:
• если $t[X] = t'[X]$ было ложным, то оно все еще ложно: это не повлияет на СРФЗ
• если $t[X] = t'[X]$ было истинным, то оно все еще такое: это не может повлиять на СРФЗ;
• если $t[X] = t'[X]$ было неизвестным, то оно может стать правдой или ложью. Из-за СРФЗ $X → Y$ и того, что $t[X]=t'[X]$ не было ложным, мы имеем, что $t[Y]=t'[Y]$ не является ложным. Следовательно, если наборы $t, t'$ удовлетворили СРФЗ перед обновлением, они должны удовлетворить его и после обновления.

Поскольку все пары строк удовлетворяют условиям СРФЗ после обновления, СРФЗ все еще выполняются, что доказывает
первую часть результата.

(2) Предположим, что атрибуты в X не равны null. Мы хотим показать, что мы можем заменить любой null маркер в Y на фактическое значение. Выберите строку $t$ в $r$, где $t[Y]$ содержит null маркер. Рассмотрим множество $τ$ элементов $t'$ такое, что что $t'[X] = t[X]$ не ложно. (Поскольку атрибуты в $X$ не равны null, мы имеем, что «$t'[X] = t[X]$ не ложно» эквивалентно «$t'[X] = t[X]$ истинно».) Имеем, что проекция $τ$ на $Y$ содержит не более одного актуального значения. (Предположим, что это не так, тогда можем найти строки $t''$ и $t'''$ из $τ$ такие, что $t''[Х] = t'''[X]$ не является ложным, но $t''[Y]=t'''[Y]$ — ложь.) Если имеется одно фактическое значение, установим $t[Y]$ к этому значению; если нет, выберем значение случайным образом. Эта модификация явно не нарушает СРФЗ $X → Y$, но он устраняет один null маркер.

Чтобы понять, почему из леммы 5.3 следует, что СРФЗ удовлетворяют Ц1 рассмотрим любой СРФЗ $X → Y$ над заданным отношением.
Мы можем заменить фактические значения вместо любого null маркера в атрибуте $X$ по первой части леммы. В качестве второго шага, поскольку атрибуты в X стали не-null, мы можем заменить фактические значения на любой null маркер в $Y$. Что касается ЛФЗ, мы собираемся доказать нечто более сильное: что они удовлетворяют сильную Ц1.

Лемма 5.4. ЛФЗ строго обеспечивает реализуемые null маркеры (сильная Ц1).
Доказательство. Для доказательства Ц1 достаточно заменить все null маркеры на единственное $v ∈ V$, еще не входящее в отношение. По проверке это распространяется на наборы ФЗ, поэтому мы получаем также сильную Ц1 этим методом.

У нас есть то, что ЛФЗ и СРФЗ обеспечивают реализуемые null маркеры. То есть при наличии отношения с набором ФЗ, мы всегда можем заменить null маркеры на некоторые фактические значения, не нарушая ФЗ. Фактически, если мы добавим дополнительное ограничение на СРФЗ, они оба сильно обеспечивают реализуемые null маркеры (в смысле сильной Ц1). В связи с этим мы принимаем практическое соглашение о том, что некоторые атрибуты могут содержать null маркеры, в то время как другие не могут: это мотивировано стандартом SQL. Для набора ФЗ $F$ мы говорим, что атрибут $B$ определяет другой атрибут $A$ под $F$, если существует ФЗ $B ∈ X → Y, A ∈ Y$ в транзитивном замыкании $F$. Естественно, это свойство транзитивно: если $A$ определяет $B$ и $B$ определяет $C$, тогда $A$ определяет $C$. (По соглашению мы опускаем петли в $F$: $X → X$.)

Состояние 1ПЧ. Рассмотрим множество ФЗ $F$ над связью. Рассмотрим любой атрибут $A$, который может содержать null маркеры. Тогда A должна стоять справа не более чем от одной ФЗ из множества ФЗ $F$ связи. Более того, пусть даны два различных атрибута, которым разрешено содержать null маркер, $A$ и $B$, и если $A$ определяет $B$, то $В$ не может определить $А$.

РИС. 1: Иллюстрация, использованная для доказательства Леммы 5.5 для множества ФЗ $\{\{E, D\} → \{A\}, \{A\} → \{F\}, \{A, B\} → \{F\}\}$.

РИС. 2: Диаграмма Венна, которая иллюстрирует Лемму 6.1

Мы подчеркиваем, что условие 1ПЧ относится только к атрибутам, для которых разрешены null маркеры: ограничение для других атрибутов не требуется.

На рис. 1 приведен пример набора ФЗ, удовлетворяющих условию 1ПЧ, даже если для всех атрибутов разрешены null маркеры: $\{E, D\} → \{A\}, \{A\} → \{F\}, \{А, В\} → \{F\}$. Однако, если мы заменим единственную ФЗ $\{E, D\} → \{A\}$ двумя ФЗ, такими как $\{E\} → \{A\}$ и $\{D\} → \{A\},$ нам нужно добавить требование, что A не null, чтобы удовлетворить 1ПЧ. Точно так же, если мы добавим ФЗ $\{F\} → \{A\}$ в дополнение к существующему ФЗ $\{A\} → \{F\}$, нам нужно потребовать, чтобы оба A и F были не null, поскольку $F$ будет определять $A$, в то время как $А$ определяет $F$.

**Лемма 5.5.** СРФЗ сильно обеспечивает реализуемые null маркеры всякий раз, когда выполняется условие 1ПЧ (сильная Ц1).

Доказательство. Предположим не ограничивая общности, что все СРФЗ в наборе имеют вид $X → Y$, где $Y$ является одноэлементным, а $X$, $Y$ не пересекаются.

Построим граф, где каждый атрибут, для которого разрешены null маркеры — это узел, и есть ребро между двумя атрибутами $А, В$ тогда и только тогда, когда $А$ определяет $В$. Проиллюстрируем такой граф на рис. 1, где для простоты, мы опустили некоторые ребра, которые подразумеваются транзитивностью.
Временно предположим, что граф не пуст. Из-за условия 1ПЧ граф должен быть бесцикловым, а значит, некоторые из вершин должны быть нулевой в степени (например, $E$ и $D$ на рис. 1). Назовем этот набор узлы/атрибуты $A_0$.
Согласно лемме 5.3, мы можем заменить фактические значения для любого null маркера, который они содержат. Действительно, рассмотрим такой атрибут $A ∈ A_0$. Этот атрибут появляется в правой части не более чем одного ФЗ в наборе (назовем это $F_А$), однако $A$ может появиться слева от несколькоких ФЗ. Эти ФЗ не вызывают беспокойства: замена null маркера в атрибуте $A$ никогда не нарушает суперрефлексивность ФЗ по первой части леммы 5.3. Между тем, поскольку $F_А$ таково, что ни один атрибут в его левой части не содержит null маркер, затем вторая часть леммы 5.3 говорит нам, что null маркеры $A$ реализуемы.

После подстановки фактических значений вместо любого null маркера в атрибутах $A_0$ удалим эти узлы из графа. Снова должны быть узлы с нулевой степенью вхождения ребер (например, узел $A$ на рис. 1) или граф пуст. Повторим процесс, пока граф не станет пустым. Атрибуты, которые либо не появляются как часть какого-либо ФЗ или которые не могут содержать нулевые маркеры, нас не беспокоят.

## 6. Сравнение ФЗ

Теперь мы можем охарактеризовать ЛФЗ и SRFD должным образом. Мы можем связать ЛФЗ и СРФЗ с друг с другом, а также с определениями Левена и Луазу. Все они являются консервативными расширениями классической концепции: в таблице без null они совпадают с классическими ФЗ. Однако, как правило, ЛФЗ и СРФЗ несравнимы, как показано в таблице 3.
Мы показываем, что сильная ⇒ суперрефлексивная ⇒ слабая и сильная ⇒ литеральная ⇒ слабая (см. рис. 2). То есть оба ЛФЗ и СРФЗ сильнее слабых ФЗ, тогда как сильные ФЗ сильнее, чем ЛФЗ и СРФЗ.

**Лемма 6.1.** Справедливо следующее:
1. Если ФЗ $X → Y$ выполняется буквально, то выполняется слабо.
2. Если ФЗ $X → Y$ выполняется суперрефлексивно, то она выполняется слабо.
3. Если ФЗ $X → Y$ выполняется строго, то оно должно выполняться буквально и суперрфлексивно.

Доказательство. Предположим не ограничивая общности, что $X$ и $Y$ не пересекаются и что $Y$ является одноэлементным.
(1) Если ФЗ $X → Y$ выполняется литерально, то мы можем заменить любой null маркер любым $v ∈ V$, которое еще не присутствует в отношении, и ФЗ все еще выполняется. Это показывает, что литеральные ФЗ сильнее чем слабые ФЗ.
(2) По лемме 5.3 можно построить такую оценку, что суперрефлексивная ФЗ корректна в конвенционном смысле. Благодаря существованию оценки мы имеем, что $X → Y$ выполняется слабо.
(3) Сначала докажем, что из сильной ФЗ следует суперрефлексивность.
Предположим, что $X → Y$ выполняется сильно. Рассмотрим две строки $t, t'$. Если $t[X] = t'[X]$ не ложно (в трехзначной логике Кодда), то в каком-то возможном мире $t[X] = t'[Х]$ должно выполняться. В таком возможном мире $t[Y] = t'[Y]$ должно выполняться, откуда следует, что $t[Y] = t'[Y]$ не должно быть ложным (в трехзначной логике Кодда). Это доказывает, что из сильной ФЗ следует суперрефлексивная ФЗ.
Мы доказываем, что из сильной следует литеральная. Предположим, что ФЗ $X → Y$ выполняется сильно и что $t[X]$ и $t'[Х]$ идентичны. (Мы предполагаем, что $X$ и $Y$ не пересекаются и $Y$ является одноэлементным, как было сказано ранее.) Существуют некоторые миры, где $t[X] = t'[Х]$ верно. Если $t[Y]$ и $t'[Y]$ не идентичны, то хотя бы в одном из этих миров они будут отличаться. То есть, если у кого-то есть null маркер в $t[Y]$ и значение $a$ в $t'[Y]$ (и наоборот) мы можем заменить null маркер на значение, отличное от $a$. Следовательно, мы должны иметь, что $t[Y]$ и $t'[Y]$ идентичны. Поэтому из сильных ФЗ следуют литеральные ФЗ. Это завершает доказательство.
Мы можем убедиться, что ЛФЗ и СРФЗ строго слабее, чем СФЗ. Напомним, что по схеме $A, B, C$ и ФЗ $A → B$ и $B → C$ множество строк (a, b, null) и (c, b, null) нарушает сильную ФЗ $B → C$. Однако оно удовлетворяет ФЗ $A → B$ и $B → C$ литерально и ссуперрефлексивно. Тот факт, что ЛФЗ и СРФЗ позволяют использовать null маркеры, подтверждает наше утверждение, что они без необходимости не запрещают null маркеры где они могут иметь смысл (Ц3).

## 7. Вычислительная эффективность
Остается вопрос об эффективной реализации предложенных нами концепций (Ц4). Здесь мы покажем, что оба ЛФЗ и СРФЗ могут быть реализованы по стоимости, близкой к применению обычных ФЗ. Поскольку SQL не применяет ФЗ напрямую, мы сравниваем с тесно связанным свойством - стоимостью обеспечения исполнения ключа ограничения в отношении. Это предполагает, что база данных находится в соответствующей нормальной форме, такой что применение ключей эквивалентно применению ФЗ. Пусть дано отношение $r$, если $X ⊆ r$ объявлен как первичный ключ для $r$, любая вставка $t ∈ r$ проверяется, чтобы убедиться, что $X$ остается ключом. На практике системы реляционных БД запрещают появление двух различных строк $t, t'$, согласующихся на $X$ ($t[X] = t'[X]$ должно быть ложью). Это может быть достигнуто путем создания индекса (традиционно древовидного индекса) на $X$: при вставке $t$ мы ищем любое $t' ∈ r$, для которого $t[Х] = t'[X]$ (обратите внимание, что null маркеры запрещены в первичном ключе). Вызовим набор строк, полученный в результате поиска $S$. При вставке, если $S = ∅$, вставку можно продолжить; иначе для каждого $t' ∈ S$ проверяем, правда ли, что $t'$ идентичен $t$. Если это так, вставка может продолжаться; иначе это запрещено. Обновления обрабатываются аналогичным способом. Сложность этой процедуры оценивается $\mathcal{O}(\log{}|r|)$ при использовании древовидного индекса, поскольку ожидается, что $|S|≤ 1$. (Конечно, мы можем получить ожидаемую константную временную сложность с использованием индекса на основе хэша.)
Мы также можем напрямую применять ФЗ, независимо от того, являются ли они литеральными или сверхрефлексивными. Пусть дано отношение $r$ и произвольная ФЗ $X → Y$, на нем мы создаем индекс на $X$ — для конкретности, мы предполагаем, что $B∗$ -дерево индекс, так как они доступны почти в любой системе БД.
Имея индекс, достаточно проверить разрешена ли вставка новой строки $t$. Действительно, обновление можно рассматривать как удаление, за которым следует вставка, а удаления не могут нарушать ФЗ.
Имея индекс, применять ЛФЗ не сложно. Мы строим единственный индекс на $X$, рассматривая объединение всех атрибутов — следуя лексикографическому порядку, с null маркерами в отдельных атрибутах вместе в начале или в конце своих позиций. То есть в индексе для атрибутов ABC строка $(a_1, b_1, null)$ будет идти до или после всех строк $(a_1,b_1,c)$, для $c$ любого значения из $C$; строка $(a_1, null, b_1)$ будет идти до или после любых строк $(a_1, c, b_1)$ для c любого значения из $С$; и так далее.
Это может быть достигнуто рассматривая null маркеры как строго большие чем любое другое значение или строго меньше. Предположим, что мы вставляем новую строку $t$. Мы можем найти за время $\mathcal{O}(| S | + \log{}|r|)$ множество $S$ всех строк $t'$ таких, что $t[Х]$ и $t'[Х]$ идентичны:

$$ S = \bigcap_{A \in X}{ \{ t' \in r|t'[A]=t[A] ∨ t'[A]~и~t[A] ~равно~null} \}$$

Затем мы можем проверить, являются ли $t[Y]$ и $t'[Y]$ идентичными для всех $t'$ за линейное время $\mathcal{O}(| S |)$. Обратите внимание, что мы считаем мощность множества $X (| X |)$ малой константой.
Мы также можем эффективно применять $X → Y$ как СРФЗ,
хотя общая стоимость, вероятно, будет больше. Индекс каждого атрибута $A ∈ X$, используя, как и прежде, соглашение, что мы рассматриваем null маркеры как строго большие (или строго меньшие), чем любое другое значение. Имея $t$, сначала мы проверяем, содержит ли $t[Y]$ null маркер (предположим $Y$ — одноэлемнтный, не пересекающийся с X), и в этом случае больше ничего не надо. В противном случае находим все t' такие, что
“t[X] = t'[X] не ложь” вычисляя

$$ S = \bigcap_{A \in X|t[A]~not~null}{ \{ t' \in r|t'[A]=t[A] ∨ t'[A]~и~t[A] ~равно~null} \}$$

с соглашением, что результат равен r, если t[X] содержит только null маркеры. Вычисление пересечения S между несколькими множествами S1, S2, . . . , S|Х| требует только сложность $\mathcal{O}(\sum_{i=1}^{|X|}|S_{i}| + |S|)$ или лучше [16]. Каждое множество $S_i$ может быть сгенерировано за время $\mathcal{O}(|S_{i}| + \log{}|r|)$ при общей сложности $\mathcal{O}(\sum_{i=1}^{|X|}|S_{i}| + |S| + \log{}|r|)$
Затем мы рассматриваем $t'[Y]$ для всех $t' ∈ S$: если существует фактическое значение, приверим, что $t[Y]$ равно $t'[Y]$. То есть, мы возвращаемся

$\bigwedge\limits_{t' \in S} t'[Y]=t[Y] ∨ t'[Y]~и ~равно~null$
Это можно вычислить за время $\mathcal{O}(|S|)$. Подводя итог, использование ЛФЗ или СРФЗ в обновлении или вставке могут быть выполнены за время
• $\mathcal{O}(|S| + \log{}|r|)$ или
• $\mathcal{O}(\sum_{i=1}^{|X|}|S_{i}| + |S| + \log{}|r|)$
Наши заметки реализации требуют только поиска по дереву и установки пересечений, которые хорошо поддерживаются всеми системами баз данных. Этого достаточно, чтобы сделать вывод, что они практичны в вычислительном отношении (Ц4).

## 8. Расширение дизайна логических БД для включения в них null маркеров
Как мы обсуждали в §5, можно применять ФЗ с null маркерами, использующими либо СРФЗ, либо ЛФЗ — без особых усилий со стороны дизайнера БЗ. Однако, мы обычно применяем ФЗ, используя логический дизайн БД. То есть мы разлагаем отношения в нормальные формы и определяем ключи.
Мы хотели бы оставаться как можно ближе к духу SQL. Таким образом, мы спрашиваем, можем ли мы использовать логический дизайн с СРФЗ и ЛФЗ. Это разрешит использование логического дизайна БД для включения null маркеров. К сожалению, хотя и ЛФЗ, и СРФЗ выполняют все наши цели (от Ц1 до Ц4), СРФЗ не совместим с обычным логическим дизайном. Но нам повезло больше с ЛФЗ.
Напомним, что в отношении $r_1$ множество атрибутов $X ⊆ sch(r_1)$ является ключом, если (стандартная) ФЗ $X → sch(r_1)$ выполняется и если $X$ минимально. Более того, в отношении $r_2$ набор атрибутов $Y ⊆ sch(r_2)$ является внешним ключом для $r_1$, если $π_{Y} (r_2) ⊆ π_{X}(r_1)$ для всех расширений $r_1$ и $r_2$.
Соединение $r = r_1$ $\times_{X=Y}$ $r_2$ — это новое отношение, созданное комбинацией всех строк $t_1 ∈ r_1$ и всех строк $t_2 ∈ r_2$ таких, что $t_1[X] = t_2[Y]$ в новой строке $t$, равной $t_1$ на $sch(r_1)$ и равной $t_2$ на $sch(r_2)$ − $Y$. Соединение $r = r_1$ $\times_{X=Y}$ $r_2$ без потерь, когда $πsch(r_1)(r) = r_1$ и $πsch(r_2)(r) = r_2$.
Мы расширяем понятия ключей и объединений в контексте ЛФЗ следующим образом.
<ul>
<li> Мы говорим, что $X ⊆ sch(r)$ является литеральным суперключом для $r$ если $X → Y$ выполняется литерально для любого $Y ⊆ sch(r)$ и литеральный ключ тогда и только тогда, когда это минимальный литеральный суперключ. А литеральный внешний ключ является ограничением соблюдения целостности между двумя отношения: набор атрибутов $X$ в отношении $r_1$ должен соответствовать набору атрибутов $X$ в отношении $r_2$ так, что для каждой строки $t$ в $r_1$ должна быть строка $t'$ в $r_2$ такая, что $t[X]$ и $t'[Х]$ идентичны и такая, что $X$ содержит литеральный ключ в $r_2$. </li>
<li>Как и в SQL, каждое литеральное ограничение внешнего ключа поддерживает соответствующее соединение. Литеральное соединение $r_1$ и $r_2$ на $X$, внешний ключ в $r_1$, отмеченный на $b$, определяется следующим образом: для любых двух наборов $t_1$, $t_2$ из $r_1$, $r_2$ такие, что $t_1[X]$ и $t_2[X]$ совпадают, порождаем набор $t$ такой, что $t[A] = t_1[A]$ для всех $A ∈ sch(r_1)$ и $t[A] = t_2[A]$ для всех $A ∈ sch(r_2) − sch(r_1)$. </li>
С этими определениями мы имеем, что соединения без потерь поддерживается даже с null маркерами. Формально, пусть дано отношение r такое, что $sch(r) = Z \cup W$ и такое, что $Z \cap W → W$ выполняется литерально, $\times$ — соединение без потерь: $r = π_{Z}(r) \times π_{W} (r)$.

Предложение 8.1. (Соединение без потерь) Если $sch(r) = Z ∪ W$ и $Z ∩W → W$ выполняется литерально, то $r = π_{Z}(r) \times π_{W} (r)$.

Доказательство. Для целей литерального соединения null маркер можно рассматривать как любое другое значение. Т. е. имеем набор значений V, расширенный null маркером, который рефлексивен, симметричен и транзитивен. К завершению доказательства, мы должны показать, что $r = π_{Z}(r) \times π_{W} (r)$.
1. Предположим, что $t ∈ r$. Найдется строка $t^{(Z)}$ в $π_{Z}(r)$, такая что $t[Z]$ и $t (Z)$ идентичны. Аналогично, найдется строка $t^{(W)}$ в $π_{W} (r)$ такая, что $t[W]$ и $t ^{(W)}$ идентичны. Имеем, что $t^{(W)} [Z ∩ W] $ идентична $t^{(Z)} [Z ∩ W] $. Таким образом, мы имеем $t \in π_{Z}(r) \times π_{W} (r)$.
2. Предположим, что $t \in π_{Z}(r) \times π_{W} (r)$. Должно быть $t' ∈ r$ такое, что $t'[Z] = t[Z]$. Имеем, что $t[Z∩W]$ и $t'[Z∩W]$ должны быть идентичными, так как $Z∩W ⊂ Z$.
Так как $Z ∩W → W$, то $t[W]$ и $t'[W]$ идентичны. Таким образом, мы имеем, что $t[Z ∪ W]$ и $t'[Z ∪ W]$ идентичны, что показывает, что $t ∈ r$.

Это завершает доказательство.

На самом деле, мы можем показать, что логический дизайн хорошо выглядит над ЛФЗ: пока мы можем нормализовать отношение в обычном смысле, то мы можем нормализовать его в смысле ЛФЗ.

## 9. Выводы и дальнейшие исследования

Мы рассмотрели концепцию ФЗ при наличии null маркеров и указали набор свойств, который, мы считаем, любое определение понятия должно удовлетворять. Мы предложили два новых определения того, что означает, что ФЗ выполняется в этой ситуации, для которой свойства имеют место: наши определения удовлетворяют требованиям аксиомы Армстронга для отношений с null маркерами, разрешают null маркеры для использования на практике (не только с специальными примерами), и в то же время разрешают этим null маркерам постоянно обновляться до фактических значений. Эти ФЗ также могут быть эффективно применены с вычислительной точки зрения, несмотря на null маркеры. Оба определения имеют
немного разные свойства (ЛФЗ обеспечивают соединение без потерь, в дополнение к согласованности БД), но они оба удовлетворяют нашим аксиомам.
Очевидно, что наши требования связаны с нашей целью получить определение, которое можно использовать на практике. Открытый вопрос заключается в том, являются ли свойства, выдвинутые здесь как желаемые, являются единственными — или хотя бы важные, в некотором смысле важные. Мы считаем, что наши свойства удовлетворяют интуиции, что делает концепцию ФЗ применимой в практических ситуациях. Тем не менее, следует изучить дополнительные свойства, чтобы лучше понять желаемое или ожидаемое поведение ФД при наличии null маркеров; возможно, набор альтернативных свойств, каждое из которых развивает концепции ФД, могут быть разработаны для разных сценариев. Согласование какого-то набора или наборов базовых требований предоставило бы исследователям явную меру, по которой можно судить о различных формализациях.

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

## Ссылки
[1] Кодд, Е. Ф. (1986) Недостающая информация (применяемая и неприменяемая) в реляционных базах данных. SIGMOD Rec., 15, 53–53.
[2] Заниоло, C. (1984) Отношения в базах данных с null маркерами. Дж. Комп. Сист. Наук., 28, 142–166.
[3] Атцени, П. и Морфуни, Н. М. (1984) Функциональные зависимости в отношениях с null значениями. Беск. Проц., 18, 233–238.
[4] Хартман, С. и Линк, С. (2012) Проблема зависимостей данных над определениями таблиц SQL: аксиоматические, алгоритмические и логические характеристики.ACM Trans. Сист. баз данных, 37, 13:1–13:40.
[5] Либкин, Л. (1994) Аспекты частичной информации в БД. Тезис кандидатской работы в университете Пеннсильвании.
[6] Бадия, А. и Лемир, Д. (2011) Призыв к оружию: пересмотр дизайна баз данных SIGMOD Rec., 40, 61–69.
[7] ISO 9075-1:2008 (2008) Информационные технологии: языки баз данных - SQL – Часть 1, 3-е издание. ISO, Женева.
[8] Хартманн, С., Лек, У. и Линк, С. (2011) Про семейства ключей Кодда над неполными отношениями. Comput. J., 54, 1166–1180.
[9] Бернштейн, П. (1976) Синтез третьей нормальной формы
отношения из функциональных зависимостей. ACM Trans. Database Syst., 1, 277–298.
[10] Чен, П. П.-С. (1976) Модель сущность-связь — навстречу к универсальному представлению данных. ACM Trans. Database
Syst., 1, 9–36.
[11] Ли, В., Линк, С., и Ферраротти, Ф. (2013) Эффективное
распознавание и визуализация семантических требований совершенными образцами SAL. Концептуальное моделирование, Лекция
Заметки по компьютерным наукам, 8217, с. 227–240. Шпрингер, Берлин Хейдельберг.
[12] Дата, С. Дж. (2009) SQL и реляционная теория: как написать точный код SQL. O’Рилли Медиа, Inc., Себастополь, Калифорния.
[13] Имелинский, Т. и Липский, В. (1984) Неполная информация в реляционных базах данных. J. ACM, 31, 761–791.
[14] Левен, М. и Луазу, Г. (1998) Аксиоматизация функциональных зависимостей в неполных отношениях. Теор. Комп. Наук, 206, 283–300.
[15] Челлас, Б. Ф. (1980) Модулярная логика: введение Cambridge Univ Press, Cambridge.
[16] Динь, Б. и Кёниг, А. Ц. (2011) Быстрое пересечение множеств в памяти. Proc. VLDB Endow., 4, 255–266.