С.Д. Кузнецов - Основы баз данных (1121716), страница 17
Текст из файла (страница 17)
В терминах алгебры Кодда проще всего определяются алгебраические черты языка БОЬ, в частности общая семантика оператора якьест. Базисом предложенной Крисом Дейтом и Хью Дарвеном Алгебры А являются операции реляционного отрицания (дополнения), реляционной конъюнкции гили дизьюнкции) и проекции (удаления атрибута). Реляционные аналоги логических операций определяются в терминах отношений на основе обычных теоретико-множественных операций и позволяют выражать напрямую операции пересечения, декартова произведения, естественного соединения, объединения отношений и т. д.
Путем комбинирования базовых операций выражаются операции переименования атрибутов, со- тз Курс Основы баэ данных единения общего вида, взятия разности отношений. Алгебра А позволяет лучше осознать логические основы реляционной модели, хотя, безусловно, является в меньшей степени ориентированной на практическое применение, чем алгебра Кодда*. Даже сами авторы Алгебры А, Дейт и Дарвен, в своем учебном языке Тмгоггаг'Р используют не Алгебру А напрямую, а некоторое ее надмножество, в большей степени напоминающее алгебру Кодла. Базовые операции Алгебры А Материал этой лекции излагается на несколько более формальном уровне, чем в предыдущих лекциях.
Используемые понятия определяются, по существу, так же, как и в лекции 2, но для удобства и обеспечения точности изложения мы повторим определения. Пусть г — отношение, л — имя атрибута отношения г, т — имя соответствующего типа (т. е. типа или домена атрибута д), ч — значение типа т. Тогда: ° заголовком нг отношения г называется множество атрибутов, т.е, упорядоченных пар вида <я, т>. По определению никакие два атрибута в этом множестве не могут содержать одно и то же имя атрибута А; ° кортеж гг, соответствующий заголовку нг, — это множество упордлоченных триплетов вида <д, т, г >, по одному такому триплету для кажлого атрибута в нг; ° тело Вг отношения г — зто множество кортежей сг. Заметим, что (в общем случае) могут существовать такие кортежи гг, которые соответствуют Нг, но не входят в Вг.
Заметим, что заголовок — это множество (упорядоченных пар вида <я, т>), тело — это множество (кортежей сг), и кортеж — это множество (упорядоченных триплетов вида <я, т, ь >). Элемент заголовка — это атрибут (т. е. упорядоченная пара вида <д, т>); элемент тела — это кортеж; элемент кортежа — это упорядоченный триплет вида <д, т, у>. Любое подмножество заголовка — это заголовок, любое подмножество тела — это тело, и любое подмножество кортежа — это кортеж. Определим несколько основных операций (как будет показано далее, некоторые из них избыточны).
Каждое из последующих определений состоит из: формальной спецификации ограничений (если они имеются), применимых к операндам соответствующей операции; формальной спецификации заголовка результата этой операции; формальной спецификации тела этого результата и неформального обсуждения формальных спецификаций. * Нельзя не упомянуть еше и о том, что «алгебра Кодла в действительности не является алгеброй отношений в математическом смысле, поскольку ее операции применимы не ко всем отношениям. В отличие от этого алгебра А — это .настоящая» алгебра, в которой отсутствуют какие-либо ограничения на операнды. 74 Алгебра А Дейта и Дареена Лекция 4 Во всех формальных спецификациях ех! з ге обозначает квантор существования; ехтяге сг означает «существует такой гг, что».
Символ «'-» означает принадлежность одного множества другому; сгбвг означает, что элемент гг принадлежит множеству Вг. Выражение сг)!Вг означает, что элемент гг не принадлежит множеству Вг. Операции т)низ и ил!оп являются традиционными теоретико-множественными операциями взятия разности и объединения множеств. Поскольку некоторые базовые операции Алгебры А имеют названия обычных логических операций, чтобы избежать путаницы, имена реляционных операций берутся в угловые скобки: <нот>, <АНО>, <ОК> и т. д. В исходный базовый набор операций входят операции реляционного дополнения <нот>, удаления атрибута <ккмочк>, переименования атрибута <ккнАМК>, реляционной конъюнкции <АНО> и реляционной дизъюнкции <ОК>.
Операция реляционного дополнения Пусть в обозначает результат операции <нот> г. Тогда: ° нв = нг (заголовок результата совпадает с заголовком операнда); ° Вв = (гв: ехтэгз сг )гг 4 Вг апд гз = гг) ) (втелорезультатавходят все кортежи, соответствующие заголовку и не входшцие в тело операнда). Операция <нот> производит дополнение в заданного отношения г. Заголовком в является заголовок г.
Тело в включает все кортежи, соответствующие этому заголовку и не входящие в тело г. Видимо, следует пояснить, почему реляционный аналог операции логического отрицания называется здесь операцией реляционного дополнения. Во-первых, термин «дополнение» полностью соответствует сути операции <нот>. тело результата операции <нот> г является дополнением вг до полного множества кортежей, соответствующих нг. Во-вторых, это не противоречит прироле булевской операции нот: у булевского типа имеются всего два значения — ггие и)аде, и мот ггие = !а)зе, а пот )а)ве = глге. (Кстати, обратите внимание, что операцию нот в трехзначной логике (см. лекцию !) уже нельзя считать операцией дополнения.) Чтобы привести пример использования операции <нот>, предположим, что в состав домена допустимык номквА Ввокктов, на котором определен атрибут про ном отношения номквл прокктов с рис. 4.! слева, входит всего пять значений )1, 2, 3, 4, 5).
Тогда результат операции <нот> номквл пвокктов будет таким, как показано на рис. 4.1 справа. Операция удаления атрибута Пусть в обозначает результат операции г <ккмОчк> А. Для обеспечения возможности выполнения операции требуется, чтобы существовал 75 Основы баэ данных Рис. 4.1. Результат операции <НОТ> НОМЕРА ПРОЕКТОВ НЕКОтОрЫй тИП (ИЛИ ДОМЕН) ТтаКОй, ЧтО <А, Т> В Нг(т.
Е. В СОСтаВ ЗаГО- ловка отношения г должен входить атрибут А). Тогда: ° Нв = Нг е(поя (<А, т>), т. е. заголовок результата получается из за- головка операнда изъятием атрибута А; ° Вв = (Гв : ех(явя Сг ех(яСя н (Ст Е Вг ап<) и Е Т асс) <А,Т,Р> Н Сг ап<) Св = Сг жлив (<А,Т,Р>))),т.е.в тело результата входят все кортежи операнда, из которых удалено значение атрибута А.
Операция <немоте> производит отношение я, формируемое путем удаления указанного атрибута А из заданного отношения и Операция эквивалентна взятию проекции г на все атрибуты, кроме А. Заголовок в получается теоретико-множественным вычитанием из заголовка г множества из одного элемента (<А, т>). Тело в состоит из таких кортежей, которые соответствуют заголовку я, причем каждый из них является подмножеством некоторого кортежа тела отношения и Примером операции немОче (конечно же, очень похожим на пример использования операции РНОПЕСТ из предыдущей лекции) является СЛУ- жл()(ие немоте НРО нОМ (получить данные о служащих, участвующих в проектах). Результат этой операции над отношением Олужл)((ие, тело которого приведено в верхней части рис. 4.2, показан на рис.
4.2 внизу. Операция переименования Пустьвобозначаетрезультатоперации г <ненлме> (А, в).Дляобеспечения возможности выполнения операции требуется, чтобы существовал некоторый тип т, такой, что <А, т> е нг, и чтобы не существовал такой тип т, что <в, т е нг. (Другими словами, в схеме отношения г должен присутствовать атрибут А и не должен присутствовать атрибут в.) Тогда; ° Нв = (Нг вупця (<А, Т>) ) сп(оп (<В, Т>), т. е. в схеме результата В заменяет А; ° Вв = (Гв: ех(ясв Сг ех(ягя и (Вг 6 Вг апс) и Е Т апс( <А, Т, и> Е Сг апс) Св = (Сг Ыгпля (<А, Т, н>)) оп1оп (<В, Т, и>))), т. е. в кортежах тела результата имя значений атрибута А меняется на В. Алгебра А Дейта и Дареена Лекция 4 Рис.
4.2. Результат операции слУКАЩие еемОче ЛРО ИОН Операция <еенлие> производит отношение а, которое отличается от заданного отношения г только именем одного его атрибута, которое изменяетСя С А На Е. ЗаГОЛОВОК Ы таКОй жс, КаК ЗаГОЛОВОК т-, За ИСКЛЮЧЕНИЕМ ТОГО, ЧтО пара <В, т> заменяет пару <А, т>. Тело ы включает все кортежи тела г, но в каждом из этих кортежей триплет <в, т, г> заменяет триплет <А, т, у>.
По причине очевидности пример использования этой операции мы приводить не будем. Основы баа данных Курс Операция реляционной конъюнкции Пусть в обозначает результат операции г1 <АЫО> г2. Для обеспечения возможности выполнения операции требуется, чтобы если <л, т1>енг1 и <л, т2>еиг2, то т1=т2. (Другими словами, если в двух отношениях-операндах имеются одноименные атрибуты, то они должны быть определены на одном и том же типе (домене).) Тогда: ° нв = нг1 оп(оп нг2, т.
е. заголовок результата получается путем объединения заголовков отношений-операндов, как в операциях тТМЕЕ и гоги из предыдущей лекции; ° Вв = ( Св: ех(ага ГП1 ех(агэ Гг2 ((Гг1СВг1 ацс) Сг2ЕВг2) асс) Св = Г г1 цп(оп гг2) ); обратите внимание нато, что кортеж результата определяется как абвединение картезкей операндов; поэтому: ° если схемы отношений-операндов имеют непустое пересечение, то операция . АМО> работает как естественное соединение; ° если пересечение схем операндов пусто, то <Аып> работает как расширенное декартово произведение; ° если схемы отношений полностью совпадают, то результатом операции является пересечение двух отношений-операндов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
