Исчисление доменов и его реляционная полнота — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Исчисление доменов)
м (rollbackEdits.php mass rollback)
 
(не показано 10 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
==Исчисление доменов==
 
==Исчисление доменов==
В отличие от исчисления кортежей, где областью значения переменных были отношения, в исчислении доменов, значения переменных лежат в заренее заданых доменах (мы будем называть их также типами). Введём синтаксис для указания типов переменных. Также введём предикат, будем называть его ''условием принадлежности'', который для заданного отношения и значений атрибутов проверяет, есть ли совпадающий кортеж в отношении.
+
{{Определение
 +
|definition=
 +
'''Исчисление доменов''' {{---}} вид реляционного исчисления, в котором значения переменных принадлежат заранее определённым ''доменам''.
 +
}}
 +
 
 +
Домен следует понимать как какое-то именованное множество допустимых значений для переменных. На современном языке, это понятие достаточно близко к понятию типа.
 +
 
 +
Введём синтаксис для указания типов переменных. Также введём предикат, будем называть его ''условием принадлежности'', который для заданного отношения и значений атрибутов проверяет, есть ли совпадающий кортеж в отношении.
 +
 
 
===Синтаксис===
 
===Синтаксис===
 
  <font color=red>Переменная</font> :: <font color=red>Тип</font> <font color=green>-- Переменная может принимать значения из какого-то типа. Тип == набор значений
 
  <font color=red>Переменная</font> :: <font color=red>Тип</font> <font color=green>-- Переменная может принимать значения из какого-то типа. Тип == набор значений
Строка 12: Строка 20:
  
 
===Примеры использования условия принадлежности===
 
===Примеры использования условия принадлежности===
Предикат будет истинным, если в отношении S найдётся кортеж <code>(FirstName = 'Иван', LastName = 'Иванов')</code> или, например (при наличии ещё одного атрибута), <code>(FirstName = 'Иван', LastName = 'Иванов', Email = 'ivan@example.com')</code> и ложным, если ни в одном кортеже не совпали все значения атрибутов с перечисленными
+
Следующий предикат будет истинным, если в отношении S найдётся кортеж <code>(FirstName = 'Иван', LastName = 'Иванов')</code> или, например (при наличии ещё одного атрибута), <code>(FirstName = 'Иван', LastName = 'Иванов', Email = 'ivan@example.com')</code> и ложным, если ни в одном кортеже не совпали все значения атрибутов с перечисленными
  
 
  S<font color=red>{</font>FirstName = <font color=green>'Иван'</font>, LastName = <font color=green>'Иванов'</font><font color=red>}</font>
 
  S<font color=red>{</font>FirstName = <font color=green>'Иван'</font>, LastName = <font color=green>'Иванов'</font><font color=red>}</font>
Строка 32: Строка 40:
  
 
==Реляционная полнота исчисления доменов==
 
==Реляционная полнота исчисления доменов==
 +
{{Утверждение
 +
|statement=Исчисление доменов реляционно полно
 +
|proof=
 +
Выразим базис реляционной алгебры в терминах исчисления доменов:
  
====Проекция $\pi_{A_1, ..., A_n}(R)$====
+
'''Проекция $\pi_{A_1, ..., A_n}(R)$''' Выбираем только такие наборы значений $A_1$...$A_n$, для которых в исходном отношении есть кортеж, в котором атрибуты $A_1$...$A_n$ принимают значения $A_1$...$A_n$.
  $A_1$, ..., $A_n$ <font color=blue>from</font> $R$ <font color=blue>where</font> $R$<font color=red>{</font>$A_1$ = $A_1$, ..., $A_n$ = $A_n$<font color=red>}</font>
+
  $A_1$, ..., $A_n$ <font color=blue>where</font> $R$<font color=red>{</font>$A_1$ = $A_1$, ..., $A_n$ = $A_n$<font color=red>}</font>
  
====Фильтр $σ_θ(R)$====
+
'''Фильтр $σ_θ(R)$'''
  $A_1$, ..., $A_n$ <font color=blue>from</font> $R$ <font color=blue>where</font> $R$<font color=red>{</font>$A_1$ = $A_1$, ..., $A_n$ = $A_n$<font color=red>}</font> ∧ $θ$
+
Выбираем только такие наборы значений $A_1$...$A_n$, которые есть в исходном отношении R и удовлетворяют условию θ
 +
  $A_1$, ..., $A_n$ <font color=blue>where</font> $R$<font color=red>{</font>$A_1$ = $A_1$, ..., $A_n$ = $A_n$<font color=red>}</font> ∧ $θ$
  
====Переименовывание $ε_{A=expr}(R_1)$====
+
'''Переименовывание $ε_{A=expr}(R_1)$'''
  expr as A <font color=blue>from</font> $R$ <font color=blue>where</font> $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}
+
Просто используем специальный синтаксис
 +
  ..., $expr$ as $A$, ... <font color=blue>where</font> $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}
  
====Объединение $R_1 ∪ R_2$====
+
'''Объединение $R_1 ∪ R_2$'''
 +
Выбираем только такие наборы значений $A_1$...$A_n$, что хотя бы в одном из отношений есть соответствующий кортеж
 
  $A_1$, ..., $A_n$ <font color=blue>where</font> $R_1$<font color=red>{</font>$A_i$ = $A_i$<font color=red>}</font> ∨ $R_2$<font color=red>{</font>$A_i$ = $A_i$<font color=red>}</font>
 
  $A_1$, ..., $A_n$ <font color=blue>where</font> $R_1$<font color=red>{</font>$A_i$ = $A_i$<font color=red>}</font> ∨ $R_2$<font color=red>{</font>$A_i$ = $A_i$<font color=red>}</font>
  
====Разность $R_1 ∖ R_2$====
+
'''Разность $R_1 ∖ R_2$'''
 +
Выбираем только такие наборы значений $A_1$...$A_n$, что соответствующий кортеж есть в $R_1$, но нет в $R_2$
 
  $A_1$, ..., $A_n$ <font color=blue>where</font> $R_1$<font color=red>{</font>$A_i$ = $A_i$<font color=red>}</font> ∧ $¬R_2$<font color=red>{</font>$A_i$ = $A_i$<font color=red>}</font>
 
  $A_1$, ..., $A_n$ <font color=blue>where</font> $R_1$<font color=red>{</font>$A_i$ = $A_i$<font color=red>}</font> ∧ $¬R_2$<font color=red>{</font>$A_i$ = $A_i$<font color=red>}</font>
  
====Декартово произведение $R_1 × R_2$====
+
'''Декартово произведение $R_1 × R_2$'''
 +
Выбираем наборы значений  $A_1$, ..., $A_n$, $B_1$, ..., $B_m$ такие, что ($A_1$...$A_n$) есть в $R_1$, а ($B_1$...$B_n$) есть в $R_2$
 
  $A_1$, ..., $A_n$, $B_1$, ..., $B_m$ <font color=blue>where</font> $R_1$<font color=red>{</font>$A_i$ = $A_i$<font color=red>}</font> ∧ $R_2$<font color=red>{</font>$B_j$ = $B_j$<font color=red>}</font>
 
  $A_1$, ..., $A_n$, $B_1$, ..., $B_m$ <font color=blue>where</font> $R_1$<font color=red>{</font>$A_i$ = $A_i$<font color=red>}</font> ∧ $R_2$<font color=red>{</font>$B_j$ = $B_j$<font color=red>}</font>
  
====Естественное соединение $R_1 ⋈ R_2$====
+
'''Естественное соединение $R_1 ⋈ R_2$'''
 +
Выбираем такие наборы значений $A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$, что $B_1$, ..., $B_m$ что ($A_1$, ..., $A_n$, $B_1$, ..., $B_m$) входит в $R_1$, а ($B_1$, ..., $B_m$, $C_1$, ..., $C_l$) в $R_2$. Автоматически получаем соединение по $B_1$, ..., $B_m$. Это можно было бы записать иначе - явной проверкой равенства этих атрибутов (тогда придётся использовать ещё m переменных), но проще сделать так.
 
  $A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$ <font color=blue>where</font> $R_1$<font color=red>{</font>$A_i$ = $A_i$, $B_j$ = $B_j$<font color=red>}</font> ∧ $R_2$<font color=red>{</font>$C_k$ = $C_k$, $B_j$ = $B_j$<font color=red>}</font>
 
  $A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$ <font color=blue>where</font> $R_1$<font color=red>{</font>$A_i$ = $A_i$, $B_j$ = $B_j$<font color=red>}</font> ∧ $R_2$<font color=red>{</font>$C_k$ = $C_k$, $B_j$ = $B_j$<font color=red>}</font>
 +
 +
<div></div>
 +
}}

