17228

РЕЛЯЦИОННОЕ ИСЧИСЛЕНИЕ

Лекция

Информатика, кибернетика и программирование

Лекция №7 РЕЛЯЦИОННОЕ ИСЧИСЛЕНИЕ В выражениях реляционной алгебры всегда явно задается определенный порядок а также подразумевается определенная стратегия вычисления запроса. В реляционном исчислении не существует никакого описания процедуры вычисления за

Русский

2013-06-30

191 KB

35 чел.

Лекция №7

РЕЛЯЦИОННОЕ ИСЧИСЛЕНИЕ

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

Название реляционного исчисления произошло от той части логики, которая называется исчислением предикатов. В контексте баз данных оно существует в двух формах: в форме предложенного Коддом реляционного исчисления кортежей и в форме предложенного Лякруа и Пиротт реляционного исчисления доменов.

В логике первого порядка (или теории исчисления предикатов) под предикатом подразумевается истинностная функция с параметрами. После подстановки значений вместо параметров функция становится выражением, называемым суждением, которое может быть истинным или ложным.

Устно. Например, предложения "Иванов является сотрудником данной организации" и "Иванов имеет более высокую зарплату, чем Сидоров" являются суждениями, поскольку можно определить их истинность или ложность. В первом случае функция "является сотрудником данной организации" имеет один параметр ("Иванов"), а во втором случае функция "имеет более высокую зарплату, чем" имеет два пара метра ("Иванов" и "Сидоров").

Если предикат содержит переменную, например в виде "х является сотрудником организации", то у этой переменной должна быть соответствующая область определения. Таким образом, при подстановке вместо переменной х одних значений суждение может оказаться истинным, а при подстановке других — ложным.

Устно. Например, если областью определения являются все сотрудники некоторой организации, и подставить вместо переменной х значение "Иванов", который является сотрудником организации, то суждение "Иванов является сотрудником данной организации" будет истинным. Если же вместо переменной х подставить имя другого человека, который не является сотрудником данной организации, то суждение станет ложным.

Если Р — предикат, то множество всех значений переменной х, при которых суждение Р становится истинным, можно символически записать следующим образом:

{х | Р(х)}

Предикаты могут соединяться с помощью логических операций  (AND),  (OR) и  (NOT) с образованием составных предикатов.

Реляционное исчисление кортежей

В реляционном исчислении кортежей задача состоит в нахождении таких кортежей, для которых предикат P является истинным. Это исчисление основано на переменных кортежа. Переменными кортежа являются такие переменные, областью определения которых служит указанное отношение. Таковыми являются переменные, для которых допустимыми значениями могут быть только кортежи данного отношения. (Понятие "область определения" в данном случае относится не к используемому диапазону значений, а к домену, в котором определены эти значения.)

Формулы в реляционном исчислении имеют вид {t   (t)}, где t — переменная - кортеж, т.е. переменная, обозначающая кортеж некоторой фиксированной длины, а — формула, построенная из атомов и совокупности операторов, которые определяются ниже.

Атомы формул   могут быть трех типов:

  1.  R(t), где R — имя отношения, а t — переменная-кортеж. Этот атом означает, что t есть кортеж в отношении R.
  2.  t[i]  s[j], где t и s являются переменными - кортежами, а — арифметический оператор сравнения (=, , , и т.д.). Этот атом означает, что i-й компонент t находится в отношении с j-м компонентом s. Например, t [1] < s [2] означает, что первый компонент t меньше, чем второй компонент s.
  3.  [i]  a и  [i], где и [i] имеют тот же смысл, что и в п. 2, а а - константа. Первый из этих атомов означает, что i-й компонент t находится в отношении с константой а. Второй атом имеет аналогичный смысл. Например, [1] = 3 указывает, что значение первого компонента t равно 3.

При определении операций реляционного исчисления введем понятия «свободных» и «связанных» переменных - кортежей. (Эти понятия имеют в точности тот же смысл, что и в исчислении предикатов.)

Неформально вхождение переменной в формулу является «связанным», если этой переменной предшествует квантор «для всех»  - всеобщности или «существует» - существования. В противном случае переменная называется «свободной».

Устно. Понятие свободной переменной аналогично понятию глобальной переменной в языке программирования, т.е. переменной, определенной вне текущей процедуры. Связанная переменная подобна локальной переменной – переменной, которая определяется в данной процедуре.

