Базы Данных, 10 лекция (от 06 октября)
Материал из ESyr's Wiki pages.
Базы данных 06.10.06
Лектор хочет устроить контрольную через 4 пары.
r1 DIVIDE BY r2
r1{A, B} r2{B}
(r1 <REMOVE> B) <AND> <NOT> (((r2 <AND> (r1 <REMOVE> B)) <AND> <NOT> r1) <REMOVE> B)
<AND> <NOT> - MINUS
(r1 <REMOVE> B) MINUS (((r2 <AND> (r1 <REMOVE> B)) MINUS r1) <REMOVE> B)
|
r1 |
A |
B |
r2 |
B |
1. R1 = r1 <REMOVE> B |
A |
2. R2 = R1 <AND> r2 |
A |
B |
3. R3 = R2 MINUS r1 |
A |
B |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
a1 |
b1 |
|
b1 |
|
a1 |
|
a1 |
b1 |
|
a2 |
b2 |
|
|
a1 |
b2 |
|
b2 |
|
a2 |
|
a1 |
b2 |
|
a2 |
b3 |
|
|
a1 |
b3 |
|
b3 |
|
a3 |
|
a1 |
b3 |
|
|
|
|
|
a2 |
b2 |
|
|
|
|
|
a2 |
b1 |
|
|
|
|
|
a3 |
b1 |
|
|
|
|
|
a2 |
b2 |
|
|
|
|
|
a3 |
b2 |
|
|
|
|
|
a2 |
b3 |
|
|
|
|
|
a3 |
b3 |
|
|
|
|
|
a3 |
b1 |
|
|
|
|
|
|
|
|
|
|
|
|
a3 |
b2 |
|
|
|
|
|
|
|
|
|
|
|
|
a3 |
b3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4. R3 PROJECT {A} = R4 |
A |
5 .R1 MINUS R4 |
A |
|
|
|
|
|
|
|
|
|
|
|
a2 |
|
a1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
a3 |
|
|
|
|
На время мы простимся с алгеброй.
Основной механизм манипулирования БД –
Реляционное исчисление
Кортежей
Доменов
РассмотримЖ
СЛУЖАЩИЕ{СЛУ_НОМ, СЛУ_ИМЯ, СЛУ_ЗАРП, ПРО_НОМ}
ПРОЕКТЫ{ПРО_НОМ, ПРОЕКТ_РУК, ПРО_ЗАРП}
Мы хотим узнать имена и номера служащих – начальников отжела со средней заработной платой 11500 рублей.
(СЛУЖАЩИЕ JOIN ПРОЕКТЫ WHERE (СЛУ_НОМ = ПРОЕКТ_РУК AND ПРО_ЗАРП > 11500)) PROJECT (СЛУ_ИМЯ, СЛУ_НОМ)
Это мощные операции, но если отвлечься от этого, то это обычные операции.
Сейчас люди говорят раньше на SQL, чем на русском.
В 60 х языках провели исследование, как лучше писать запросы, на SQL (коммандном языке) или на алгебре. На SQL начали через два дння, в алгебре через 2 недели. Но через месяц на SQL делали в три раза больше ошибок.
Этот же запрос на языке реляционного исчисления кортежей:
Вводятся две кортежные переменные:
RANGE СЛУЖАЩИЙ IS СЛУЖАЩИЙ
RANGE ПРОЕКТ IS ПРОЕКТ
СЛУЖАЩИЙ.СЛУ_ИМЯ, СЛУЖАЩИЙ.СЛУ_НОМ
WHERE EXISTS ПРОЕКТ
(СЛУЖАЩИЙ.СЛУ_НОМ = ПРОЕКТ.ПРОЕКТ_РУК AND ПРОЕКТ.ПРО_ЗАР > 11500)
//Я очень старался всех сотрудников вычистить, но кое-где остались.
На операцию соединения очень сильно намекает СЛУЖАЩИЙ.СЛУ_НОМ = ПРОЕКТ.ПРОЕКТ_РУК.
EXISTS можно выбросить, так как по смыслу квантора существования его можно выбросить, не нарушая смысл выражения.
Почем уквантор существования полезен – пример эквисоединения, который является полусоединением (было ещё на первой лекции)
Реляционная алгебра, при том, что это совершенно фундаментальная вещь, она показывает много хороших св-в, тем не менее, на самой алгебре языков БД практически не было. На памяти лектора в 70х годах был только один язык, QUEL (?). А на исчислении доменов языки существовали и один из них существует до сих пор.
QUEL использовался в университете Кэмбридж (Ingres). - Стоунбрейкер
Alpha - был первый декларативный язык лектора.
Этот язык был сильно математизированный. Про это можно почитать, но, спасибо Кристоферу Дейте, который написал пересказ Коддовских статей, две из которых перевёл лектор.
В SQL есть доно свойство, которое люди хвалт, но оно удручает временами. В нём разрешается писать вложенные подзапросы в разных местах. Но в языке ещё есть кванторы. В этом случае они себя ведут по-дурацки, ибо пишется целый запрос, который вырабатывает да или нет. В QUEL кванторы можно писать без подзапросов.ы
//Педедыв
В основе исчислений, самое дазовое понятие – переменная. Так как мы говорим про исчисление кортежей, то кортежная переменная. Чтобы можно было ими пользоваться, их нужно объявлять (ситаксис QUEL):
RANGE a IS r //a.b
Правильно построенная формула (Well-Formal Formula):
Простое условие – правильно формула, в скобках – простое условие:
СЛУЖАЩИЙ.СЛУ_НОМ = 2934
СЛУЖАЩИЙ.СЛУ_НОМ = ПРОЕКТ.ПРОЕКТ_РУК
Конструкции:
NOT, AND, OR, IF ... THEN
IF a THEN b = NOT a OR b;
Читатель нашёл у меня ошибку, но, естественно, он был не прав.
Из лжи следует всё, что угодно
Иногда формулировка с помощью импликаций выглядит заманчиво, затягивает, она и в sQL есть.
Приоритеты: NOT > AND > OR
если for m – WFF, сопр-простое сравнение
NOT form, comp AND form? Comp OR form, IF comp THEN form – WFF
Есть правильно построенная формула. Мы хотим определить формулу истинности, то есть те выражения, которые приводят её в TRUE. Мы довольно долго думали, и в результате придумали использовать вложенные циклы.
Следующий шаг – прямого аналога в алгебре нет – квантор.
Функция, Аргумент – множество, вырабатывает тру или фолс.
Поддерживается два квантора:
Квантор существования EXISTS
FORALL
EXISTS var(form), FORALL var(form) – WFF
Свободные и связанные переменные
Переменные, которые ни разу не встречаются под знаком квантора, называются свободными.
Связанные переменные – закрытые, только под квантором, влияют на способ вычисления формулы.
Пусть есть формула:
есть СЛУ1 и СЛУ2, определены на отношении СЛУЖАЩИЕ
Формула:
EXISTS СЛУ2(СЛУ1.СЛУ_ЗАРП > СЛУ2.СЛУ_ЗАРП) – все с неминимальной зарплатой.
Циклы:
foreach СЛУ1
foreach СЛУ2
FORALL СЛУ2(СЛУ1.СЛУ_ЗАРП >= СЛУ2.СЛУ_ЗАРП) – все с максимальной зарплатой.
Нет условия на несравнение с самим собой, ибо это не влияет.
Здесь точно внутринний цикл будет крутиться до конца, ибо квантор такой.
В одну формулу может входить несколько подформул, в которые одна и та же связанная переменная может входить в разном качестве.
EXISTS СЛУ2(СЛУ1.ПРО_НОМ = СЛУ2.ПРО_НОМ AND СЛУ1.СЛУ_НОМ != СЛУ2.СЛУ_НОМ) AND FORALL СЛУ2(IF СЛУ1.ПРО_НОМ = СЛУ2.ПРО_НОМ THEN СЛУ1.СЛУ_ЗАРП = СЛУ2.СЛУ_ЗАРП)
Нельзя обойтись одним вхождением, ибо нужны и квантор существования, и квантор всеобщности.
SQL и вложенные запросы:
Кванторы появились в SQL не так давно.
QUEL был лучше, чем SQL. Но SQL его загубил.
Зато в SQL очень давно существуют другие агрегатные функции (возвращают халявное значание, а получают множество) – COUNT, MINIMUM, MAXIMUM, AVERAGE. Для использования их нужно сформировать множество, то есть использовать подзапрос. В SQL мы с тем же самым успехом могли написать
min СЛУ2.СЛУ_ЗАРП
QUEL позволяет обходиться ьез подзапросов, когда они не нужны. Когда доберемся до System R, нам расскажут ещё про вложенные запросы. Языки рел исчисления, в отличие от SQL, позволяют для квантифицуированных запросов обойтись без подзапросов.
Что осталось сделать:
Научились строить формулы, в которых есть свободные переменныею Не хватает конструкции, которая говорит, что мы хотим получить.
</BODY>
