17228

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

Лекция

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

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

Русский

2013-06-30

191 KB

37 чел.

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


 

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

25015. Принципы и оценка эффективности PR-деятельности 22.35 KB
  Комплексная оценка эффективности 1997 г. Установление целей и задач – оценка подготовки. Оценка коммуникационного продукта – измерение вложений. Оценка промежуточных результатов Реально достигнутые аудитории по качеству и количеству.
25016. Правовое обеспечение связей с общественностью. Правовое регулирование или формальное регулирование 39.19 KB
  Но их интересы постоянно сталкиваются – юристы заинтересованы в нераспространении информации а PRспециалисты наоборот критикуют политику закрытости. Процесс правового регулирования PR включает в себя следующие законодательные акты: В сфере деятельности органов государственной власти Федеральный закон О порядке освещения деятельности органов государственной власти в государственных средствах массовой информации Закон О государственной тайне Указы Президента РФ О государственном флаге Об управлении Президента РФ по связям с...
25017. Этические проблемы паблик рилейшнз 19.51 KB
  Вопервых это касается этики поведения каждого специалиста PR вовторых этики поведения собственной организации представляемой специалистом. Здесь речь идет о непосредственной зависимости между этикой поведения и успехом компании. Работниками сферы паблик рилейшнз разработано и предложено немало инструкций по этике поведения и руководящих кадров организаций и собственно специалистов данной сферы. Необходимой линией поведения при разрешении большинства из перечисленных проблем является стремление сохранить взаимное доверие между...
25018. Кодексы профессионального поведения специалиста по связям с общественностью 23.79 KB
  Международные кодексы: Кодекс профессионального поведения Международной ассоциации по связям с общественностью IPRA; Международный этический Кодекс Паблик Рилейшнз Афинский кодекс; Профессиональная Хартия международного комитета ассоциаций PRконсультантов Римская Хартия; Кодекс профессионального поведения в области PR Лиссабонский кодекс; Международный кодекс по практике маркетинговых и социальных исследований и др. Международный этический Кодекс Паблик Рилейшнз АФИНСКИЙ КОДЕКС Принят в Афинах Генеральной ассамблеей IPRA в мае...
25021. Лоббирование как одна из технологий PR-службы в сфере управления 20.59 KB
  Реклама должна быть добросовестной и достоверной. Недобросовестная реклама и недостоверная реклама не допускаются. Реклама должна быть распознаваемой без применения специальных знаний и без применения технических средств; Реклама не должна побуждать к агрессии насилию возбуждать панику побуждать к опасным действиям способным нанести вред; формировать негативное отношение к лицам не пользующимся рекламируемыми товарами или осуждать таких лиц. Не допускается реклама в которой отсутствует часть существенной информации о рекламируемом...
25022. Возникновение, современное состояние и развитие консалтинга в мире 23.85 KB
  Консалтинг как продукт услуга Консалтинг – производство советов. Консалтинг – это вид интеллектуальных услуг который связан с решением сложных проблем предприятия в сфере управления и организационного развития. Консалтинг как деятельность фирмы Консалтинг – это деятельность фирмы по оказанию консультационных услуг предприятиям организациям физическим лицам по широким вопросам экономики управления и права. Консалтинг как форма предоставления услуги Консалтинг – это профессиональная помощь осуществляемая в форме советов рекомендаций и...
25023. Консалтинг в сфере PR как форма бизнеса 23.68 KB
  Консалтинг в сфере PR как форма бизнеса Консалтинг в сфере связей с общественностью является разновидностью любого консалтинга а маркетинговые стратегии применимые на рынке консалтинговых услуг частично заимствованы из теоретических основ любого маркетинга услуг. На практике это реализуется управлением финансовой эффективностью бизнеса выбором маркетинговой стратегии развития фирмы и стратегии продвижения услуг. Стратегия маркетинга любых консультационных услуг а также стратегия развития консалтинговой фирмы это набор приемов по...