Исчисление доменов и его реляционная полнота — различия между версиями
(→Реляционная полнота исчисления доменов) |
м (rollbackEdits.php mass rollback) |
||
| (не показаны 4 промежуточные версии 2 участников) | |||
| Строка 45: | Строка 45: | ||
Выразим базис реляционной алгебры в терминах исчисления доменов: | Выразим базис реляционной алгебры в терминах исчисления доменов: | ||
| − | '''Проекция $\pi_{A_1, ..., A_n}(R)$''' Выбираем только такие наборы значений $A_1$...$A_n$, | + | '''Проекция $\pi_{A_1, ..., A_n}(R)$''' Выбираем только такие наборы значений $A_1$...$A_n$, для которых в исходном отношении есть кортеж, в котором атрибуты $A_1$...$A_n$ принимают значения $A_1$...$A_n$. |
| − | $A_1$, ..., $A_n | + | $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$, которые есть в исходном отношении R и удовлетворяют условию θ | Выбираем только такие наборы значений $A_1$...$A_n$, которые есть в исходном отношении R и удовлетворяют условию θ | ||
| − | $A_1$, ..., $A_n | + | $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$, ... | + | ..., $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$''' | ||
| Строка 65: | Строка 65: | ||
'''Декартово произведение $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$ такие, что ($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$, $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> | <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})
Реляционная полнота исчисления доменов
| Утверждение: |
Исчисление доменов реляционно полно |
|
Выразим базис реляционной алгебры в терминах исчисления доменов: Проекция $\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$}
|
