17228

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

Лекция

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

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

Русский

2013-06-30

191 KB

42 чел.

Лекция №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


 

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

76780. Вспомогательные аппараты мышц 185.15 KB
  Лесгафта на взаимоотношение между работой и строением мышц и костей; мышцы синергисты и антагонисты. Фасция соединительнотканная оболочка в виде футляра вокруг мышцы создающая опору для мышечного брюшка и отграничивающая мускул чем устраняется трение между мышцами. Фасции подразделяются на: поверхностные которые служат мягкой опорой для подкожной клетчатки и отделяют ее от глубже расположенных фасций и мышц; собственные которые окружают отдельные мышцы и мышечные группы и часто называются по области где располагаются: плечевая...
76781. Мышцы и фасции груди 183.63 KB
  Кроме того на груди поверхностные мышцы распределяют на передние боковые и задние соответственно делению грудной стенки на переднюю боковую и заднюю области. Внутренние межреберные мышцы 11 имеют направление волокон перпендикулярное наружным и заполняют промежуток от грудины до угла ребра где переходят в заднюю мембрану. Подреберные мышцы начинаются от углов XXII ребер и перекидываясь через одно два ребра прикрепляются к внутренней поверхности вышележащих ребер.
76782. Мышцы живота 183.58 KB
  Мышцы передней брюшной стенки прямые: правая и левая начинаются узкими длинными пучками от лобковых гребней и лобкового симфиза прикрепляются к наружной поверхности хрящей YYII ребер широкими лентовидными полосами; по своему ходу мышечные пучки прерываются 34 сухожильными поперечными перемычками которые срастаются с влагалищем прямых мышц; влагалище прямой мышцы образуется из апоневрозов косых и поперечных мышц живота так что передняя и задняя стенки его имеют неодинаковое строение: над межостистой линией обе стенки влагалища...
76783. Паховый канал 180.59 KB
  Его четыре стенки образуются: верхняя нижними краями внутренней косой и поперечной мышц живота; нижняя паховой связкой важным клиникоанатомическим ориентиром особенно при отличии паховой грыжи от бедренной и наоборот; передняя апоневрозом наружной косой мышцы; задняя поперечной фасцией рыхло прилежащей к париетальной брюшине. Медиальнонижняя оконечность кольца образована загнутой связкой из латеральной ножки апоневроза и паховой связки; латеральноверхняя округлость состоит из межножковых фиброзных волокон собственной...
76784. Диафрагма. Послойное строение диафрагмы 181.04 KB
  Послойное строение диафрагмы сверху вниз: диафрагмальная плевра: правая и левая между ними по средине диафрагмальный листок перикарда; подплевральная клетчатка и верхняя диафрагмальная фасция часть внутригрудной фасции; мышца диафрагмы и ее сухожильное растяжение; нижняя диафрагмальная фасция часть внутрибрюшной фасции; подбрюшинная клетчатка и диафрагмальная брюшина. Все три части в середине диафрагмы сходятся образуя фиброзное растяжение сухожильный центр который со стороны грудной полости имеет в середине перикардиальное...
76785. Мышцы шеи 193.78 KB
  Поверхностная мышечная группа состоит из подкожной и грудино-ключично-сосцевидной мышц, окруженных поверхностной пластинкой шейной фасции. Средняя группа (мышцы, связанные с подъязычной костью) включает надподъязычные мышцы: челюстно-подъязычную, подбородочно-подъязычную, шилоподъязычную, двубрюшную и подподъязычные мышцы: лопаточно-подъязычную, грудино-подъязычную, грудино-щитовидную, щитоподъязычную.
76786. Мимические мышцы 181.98 KB
  В процессе развития мимические мышцы совершают большие миграции но сохраняют иннервацию от лицевого нерва. Лицевые мышцы сокращаясь формируют выражение лица мимику участвуют в регуляции дыхания артикуляции речи жевании. Мышцы свода черепа Надчерепная мышца состоит из трех частей: лобной затылочной и сухожильного шлема между ними который образует апоневроз затылочнолобной мышцы.
76787. Жевательные мышцы 184.17 KB
  Из промежуточной части с началом от внутренней поверхности скуловой дуги и суставного бугорка височной кости и прикреплением к наружной поверхности ветви нижней челюсти ниже ее вырезки. Из глубокой части начинающейся от внутренней поверхности скуловой дуги и прикрепляющейся к наружной поверхности мыщелкового отростка и сухожилию височной мышцы. Височная мышца заполняет веерообразно височную яму и состоит: из поверхностного слоя начинающегося от верхней височной линии теменной кости височной фасции и прикрепляющегося к наружной...
76788. Мышцы и фасции плечевого пояса 183 KB
  Под мышцей в области большого плечевого бугра располагается поддельтовидная синовиальная сумка. Кровоснабжение из торакоакромиальной пекторальной задней огибающей артерий которые анастомозируют в области плечевого сустава с артериями надлопаточной из подключичной окружающей лопатку из подмышечной образуя артериальную сеть. Дельтовидный мускул иннервируется от подмышечного нерва плечевого сплетения.