Формулы, а также свободные и связанные вхождения переменных - кортежей в эти формулы определяются рекурсивно следующим образом:

  1.  Каждый атом есть формула. Все вхождения переменных - кортежей, упомянутые в атоме, являются свободными в этой формуле.
  2.  Если 1, и 2 — формулы, то 1  2, 1  2 и  1 также формулы, утверждающие соответственно, что «1, и 2 обе являются истинными», «1, или 2, либо обе истинны» и «1 не истинна». Экземпляры переменных – кортежей являются свободными или связными в 1  2, 1  2 и  1 точно так же, как они являются свободными или связными в 1 и 2, в зависимости, где они появляются.
  3.  Если - формула, то (t)() - также формула. Вхождения переменной t, свободные в формуле , являются связанными квантором (t) в формуле (t)(). Формула (t)() утверждает, что существует значение t, при подстановке которого вместо всех свободных вхождений t в формулу эта формула становится истинной. Например, (t)(R(t)) означает, что отношение R не пусто, т.е. существует некоторый кортеж t, принадлежащий R.
  4.  Если — формула, то и (t)() — тоже формула. Свободные вхождения t в становятся связанными квантором (t) в (t)(). Другие вхождения переменных в интерпретируются так же, как в п.3. Формула (t)() утверждает, что, какое бы значение подходящей арности не подставлялось вместо свободных вхождений t в , формула станет истинной.
  5.  Формулы могут при необходимости заключаться в скобки. Предполагается следующий порядок старшинства: арифметические операции сравнения, кванторы и и, наконец, , , в перечисленном порядке.
  6.  Ничто другое не является формулой.

Квантор существования используется для указания количества экземпляров, к которым должен быть применен предикат, и используется в формуле, которая должна быть истинной хотя бы для одного экземпляра, например:

{t  R(t)  ( s) (S(s)  (s[ID] = t[ID])  s[FIO] = ‘Иванов)}

Это выражение означает, что в отношении S существует кортеж, который имеет такое же значение атрибута ID, что и значение атрибута ID в текущем кортеже t из отношения R, а атрибут FIO из кортежа s имеет значение ‘Иванов’.

Квантор всеобщности используется в выражениях, которые относятся ко всем экземплярам, например:

{t  (t) (t[CITY]  ‘Харьков’)}

Это выражение означает, что ни в одном кортеже отношения R значение атрибута CITY не равно ‘Харьков’.

В отношении логических операций могут применяться следующие правила эквивалентности:

  1.  (t) ((t))  (t) (((t)))
  2.  (t) ((t))  (t) (((t)))
  3.  (t) (1(t)  (2(t))  (t) ((1(t))  (2(t)))
  4.  (t) (1(t)  (2(t))  (t) ((1(t))  (2(t)))

Исходя из рассмотренных правил, последнюю формулу можно записать следующим образом:

{t  (t) (t[CITY] = ‘Харьков’)}

Редукция операций реляционной алгебры к реляционному исчислению с переменными - кортежами

Теорема. [Дж. Ульман Основы систем баз данных. «Финансы и статистика», 1983.] Если E – выражение реляционной алгебры, то существует эквивалентное ему безопасное выражение в реляционном исчислении с переменными – кортежами.

В данном случае E эквивалентно выражению {t  R (t)}.

Выражение {t   (t)} называют безопасным, если выполняются следующие условия:

  1.  Всякий раз, когда t удовлетворяет , каждый компонент t является элементом dom().
  2.  Для любого подвыражения вида (u) ((u)) каждый компонент u принадлежит dom(), если u удовлетворяет .
  3.  Если для любого подвыражения вида (u) ((u)) каждый компонент u не принадлежит dom(), то u удовлетворяет .

Условия 2 и 3 позволяют установить истинность квантифицированной формулы (u) ((u)) и (u) ((u)), рассматривая только u, составленные из принадлежащих dom() значениям. Например, любая формула (u) (R(u) …) удовлетворяет условию 2, а любая формула (u) (R(u) …) удовлетворяет условию 3. Фактически это подтверждает тождества 1-4.

Безопасность выражений

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

{t  R(t)}

Выражения такого рода называют опасными. Для того чтобы избежать возникновения этой проблемы, необходимо ввести ограничение, согласно которому все значения, присутствующие в полученных результатах, должны принадлежать к области определения исходного выражения Ai; для этого используется обозначение dom(Ai). Областью определения выражения Ai являются все значения, явно присутствующие в Ai .

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

Выразим некоторые операции реляционной алгебры через формулы реляционного исчисления кортежей.

1). Объединение отношений R и S выражается следующим образом:

{t  R(t)  S(t)}

или

{t  ( u) (R(u))  ( v) (S(v)) (t[1] = u[1]  t[1] = v[1])}

Например:

R(u)

S(v)

RS(t)

1

1

1

a

d

a

b

c

b

c

c

d

Это означает: «множество кортежей t, таких, что t принадлежит R или t принадлежит S». Отметим, что объединение имеет смысл, только если R и S обладают одной и той же арностью.

2). Разность R  S может быть представлена следующим выражением:

