Введение в системы БД (542480), страница 57
Текст из файла (страница 57)
1970 АСМ Б!СР!ВЕТ 'сЧог)свЬор оп Васа Вевспрйоп апб Ассевв. — ЫочешЬег, 1970. См. аннотацию к [6.7]. Бсгпаб А.3. ТЬе Ке1абопа! АрргоасЬ со сйе Мапайешегп об Васа Вавев П Ргос. 1Р1Р Сопйгева — 13цЬ13апа, Уцйов!ач!а. — Ацйцвс, 1971. Мы упоминаем систему МасА1МБ [6.6], [6.7], в основном, ради исторического интереса. Она является наиболее ранним примером системы, поддерживающей парные отношения и алгебраический язык. Интересным также является то, что эта система разрабатывалась параллельно (и, по меньшей мере, частично независимо) с работой Кодла над реляционной моделью.
Однако, в отличие от работы Кодла, система МасА!МБ не получила существенного развития в будущем. Нос!еу М.О. ТЬе Ресег!ее 1Б/1 Бумет П 1ВМ 1)К Бс!еппбс Сел!ге Керогс 13КБС- 00! 8. — МагсЬ, 1972. См. аннотацию к [6.9]. Тобй Б.З.Р. ТЬе Ресег1ее Ке!абопа1 Тевс ЧеЬ!с1е — А Бувсет Очегсйеъч П!ВМ Був. 3. — ! 976. — ! 5, № 4. Ресег!ее Ке1асюпа1 Тем ЧеЬсс1е (РКТЧ) — это экспериментальная система, разработанная в научном центре компании !ВМ 13К, в городе Петерли, Англия. Она была разработана на основе более ранней системы !Ы [6.8], которая, вероятнее всего, являлась первой реализацией идей Кодда. В ней поддерживались и-арные отношения и версия алгебры под названием !БВЬ (!пбоппасюп Бувсеш Вазе 1лпйца8е — базовый язык информационных систем).
Эта версия реляционной алгебры основывалась на предложениях, изложенных в [6.10]. Первоисточником идей, приведенных в этой главе относительно вывода типов отношений, являются алгебра !БВ1. и предложения из [6.10]. Система РКТЧ обладала следующими важными свойствами. ° Поддерживала операторы ЕЕИАИЕ, ЕХТЕИР и БОИИАЕ1ХЕ ° Включала в себя сложные средства для преобразования выражений [глава 17) ° Включала средство отложенного вычисления, что важно как для оптимизации„ так и для поддержки представлений [см.
обсуждение предложения 81ТЕ в данной главе) Глава б. Реляционная алгебра юзз ° Обеспечивала "функцию расширяемости", т.е, возможность расширять систему, добавляя определенные пользователем операторы 6.10. На!! Р.А Ч., Н)гсЬсос)г Р., апб ТогЫ 8.1.Р. Ап А)веЬга оГ Ке1агюпз Гог МасЬ|пе Сошршайоп // Сопб Кесогб оГ!Ье 2пг) АСМ Бушрозшш оп Риис)р!ез оГРгомгаппшпв Ьапвцавез. — Ра1о А!го, СаИ.
— )апцагу, 1975. 6.11. На!! Р.А.Ч. Ке!айопа! А)веЬга, 1.орс апг) Рцпсйопа! Ргорапптппв // Ргос. 1984 АСМ Б! ОМОВ !пц Сопб оп Мапавешегп оХ Овса. — Воз!оп, Маза. — )цпе, 1984. В статье представлена функциональная интерпретация реляционной алгебры, чтобы (как говорится в статье) изложить теоретические основы так называемых "языков четвертого поколения" (4ОЬ) (см, главу 2) и интегрировать функциональные, логические (глава 23) и реляционные языки таким образом, чтобы они могли совместно использоваться в технологиях реализации.
Автор утверждает, что, хотя логическое программирование и базы данных уже на протяжении некоторого времени сближаются друг с другом, во время написания функциональных или аппликативных языков обрашается мало внимания на требования баз данных или технологии реализации. Поэтому статья, главным образом, вносит вклад в сближение межлу ними. 6.12. К!ц8 А. Ес)ц)ча!епсе оГ Ке)айопа) А!веЬга апб Ке)а!юпа) Са1сц1цз Опегу 1.апвпавез Нач)пв Аввгеваге Рцпсйопз 0)АСМ 29.
— )ц)у, 1982. — № 3. В статье определяется множество расширений реляционной алгебры и реляционного исчисления (глава 7), предназначенных для включения поддержки обобшаюших функций, и демонстрируется эквивалентность двух расширенных языков. Ответы к некоторым упражнениям Заиечание. Ответы к упр. 6.13-6.50 не являются единственно возможными. 6.2. Операция соединения 301К уже рассматривалась в разделе 6.4.
Операция пересечения 1КТЕЕЯЕСТ может быть определена одним из двух представленных ниже эквивалентных вариантов. л 1ктевяест в = л мтквя (л мтквя в ) А 1КТЕВЯЕСТ В ж В М1КВЯ (В МХКВБ й ) Эти два равносильных выражения хотя и допустимы, но несколько неудовлетворительны, поскольку А 1КТЕВЯЕСТ В вЂ” симметричное выражение относительно операндов А и В, а остальные два выражения не симметричны. Для сравнения ниже приводится симметричный вариант.
( Л МХКВЯ ( Л МХКВЯ В ) ! 0810К ( В МХКВЯ ( В МХКВЯ й ) ) Замечание. Если дано, что отношения й и В совместимы по типу, то получаем следующее. А 1КТЕВЯЕСТ В и А 3018 В Теперь о делении. Можно записать следуюшее. А 01710881 В РЕВ С = й ( Х ) М1КВБ ( ( А ( Х ) Т1МЕЯ В ( Х ) ) м1квя с ( х, х ) ) ( х ) 234 Часть 11. Реляционная модель 6.3. 6.4.
Здесь Х вЂ” множество атрибутов, общих для отношений А и С, а У вЂ” множество атрибутов, общих лля отношений В и С. Замечание. Определенный таким образом оператор 01Ч10ЕВХ является обобщением оператора деления, рассмотренного ранее в этой главе, но все еще не оператором Вша)! 0~чЫе (6.3] ввиду предположения о том, что отношение А не содержит атрибутов, отличных от атрибутов Х, отношение В не содержит атрибутов, отличных от 1, и отношение С не имеет атрибутов, отличных от атрибутов Х и 1.
Приведенное выше обобщение позволяет записать запрос "Получить номера поставщиков всех деталей" в более простой форме Я 01Ч10ЕВУ Р РЕВ ЯР вместо развернутой формулировки. Я ( ЯЕ ) Р1Ч10ЕВХ Р ( Р$ ) РЕЕ ЯР ( Я$, Р$ ) А 1ЕТЕЕЯЕСТ В (см. ответ к упр. 6.2). Замечание. Поскольку операпия произведения является специальным случаем операции соединения, в роли примитивного оператора вместо Т1ИЕЯ может выступать оператор 101И, тем более что он является более общим. Здесь мы даем только неформальное (очень неформальное) схематическое "доказательство'*. ° Оператор произведения — это единственный оператор, увеличивающий количество атрибутов, а значит, его нельзя имитировать любыми другими операторами. Поэтому произведение — примитивная операция.
° Оператор проекции — это единственный оператор, уменьшающий количество атрибутов, а значит, его нельзя имитировать любыми другими операторами. Поэтому проекция — примитивная операция. ° Оператор объединения — единственный оператор, увеличивающий количество кортежей, кроме оператора произведения, но произведение к тому же увеличивает количество атрибутов. Пусть отношения А и В должны быть объединены. Обратите внимание, что отношения А и В должны быть совместимы по типу и в их объединении должны быть те же атрибуты, что и в них самих, Если мы образуем произведение отношений А и В, а затем используем проекцию, чтобы уменьшить множество атрибутов в произведении до множества атрибутов в отношении А (или В), мы просто снова вернемся к исходному отношению А (или В).
( А Т1ИЕЯ В ) ( <все атрибута> А ) - =А ° (Но только если отношение В не пустое.) Следовательно, произведение не может быть использовано для моделирования операции объединения, а значит, операция объединения примитивна. ° Оператор вычитания не может быть смоделирован через произведение (поскольку операция произведения увеличивает количество кортежей), через объединение (аналогично) или через проекцию (поскольку проекция сокращает количество атрибутов). Также он не может быть смоделирован с помощью выборки, поскольку вычитание реагирует на значения во втором отношении, которого не может быть при выборке (в силу природы условия выборки).
Следовательно, операция вычитания также примитивна. Глава б. Реляционная алгебра гзя ° Оператор выборки является единственной операцией, которая позволяет сравнивать значения атрибутов с определенными литералами (т.е. со значениями, которые не являются частью какого-либо отношения).
Следовательно, операция выборки также примитивна. 6.5. Короткий ответ — нет. Оригинальный оператор Кодда 01ч10ЕВ1 удовлетворяет следующему условию, ( А Т1МЕЯ В ) 01ч10ЕВ1 В = А Однако необходимо принять к сведению следующее. ° Оператор деления Ковда был бинарным, а наш оператор 01ч10ЕВ1 является триадическим; следовательно, он не может удовлетворять подобному свойству.
° В любом случае, даже если, используя оператор Кодда, разделить А на В, а затем найти декартово произведение результата и отношения В,может получиться отношение, совпадающее с А, хотя, вероятнее всего, оно будет некоторым собственным подмножеством й. ( А 01ч'10ЕВТ В ) Т1ИЕЯ В < А Оператор 01Ч10ЕВ1 Колда больше похож на целочисленное деление в обычной арифметике (т.е. он игнорирует остаток).
6.6. Ловушка заключается в том, что в операции Я01М атрибуты 01Т1 исполбзуются так же, как и атрибуты Я)) и Р)) (в силу нашего определения оператора Ю01М). Результат будет подобен следующему. 6.7. Количество возможных проекций равно 2". К ним относятся идентичная проекция (т.е. проекция по всем п атрибутам, которая дает результат, идентичный исходному отношению А) и "нулевая" проекция (т.е. проекция по никаким атрибутам), которая лает в результате ТйВЬЕ РРИ, если исходное отношение А пустое, и ТйВЬЕ РЕЕ в противном случае [5.5]. 6.8. Да, есть такое отношение, а именно — ТАВЬЕ РЕЕ. Отношение ТАВЬЕ РЕЕ (далее для краткости — просто РЕЕ) — аналог числа 1 по отношению к умножению в обычной арифметике, поскольку для всех отношений В имеем следующее. В ТТМЕЯ РЕЕ - =РЕЕ ТХМЕЯ В н В Иначе говоря, РЕŠ— это тождественный элемент для операции Т1МЕЯ (и конечно, для операции Б01М).
6.9. Не существует отношения, ведущего себя относительно операции Т1ИЕЯ аналогично числу нуль относительно операции умножения. Однако поведение отношения ТйВЬЕ РРИ (нли сокращенно — РРМ) несколько сходно с поведением нуля, так как для всех отношений Е имеем следующее. 23б Часть П. Реляционная модель Е Т1МЕЯ ООМ = РОМ Т1МЕЯ Н = <пустое отношение с тем ке заголовком, что и заголовок Е> 6.10. Отношениями, которые совместимы с ОЕЕ и ООМ при объединении, пересечении и вычитании, являются сами отношения РЕЕ и ООМ. В результате имеем следующее. В случае вычитания первый операнд показан слева в таблице, а второй — вверху (для других операторов, конечно, операнды могут меняться местами).
Обратите внимание, как это напоминает таблицы истинности для логических операций ОЕ, АМО, АМР МОТ соответственно. Конечно, такое совпадение не случайно. Рассмотрев затем выборку и проекцию, получим следующее. ° Любая выборка из отношения ОЕЕ дает отношение ОЕЕ, если значение условия выборки равно значению истина, и ООМ, если оно равно значению ложь. ° Любая выборка из отношения ООМ дает отношение ООМ. ° Проекция любого отношения по пустому множеству атрибутов дает отношение ООМ, если исходное отношение пустое, и отношение ОЕЕ в противном случае. В частности, проекция отношения ОЕЕ или отношения ООМ (обязательно по пустому множеству атрибутов) возвращает исходное отношение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