Текущая версия на 19:44, 4 сентября 2022

Исчисление доменов

Определение:
Исчисление доменов — вид реляционного исчисления, в котором значения переменных принадлежат заранее определённым доменам.


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

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

Синтаксис

Переменная :: Тип -- Переменная может принимать значения из какого-то типа. Тип == набор значений

 -- Условие принадлежности отношению
Отношение {
  Атрибут1 = Значение1,
  Атрибут2 = Значение2,
  ...
}

Примеры использования условия принадлежности

Следующий предикат будет истинным, если в отношении S найдётся кортеж (FirstName = 'Иван', LastName = 'Иванов') или, например (при наличии ещё одного атрибута), (FirstName = 'Иван', LastName = 'Иванов', Email = 'ivan@example.com') и ложным, если ни в одном кортеже не совпали все значения атрибутов с перечисленными

S{FirstName = 'Иван', LastName = 'Иванов'}

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

S{FirstName = FirstName, LastName = LastName}

Примеры запросов

Идентификаторы всех студентов

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

SId where S{SId = SId}
Идентификаторы студентов, не сдавших курс с CId=10

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

SId where ¬∃Points (Points ≥ 60 ∧ Points{SId = SId, Points = Points, CId = 10})

Реляционная полнота исчисления доменов

Утверждение:
Исчисление доменов реляционно полно
[math]\triangleright[/math]