{t  R(t)   S(t)}

или

{t  ( u) (R(u)  ( v) (S(v)  (t[1]=u[1]  u[1] ≠ v[1])))}

3). Если R и S — отношения арности соответственно r и p, то декартовое произведение R  S в исчислении можно записать в виде:

{t(r+p) (u(r)) (v(p)) (R(u)  S(v)  t[1]=u[1]  t[2]=u[2]  t[r]=

=u[r]  t[r+1]=v[1]  t[r+2]=v[2] ... t[r+p]=v[p])}

Здесь, ti указывает, что t имеет арность i. Приведенное выражение означает, что R  S есть множество кортежей t (рассматриваемых как кортежи длины r+p), таких, что существует кортеж и, принадлежащий отношению R, и кортеж v, принадлежащий отношению S, причем r первых компонентов t образуют и, а следующие p компонентов – v.

4). Проекция i1, i2, …, ik(R) выражается следующим образом:

{t(k) (u) (R(u)  t[1]=u[i1]  t[k]=u[ik])}

5). Селекция F (R) может быть выражена в виде:

{t R(t)  }

или

{t  ( u) (R(u)  )}

где формула есть F, в которой каждый операнд i, обозначающий i-й компонент, заменяется на t[i].

То есть если A1=a1 AND A2=a2 AND Ak=ak(R), то

{t R(t)  (t[A1]=a1  t[Ak]=ak)}

В качестве самостоятельного примера можно представить отношение R арности 2, которое отображает экземпляр R, когда оно имеет два или более кортежа, и пустое отношение, когда R пусто или имеет только один кортеж, формулой исчисления следующим образом:

{t(2) (u) (R(t)  R(u)  (t[1]  u[1]  t[2]  u[2]))}

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

1,4 (2=3 (RS)),

тогда это выражение можно записать в виде безопасного выражения в реляционном исчислении:

  1.  первый шаг: выразим декартово произведение RS:

{t (u) (v) (R(u)  S(v)  t[1] = u[1]  t[2] = u[2]  t[3] = v[1]  t[4] = v[2])}

  1.  второй шаг: для 2=3 (RS) добавим к этой формуле терм

t[2] = t[3]

  1.  третий шаг: определим для проекции новые компоненты w и получим общий вид запроса:

{w (t) (u) (v) (R(u)  S(v)  t[1] = u[1]  t[2] = u[2]  t[3] = v[1]  t[4] = v[2])  t[2] = t[3]  w[1] = t[1]  w[2] = t[4]} 

это выражение можно записать короче, если не использовать t, а выразить все через u и w:

{w (u) (v) (R(u)  S(v)  u[2] = v[1]  w[1] = v[1]  w[2] = v[2]}

Примеры.

Список

Экзамен

Группа

ФИО

№зк

№зк

Предмет

Оценка

  1.  Создать список предметов, которые сдавали студенты.

{(t[Предмет] (t) (Экзамен (t))}

SELECT Предмет

FROM Экзамен

  1.  Создать список оценок по предмету БД и Математика.

{t[Предмет, Оценка] (t) (Экзамен (t)) (t[Предмет] = ‘БД’  t[Предмет] = ‘Математика’)}

SELECT Предмет, Оценка

FROM Экзамен

WHERE Предмет = ‘БД’ OR Предмет = ‘Математика’

  1.  Создать список студентов, которые сдали экзамен по БД.

Этот запрос можно сформулировать по-другому: Для всех студентов, данные о которых нужно привести в списке, в отношении ‘Экзамен’ существуют кортежи, соответствующие этим студентам кортежи, причем значение атрибута ‘Предмет’ в каждом таком кортежи равно ‘БД’.

Эквивалентная формулировка данного запроса в реляционной алгебре будет выглядеть так: Выбрать такие кортежи отношения ‘Список’, в которых значение атрибута ‘Предмет’ равно ‘БД’, и выполнить их соединение с отношением ‘Экзамен’.

{t[Предмет] (t) (Список(t)) (s) (Экзамен(s)) (t[№зк] = s[№зк]) (s[Предмет] = ‘БД’)}

В соответствии с исчислением

a) SELECT Предмет 

FROM Список AS a

WHERE EXISTS 

(SELECT *

FROM Экзамен AS b 

WHERE a.№зк = b.№зк AND Предмет = ‘БД’)

b) SELECT Предмет 

