Базы Данных, 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)


<COL WIDTH=10*> <COL WIDTH=10*> <COL WIDTH=10*> <COL WIDTH=10*> <COL WIDTH=10*> <COL WIDTH=66*> <COL WIDTH=10*> <COL WIDTH=48*> <COL WIDTH=10*> <COL WIDTH=10*> <COL WIDTH=45*> <COL WIDTH=10*> <COL WIDTH=10*> <THEAD> </THEAD> <TBODY> </TBODY>

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






На время мы простимся с алгеброй.


Основной механизм манипулирования БД –

Реляционное исчисление

  1. Кортежей

  2. Доменов


РассмотримЖ

СЛУЖАЩИЕ{СЛУ_НОМ, СЛУ_ИМЯ, СЛУ_ЗАРП, ПРО_НОМ}

ПРОЕКТЫ{ПРО_НОМ, ПРОЕКТ_РУК, ПРО_ЗАРП}


Мы хотим узнать имена и номера служащих – начальников отжела со средней заработной платой 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>

Личные инструменты