является головным отношением, определяемым этим правилом, где атрибутам произвольно присвоены имена Н\ и 111. В обшем случае, если бы кортеж (1,2) входил п раз в Л, а корте.-к (2, 3) входил т раз в 5, кортеж (1.3) входил бы пт раз

R г/. □

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

7 и прштле не должно быть ни слнон отрицательном реляционной подцели. Ясного опредспения смысла произвольных праоил Daialog с отрпиательнымн реаяииомными по:ше.1я.ч11 для мучьтпмножественной .модели ме сушестлует

4.6.7 Применение правил Datalog

к мультимножествам

Методы вычисления выборов, проскинй и объединений .мультимножеств можно применить и к правилам Datalog при условии, что В НИХ нет отрицательны.х реляционных подцелей. Строго говоря, берется соединение отношений, представленных в виде различных подцелей, к результату применяется любой выбор, включенный в арифметические подцели, и результат выбора ироеиируется на голову правила. На каждом из этих шагов применяется алгоритм, подходящий для мультимножеств.

С концептуальной точки зрения проще применить второй подход к оценке правил Datalog {см. раздел 4.2.4). При таком подходе просматривается каждая неотрицательная реляционная подцель и вместо нее подставляются все кортежи отношения для предиката этой подцели. Если выбор кортежей для каждой подцели дает непротиворечивое значение для каждой переменной и все арифметические подцели становятся истиннымн. сразу ясно, какой становится голова правила при данном приписывании значений переменным.

Так как мы имеем .аело с мультимножествами, дубликаты не устраняются из головы npaaima. Более того, поскольку рассматриваются все комбинации кортежей для подцелей, кортеж, входящий п раз в отношение для подцели, рассмафивается п раз как кортеж для этой подцели в конъюнкции с со всеми комбинациями кортежей для других подцелей.

Пример 4,53. Рассмотрим правило

Н(х. Z) R{x, у) AND S(y. z)

Пусть Л и отношения, изображенные на рис. 4.30. Единственное непротиворечивое приписывание корптежей подцелям {т.е. приписывание, при котором значения переменной у нз каждой подцели совпадают) получается, когда первой подцели приписывается кортеж (I, 2) из Л, а второй подцели приписывается кортеж {2, 3) из S. Поскольку {1,2) входит в R дважды, а {2, 3) входит в S один раз, есть два приписывания кортежей, порождающих приписывания переменных х- I, >=2 и г = 3. Кортеж головы правила (л-, г) при каждом из этих приписываний равен {1,3). Значит, в отношении Н головы правила нет никаких кортежей, кроме двух вхождений кортежа (1,3). Огсюда

Пример 4.54. Рассмотрим отношение Н, определяемое двумя правилами

Н(х. у) +- S(x, у) AMD X > 1 Н(х. у) S(x, у) AND у < 5

и отношение S, имеющее значения, показанные на рис. 4.30(b). Согласно первому правилу, все три кортежа из 5 вводятся в И, так как в каждом из этих кортежей первый компонент больше 1. По второму правилу в Н попадает только кортеж (2, 3), так как (4, 5) не удовлетворяет условию у< 5. Поэтому в результирующее отношение Н входят две копии кортежа (2, 3) и две копии кортежа (4, 5). П

4.6.8 Упражнения к разделу 4.6

* Упрожнение 4.6.1. Пусть РС - отношение, изображенное на рис. 4.10(a)-Нужно вычислить проекцию 7tjp rf(PC). Каковы значения этого выражения как множества и как мультимножества? Каковы средние значения кортежей этой проекции, когда отношение считается множеством или мультимножеством?

Упрожнение 4.6.2. Выполните упражнение 4.6.1 для проекции niPC).

Упрожнение 4.6.3. Это упражнение относится к отношениям линкоров из упражнения 4.1 3

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

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

! Упрожнение 4.6.4. Определенные алгебраические законы для отношений, интерпретируемых как множества, верны и для отношений, которые считаются мультимножествами. Объясните, почему каждый из следующих законов действует и для множеств, и для мультимножеств.

*а) Закон ассоциативности объединения; (Ryj S)j Ts Ли (S Т).

b) Закон ассоциативности пересечения: (Лп >5) п 7= Ло (in 7).

c) Закон ассоциативности натурального объединения: (RxS)ixTRx(StxT}

d) Закон коммутативносги объединения: (Ли 5) = (5.J/?).

e) Закон коммутативности пересечения: (Rr\ Sl={Sr\ R).

f) Закон коммутативности натурального объединения: (RxS)s(Stx R).

g) mJRu (R)kl{S), где i- произвольный список атрибутов.

Закон дистрибутивности объединения относительно пересечения: Ru (Sr, T}-{R-j S) n [R:j T).

i) acAND о(Л)-=ос(Л)>ос(/г). где Си О-произвольные условия опюситеаьно кортежей Д.

и Мпрожнснис 4.6.5. Слеяуюмаде алгебраические законы действуют для множеств, но не для мультимножеств. Объясните, почему они верны для множеств, и привс-ди-ге гротивоположные примеры, доказываюшие, что они не верны для мультимножеств.

*а) (Rr,S)- Rn{S- 7).

b) Закон дистрибутивности пересечения относительно объединения: Rr{ST)m(RrxS}yj(Rr 7).

c) OC0R fl(/f) = Oi:(/?)uan(/?), где Си Z) - произвольные условия относительно кортежей R.

4-7 Другие расширения реляционной модели

Существует ряд понятий и операций, которые не являются частью формальной реляиионной модели, но входят в реальные языки запросов. В этом разделе упоминаются операиии, которые изменяют отношения, вычисляют агрегаты типа суммы столбцов отношения и определяют представления , или именованные функции отношений. Каждая из них входит в язык баз данных SQL и будет рассмотрена в главе У Некоторые нз них упоминаются и при анализе языка запросов OQL в главе 8.

4.7-1 Модификации

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

1. Введение кортежей в отношение.

2. Удаление кортежей из отношения.

3. Обновление существующих кортежей путем изменения их компонентов.

4.7.2 Агрегаты

Операции реляционной алгебры воздействуют на определенные кортежи независимо от других кортежей этого же отношения. Часто требуется скомбинировать кортежи единственного отношения и получить агрегированное значение, т.е. функцию от всех кортежей, смешанных каким-нибудь способом. Например, в примере с фильмами может П011адобит1>ся:

подсчитать число раа)П1чных фильмов, упомянутых в отношении lulovie;

составить таблицу, показывающую сумму длин фильмов, выпущенных каждой студией;

найти администратора фильма с наибольшим чистым доходом.

Реальные языки запросов к БД позволяют применять операторы агрегации к столб-Щ1м отношения, подсчитывать и суммировать их, вычислять минимальные и максимальные значения.