FROM Список AS a

WHERE a.№зк IN

(SELECT b.№зк 

FROM Экзамен AS b 

WHERE Предмет = ‘БД’)

В соответствии с алгеброй

SELECT Предмет 

FROM Список AS a INNER JOIN Экзамен AS b ON a.зк = b.зк 

WHERE Предмет = ‘БД

  1.  Создать список студентов, которые не сдавали ни одного экзамена.

{t[ФИО] (t) (Список(t)) (s) (Экзамен(s)) (t[№зк] = s[№зк])}

a) SELECT ФИО 

FROM Список AS a

WHERE NOT EXISTS 

(SELECT *

FROM Экзамен AS b 

WHERE a.№зк = b.№зк)

b) SELECT ФИО 

FROM Список AS a

WHERE a.№зк NOT IN

(SELECT b.№зк 

FROM Экзамен AS b)

Используя правила эквивалентности логических операций, это выражение можно переписать как:

{t[ФИО] (t) (Список(t)) (s) (( Экзамен(s))   (t[№зк] = s[№зк]))}

SELECT ФИО

from Список AS A

where зк <>ALL (select зк 

from Экзамен AS B

where A.№зк=B.№зк)

Если, например, надо найти тех, кто не сдавал экзамен по нескольким предметам, то необходимо повторить вложенный запрос для каждого предмета, связывая условия поиска оператором AND.

a) SELECT ФИО 

FROM Список AS a

WHERE NOT EXISTS

(SELECT *

FROM Экзамен AS b

WHERE a.№зк = b.№зк AND Предмет = 'БД') AND NOT EXISTS

(SELECT *

FROM Экзамен AS c

WHERE a.№зк = c.№зк AND Предмет = 'Физика')

b) SELECT ФИО 

FROM Список AS a

WHERE a.№зк NOT IN

(SELECT b.№зк 

ROM Экзамен AS b AND Предмет = 'БД') AND NOT IN

(SELECT b.№зк 

ROM Экзамен AS b AND Предмет = 'Физика’)

c) SELECT ФИО

from Список AS A

here зк <>ALL (select зк 

from Экзамен AS B

where A.№зк=B.№зк AND Предмет = 'БД')

зк <>ALL

(select зк 

from Экзамен AS B

where A.№зк=B.№зк AND Предмет = 'Физика')

Использование предиката IN и квантора ALL при реализации операции вычитания можно только в том случае, если операция выполняется по одному компоненту (по одному атрибуту). Если вычитание производится по двум и более компонентам, то необходимо следовать выражению исчисления и, следовательно, в конструкции SQL использовать квантор существования.

Например, если таблица «Список» связана с таблицей «Экзамен» по двум атрибутом ФИО и №зк. Тогда для реализации операции вычитания можно использовать только квантор EXISTS, так как формула исчисления будет иметь вид:

{t[ФИО, №зк] (t) (Список(t)) (s) (Экзамен(s)) (t[№зк] = s[№зк]) (t[ФИО] = s[ФИО])}

и запрос на SQL имеет вид:

SELECT ФИО, №зк

FROM Список AS A

WHERE NOT EXISTS

(SELECT * FROM Экзамен AS B WHERE A.№зк = B.№зк)

 Запрос вида:

SELECT ФИО, №зк

FROM Список AS A

WHERE зк NOT IN

(SELECT A.№зк FROM Экзамен AS B WHERE A.№зк = B.№зк)

AND A.ФИО NOT IN

(SELECT ФИО FROM Экзамен AS C WHERE A.ФИО = C.ФИО)

 работать не будет, например, при данных вида:

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

  1.  Создать список студентов сдавших все экзамены. Здесь для корректной формулировки предположим, что в схеме БД есть таблица ‘Предмет’, содержащая список всех экзаменов, например

Предмет

Название

Преподаватель

Этот запрос можно сформулировать по-другому: Для всех студентов, данные о которых нужно привести в списке, в отношении ‘Экзамен’ существуют кортежи, соответствующие этим студентам, причем эта комбинация (Список - Экзамен) должна существовать для всех кортежей отношения ‘Предмет’.