Выразим базис реляционной алгебры в терминах исчисления доменов:

Проекция $\pi_{A_1, ..., A_n}(R)$ Выбираем только такие наборы значений $A_1$...$A_n$, для которых в исходном отношении есть кортеж, в котором атрибуты $A_1$...$A_n$ принимают значения $A_1$...$A_n$.

$A_1$, ..., $A_n$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

Фильтр $σ_θ(R)$ Выбираем только такие наборы значений $A_1$...$A_n$, которые есть в исходном отношении R и удовлетворяют условию θ

$A_1$, ..., $A_n$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$} ∧ $θ$

Переименовывание $ε_{A=expr}(R_1)$ Просто используем специальный синтаксис

..., $expr$ as $A$, ... where $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}

Объединение $R_1 ∪ R_2$ Выбираем только такие наборы значений $A_1$...$A_n$, что хотя бы в одном из отношений есть соответствующий кортеж

$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∨ $R_2${$A_i$ = $A_i$}

Разность $R_1 ∖ R_2$ Выбираем только такие наборы значений $A_1$...$A_n$, что соответствующий кортеж есть в $R_1$, но нет в $R_2$

$A_1$, ..., $A_n$ where $R_1${$A_i$ = $A_i$} ∧ $¬R_2${$A_i$ = $A_i$}

Декартово произведение $R_1 × R_2$ Выбираем наборы значений $A_1$, ..., $A_n$, $B_1$, ..., $B_m$ такие, что ($A_1$...$A_n$) есть в $R_1$, а ($B_1$...$B_n$) есть в $R_2$

$A_1$, ..., $A_n$, $B_1$, ..., $B_m$ where $R_1${$A_i$ = $A_i$} ∧ $R_2${$B_j$ = $B_j$}

Естественное соединение $R_1 ⋈ R_2$ Выбираем такие наборы значений $A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$, что $B_1$, ..., $B_m$ что ($A_1$, ..., $A_n$, $B_1$, ..., $B_m$) входит в $R_1$, а ($B_1$, ..., $B_m$, $C_1$, ..., $C_l$) в $R_2$. Автоматически получаем соединение по $B_1$, ..., $B_m$. Это можно было бы записать иначе - явной проверкой равенства этих атрибутов (тогда придётся использовать ещё m переменных), но проще сделать так.

$A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$ where $R_1${$A_i$ = $A_i$, $B_j$ = $B_j$} ∧ $R_2${$C_k$ = $C_k$, $B_j$ = $B_j$}
[math]\triangleleft[/math]