156 Глава) Операции в реляционной модели

! h) Найдите страны, вдадеюшие н обычными кораблями, и крейсерами.

! О Найд1те корабли, сохранившиеся для будущих сражений ; выведенные из строя в одной битве, они участвовали в другой.

Япрожнсние 4.1.4. Покажите дерепья выражений из упражнения 4.1.3.

* Упрожнение 4.1.5. Чем отличается натуральное соединение RtxiS от тета-соедниения RtXf-Sc условием С, согласно которому R.A = S.A для каждого атрибута А. появляющегося в обеих схемах Л и S}

I Зпражнсннс 4.1.6. Оператор на отношениях называется монотонным, если при добавлении кортежа к одному из его аргументов результат содержит все кортежи, которые были до доба&юния и, возможно, некоторые другие кортежн. Какие из описанных в этом разделе операций монотонны? Для каждой операиии объясните, почему она монотонна, или же приведите пример, показывающий, что она не монотонна.

I Упражнение 4.1.7. Пусть отношения й и 5 имеют соответственно пит кортежей. Укаж1гге минимальное и максимальное количество корзежей. получающееся в выражениях:

*а) R<uS

b) RixS

c) ac{R) X S wя некоторого условия С

d) л/. (R) - S для некоторого списка атрибутов L

! Упрожнение 4.1.8. Пачусоединенне отношений R и 5, обозначаемое Лх-это множество кортежей Л, согласующихся по крайней мере с одним кортежем S по всем агрибутам, которые являются общими для R и S. Приведите три эквивалентных ЛIX5 выражения реляиионной алгебры.

!! Упрожнение 4.1.9. Пусть R - отношение со схемой

W Аг, .., А , В,. В .... В )

а S- отношение со схемой (В, В,... BJ; т.е. атрибуты 5 являются подмножеством атрибутов R. Частное отношений /? и 5, обозначенное RS,- это такое множество кортежей i на атрибутах .4,. Л,А (т.е. атрибутах, принадлежащих R. но не при-нал,лежаиц1Х i), что для любого кортежа j из 5 кортеж к, состоящий из компонентов t для Ау.А-,.....А и компонентов s для В Й,. -. входит в л с помощью

операторов, введенных в данном разделе, напишите выражение реляционной алгебры, эквивалентное RS.

4.2 Логика отношений

Существует другой способ выражения запросов, основанный на логике, отличающейся от алгебры. Интересно то, что два подхода (а-лгсбраический и логический) ведут к одному и тому же классу выразимых запросов. Логический язык зшросов, вводикн,1й в этом разделе, называется Daialog (лотка БД ) и состоит нз правил типа еслн .., то 13 одном нз этих правил выражается такая идея: из определенной комбинации кортежей в определенном отношении люжно вывести, что некоторый другой кортеж входит в другое отношение, или же ответить на запрос.

из рис. 4.3. Тогда предикаты Л{1, 2) и Л(2,3) истинны, а для любых других х и у предикат Л(л, у) ложен. □

Аргументами предиката могуг быть переменные и константы. Атом, имеющий в качестве своих аргументов более одной переменной, это булева функция, областью определения которой являются переменные, а значениями TRUE или FALSE.

Пример 4.15. Если R- предикат из примера 4.14, то Л(дс,>) - функция, определяющая для любых X и у, входит ли кортеж (л, у) в отношение Я Для конкретного экземпляра R, показанного в примере 4.14, R{x,y) возврашает значение TRUE, если

1. .\ = I и >= 2

2. x=i м у=4

и FALSE во всех других случаях. При г - 2 атом г) имеет значение TRUE, в противном случае FALSE. □

4.2.2 Арифметические атомы

Существует другой вид атомов, имеющих важное значение в Datalog - арифметические атомы. Они выражают сравнение двух арифметических выражений, например: х<у или г+1г> + 4хг. Атомы, введенные в разделе 4.2.1, будем называть реляционными атаками, чтобы отличать их от арифметических; те и другие являются атомами .

Аргументы арифметических и реляционных атомов - это любые переменные, а их значения - TRUE и FALSE. Арифметические сравнения типа < или > похожи на имена отношений, содержащих все истинные пары. Поэтому можно представить отношение < как отношение, содержащее все кортежи типа (1,2) или (-1,5, 65.4), первые компоненты которых меньше вторых. Однако следует помнить, что отношения БД всегда конечны и обычно время от времени изменяются, а отношения арифметических сравнений типа < бесконечны и неизменны.

4.2.1 Предикаты и атомы

в Datalog отношения прелставлены символами - предикатами. Кажаый предикат имеет фиксированное число аргументов. Предикат, за которым следуют его аргументы, называется атомом. Синтаксис атомов похож на синтаксис вызова

функций в обычных языках программировання. Например: fKxi.Xj.....д ) -это

атом, состоящий из предиката Р с аргуме>ггами х Xj, .... х .

По сути, предикат - это имя функции, возвращающей булево значение. Если R - отношение с л атрибутами, расположенными в фиксированном порядке, то R будет применяться в качестве имени предиката, соответствующего данному отношению. Атом Л{й, Оз.....а ) имеет значение TRUE (истинно), если о oj, а ~

кортеж Л; в противном случае он имеет значение FALSE (ложно).

Пример 4.14. Пусть Л-это отношение

Анонимные переменные

Часто правила Daialog имеют переменные, входящие в гих только один раз. Имена таких переменных ие имеют никакого значения. Только ко1да персмеш1ая входит в правила более одного раза, нужно заботиться о ее имени, чтобы знать, являются ли различные вхождения вхождениями одной и той же переменной. Поэтому принимается общее соглашение о том, что знак в качестве аргумента атома обозначает переменную, которая появляется только в данном месте. Множество вхождений знака относятся к различным переменным и никогда к одной и той же переменной. Например, правило из примера 4.16 можно записать в следующем виде:

LongMovie(t.y) <- Movie(t.y.l, , ,J AND I > 100

Переменные с, s и р, входящие в правило только по одному разу, заменены знаком подчеркивания. Другие переменные нельзя заменять этим знаком, так как каждая из них входит в правило дважды.

Пример 4.16. ПраВ1Ц10 Datalog

LongMovle(l,y) - Movfe{t,y.l,c.s,p) AND I г 100

можно применить для вычислений длинных фильмов , которые длятся не менее 100 мнн. Оно указывает на стандартное отношение Movie, определенное в разделе 3.9 со схемой

Movle(tltle, year, length, InColor, StudioName. pTOduceiC#)

Голова данного правила - атом LotigMovic(i, у), а тело состоит из двух подцелей:

1 В первую подцель входит предикат Movie с шестью аргументами, соответствующими шести атрибутам отношения Movie. Все аргументы имеют раз-jm4Hbie переменные: / для компонента title, у для year, / для length и тл. Эта подцель означает: Пусть (л у, I, с, s. р) - кортеж текущего экземпляра отношения Movie. Более точно: Movie{r, у, I, с, s, р) истинно, если значениями шести переменных являются шесть компонентов одного из кортежей Movie.

2, Вторая подцель, /> 100, истинна, если значение компонента length отношения Movie не менее 100.

4.2-3 Правила и запросы в Datalog

Операции, сходные с операциями реляционной алгсйры, в Daialog описывают-ся с помошью прати, включающих в себя:

1. Реляционный атом, называемый головой. За ним следует

2. Символ KoropbiH часто читается как если . За ним следует

3. Те.ю. состоящее из одного или более реля1Щ0ннык или арифметических атомов, называемых подцелнмч. Подцели соединяются связкой AND, каждой из которых может предшествовать логический оператор NOT.