(t[ФИО] (t) (us) ((Список(t)) (Предмет(u)) (Экзамен(s)) (t[№зк] = s[№зк]) (s[Предмет] = u[Название])))

Эквивалентная формулировка данного запроса в реляционной алгебре нельзя выразить одной “фразой”. Данный запрос реализует операцию деления и может быть выражен следующим образом:

T1 = №зк(Список Предметы)

T2 = №зк, Название(T1 - Экзамен)

T = ФИО(T1 - T2)

SELECTзк, Название

FROM Список, Предметы;

SELECT №зк, Название

FROM список_экзамен AS c

WHERE not exists 

(select * from Экзамен AS d

where c.№зк = d.№зк and c.Название = d.Предмет);

SELECT ФИО

FROM Список AS n

WHERE not exists

(select * from минус AS m where n.№зк = m.№зк);

Сравним данный запрос с определением операции деления.

Результат операции деления R/S является набор кортежей отношения R, определенных на множестве атрибутов C, которое соответствует комбинации всех кортежей отношения S.

Операции представляется следующим образом:

T1  C(R)

T2  C((ST1) – R)

T3  T1T2

Исходные таблицы:

R

S

C

A

B

B

A

a

b

b

a

a

b1

b1

a1

a

b2

b2

a1

b

a1

b1

Результат:

T1

T2

T3

A

A

A

a

a1

a

a1


 

А также другие работы, которые могут Вас заинтересовать

68043. Ранок «Новорічний Колобок» 77.5 KB
  З Новим роком добрі люди! Щастя, сили вам, добра! Хай у Вас все добре буде! Свято починать пора! З Новим роком вас вітаю Зичу свят веселих вам. Щастя, радості бажаю Дітям, гостям і батькам.
68044. ЭКОЛОГИЧЕСКАЯ СКАЗКА «КОЛОБОК» 52 KB
  Вступительное слово Сегодня 3-Б класс приглашает вас на сказку. А о чем она подумайте сами. Не зря говорится: «Сказка ложь да в ней намек, добрым молодцам урок. Занавес раздвигается. Декорации – избушка с окошком. Из трубы дым идет. Вдали лес. Звучит музыка «В гостях у сказки».
68045. Монотипія «Світ комах» 184.5 KB
  Актуалізація опорних знань Діти сьогодні ми з вами здійснимо подорож до дивовижного світу найменших створінь природи світу комах. Яких комах ви знаєте Чим комахи відрізняються від інших істот Чим вони корисні та чим вони шкідливі Як слід ставитись до комах.
68046. Конфликт, конфликтные ситуации, компромисс 50 KB
  Цель: Изучить основные понятия: конфликт конфликтные ситуации компромисс; Ознакомить учащихся и родителей с разными стилями реагирования в конфликтных ситуациях; Учить применять навыки конструктивного решения конфликтов; Развивать в учениках способность к формированию собственных способов...
68048. Регіональний конкурс «Найкращий відгук на сучасну дитячу прозу» 36.5 KB
  Матеріал до підготовки: мікрофон музика книжкові виставки: Книги які знають усе Сучасна дитяча проза формуляри читачів 4 та 5 класів. Щоб дізнаємося які книги подобаються нашим конкурсантам ми заглянемо у їхні формуляри. Запитання для читачів: Яка книга залишила у твоїй пам’яті...
68049. Виховний захід: «Інформація» 173 KB
  Після того як перший учасник закінчив розповідь він займає місце в аудиторії слухачів. Визначте хто яке місце зайняв якщо відомо що Галя зайняла друге місце Наталя хоч і не стала переможцем але в призери попала а Віра програла Ані. Аня Віра Галя Наталя 1 місце 2 місце 3 місце...
68050. Конкурс кмітливих та винахідливих «Мій розпорядок дня» 36 KB
  - Heute haben wir Wiederholungsstunde zum Thema «Unser Tageslauf». - Sagt, an welchem Thema haben wir gearbeitet? - Woruber haben wir zu diesem Thema gesprochen? - An welchem grammatischen Stoff haben wir in dieserZeit gearbeitet (Perfekt)?
68051. Конкурс юних філологів (сценарій виховного заходу для учнів 8 класу) 54.5 KB
  Наша мова найважливіша частина не лишень нашої поведінки а й нашої особистості нашої душі розуму Сьогодні тут зібралися справжні українці шанувальники мови знавці рідного слова. Сьогодні я пропоную вам демонструючи свої знання з мови ще й зібрати з нашого незвичайного фруктового дерева...