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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «=Исчисление доменов и его реляционная полнота= ==Исчисление доменов== ===Синтаксис=== <font colo…»)
 
Строка 15: Строка 15:
  
 
Пример:
 
Пример:
−
  S{FirstName = 'Иван', LastName = 'Иванов'}
+
  S<font color=red>{</font>FirstName = <font color=green>'Иван'</font>, LastName = <font color=green>'Иванов'</font><font color=red>}</font>
−
`
 
−
Отношение {
 
−
Атрибут1 = Значение1,
 
−
Атрибут2 = Значение2,
 
−
...
 
−
}
 
−
`
 
  
−
Как мы будем записывать запросы?
+
===Примеры запросов===
  
−
Опишем переменные
 
−
`
 
−
<переменные> where <логическое выражение>
 
−
`
 
  
−
В логические выражения могут входить условие принадлежности, логические связки, кванторы и отрицания.
 
  
−
Реляционная полнота
+
==Реляционная полнота исчисления доменов==
−
--------------------
 
−
Проекция
 
−
A1, ..., An from R where R{A1=A1, ..., An = An}
 
  
−
Фильтр
+
====Проекция $\pi_{A_1, ..., A_n}(R)$====
−
A1, ..., An from R where R{A1=A1, ..., An = An} ∧ θ
+
$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>
  
−
Переименовывание
+
====Фильтр $σ_θ(R)$====
−
expr as A from R where R{A1=A1, ..., An = An}
+
$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=expr}(R_1)$====
−
A1, ..., An where R1{Ai=Ai} ∨ R2{Ai=Ai}
+
expr as A <font color=blue>from</font> $R$ <font color=blue>where</font> $R${$A_1$ = $A_1$, ..., $A_n$ = $A_n$}
  
−
Разность
+
====Объединение $R_1 ∪ R_2$====
−
A1, ..., An where R1{Ai=Ai} ∧ ¬R2{Ai=Ai}
+
$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$====
−
A1, ..., An, B1, ..., Bm where R1{Ai=Ai} ∧ R2{Bj=Bj}
+
$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$====
−
A1, ..., An, B1, ..., Bm, C1, ..., Cl where
+
$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>
−
    R1{Ai=Ai, Bj=Bj} ∧ R2{Ck=Ck, Bj=Bj}
+
 
−
   
+
====Естественное соединение $R_1 ⋈ R_2$====
−
-> Исчисление доменов реляционно полно
+
$A_1$, ..., $A_n$, $B_1$, ..., $B_m$, $C_1$, ..., $C_l$ where $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>

Версия 02:11, 13 декабря 2021

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

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

Синтаксис

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

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

Условие принадлежности

Предикат, значение которого истина тогда, когда в отношении есть кортеж с совпадающими значениями атрибутов.

Пример: 

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

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

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

Проекция $\pi_{A_1, ..., A_n}(R)$

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

Фильтр $σ_θ(R)$

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

Переименовывание $ε_{A=expr}(R_1)$

expr as A from $R$ where $R${$A_1$ = $A_1$, ..., $A_n$ = $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$ 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$ 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$ where $R_1${$A_i$ = $A_i$, $B_j$ = $B_j$} ∧ $R_2${$C_k$ = $C_k$, $B_j$ = $B_j$}
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Исчисление_доменов_и_его_реляционная_полнота&oldid=81315»