3.11 Литература к главе 3

Классической сгаты-и Кодлд (Codd) по реляционным моделям является [41. посвяшекиая тсс фчикниональныч зависимостей и основным реляционным понятиям. 3.iecb же рассматривается трезъя нормальная форма, а нормальная форма Бо()са-Код113 описаил Коллом в более поздней статье 5.

Миоюзначиые злвиснмосзн и четперзая нормальная форма были определены Фэджннсм (FagiiO в 7. Однако совершенно самостоятельный подход к reiLie многозначных згишснмостей прослеживается в [С] и 9J.

Армстронг (Anivirroiiy) первым исследован правила выведения функциональных зависимостей в 11]. Рассмотренные в данной книге правила (включая аксиомы Армстронга) и правила выведения многозначных зависимосгей взягы из (2], Техника тестирования функциональной зависимости путем вычнсле1Н1Я замыкания множества атрибутов заимствована нз (3].

Сушествует 1адд алгоритлюв н/или доказательств того, что алгоритм работает, которые НС приведены в этой книге. К ним олюсятся объяснения того, почему действует алгоритм замыкания для выведения функциональных зависимостей, как выводятся многозначные тавпсимости, как онн проецируются на разлагаемые отношения и как провести декомпозицию в 3NF, не утратив возможности проверять функциональные зависимости. Эти и другие вопросы, касаюшиеся зависимостей, анализируются в 18).

1. Armsironp, W. W. Dependency stmciures of database relationships. Proceedings of the 1974 IFIP Congress, pp. 580-583

2. Beeri. C, R. Fagin and J. H. Howard, A complete axiomatizaiion for functional and multivalued dependencies , ACM SIGMOD Intemaitonal Conference on Management of Data, pp. 47-61, 1977.

3. Bcrnsiein. P. A. Synthesizing third normal form relations from functional dependencies . ACM Iransaciions on Database Systems 1:4, pp. 277 398, 1976.

4. Codd. E. F., A relational model for large shared data banks . Comm ACM 136. pp. 377-387. 1970.

5. Codd, E. F., Fiinher normalization of ihe data base relational model, tn Doiol)ase Systems (R. Rusiia. ed). Prentice-Hall, Englewood Cliifs, NJ, 1972.

6. Delobel, C.Normalization and Jiierarchical dependencies in ihe relational data model. ACM Transactions on Database Systems ЗЗ, pp 201-222. 1978.

7. Fagiii, R. Multixalued dependencies and a new normal form for relational databases , ACM Transactions on Database Sy-stems 2:3, pp. 262-278, 1977-

8. Ullnmn. J. D.. Principles of Database and Knowledge-Base Systems. Volume I, Computer Science Press. New York. 1988.

9. гапю1о, С. aiul M. A. MelkanotT. On ific design of relational database scliemata. ACM Tmnsaciions on Database Systems 61. pp 1-47. 1981.

Глава 4

Операции

в реляционной модели

в этой главе мы приступаем к изучению БД с точки зрения пользователя. Обычно главное для пользователя - запросы к БД, т.е. написание программ, отвечающих на вопросы о текущем состоянии БД. В этой главе проблема запросов к БД рассматривается абстрактно: здесь определяются основные операторы запросов.

В то время как ODL применяет методы, которые в принципе позволяют выполнить любую операцию над данными, а E/R-модель не заключает в себе специфического способа манипулирования данными, реляционная модель содержит конкретное множество стандартных онераиин над данными. Поэтому при анализе работы с БД мы сосредоточимся иа реляционной модели и ее операциях, которые можно выразить в алгебре, назь васмой реляционной алгеброй, или в виде логики, обозначенной DailQg. В данной главе рассматриваются обе эти нотации.

В последующих главах мы обратимся к языкам и средствам, которые в настоящее время предлагают пользователю коммерческие системы БД Абстрактные операторы запросов впервые появятся в виде операций языка запросов SQL. о котором речь пойдет в главах 5 - 7, а затем в языке OQL в главе 8.

4.1 Алгебра реляционных операций

приступая к изучению операций на отношениях, нужно ознакомиться со специальной алгеброй - реляционной. Она состоит из простых, но мощных методов консфуирования новых отношений из уже имеющихся Выражения реляционной алгебры начинаются с отношений в качестве операндов Отношения представляются их именами (например, R или Movie) или явно, в виде списка их кортеже!). Затем можно последовательно строить сложные выражения, применяя любые описанные ниже операторы к отношениям или к более простым вырпжениям реляинонной алгебры. Запрос-это выражение реляционной алгебры. Таким образом, реляционная алгебра - первый конкретный пример языка запросов.

Операции реляционной алгебры делятся на четыре распространенных класса.

\. Обычные теоретико-множественные операции: объединение, пересечение и разность, примененные к отношениям.

2. Операции удаления частей отношения: отбор , уда-ляюший некоторые строки (кортежи), и проекция , удаляющая некоторые столбцы.

3. Операции комбинирования кортежеП nej-x отношений, включая декартово произведение (образование пар кортежей двух отношений всеми возможными способами) и множество видов соединения - выборочного образования пар кортежей двух отношений.

4. Операция персимеиоваиия , которая не влияет на кортежи отношения, но изменяет реляционную схему, т.е. имена атрибутов и/ши имя самого отиошения.

Для выполнения всех возлюжных вычислений на отношениях этих операций нелостаточно: пх действие весьма ограничено. Однако они позполяют сделать .многое из того, что необходимо делать с БД и, как будет показано в главе 5, составляют балыиую часгь стандартного реляционного языка запросов SQL. В ра.1лелах 4.6 и 4.7 мы рассмотрим также средства вычисления, которые имеются в i>e;uibHbix языках запросов тина SQL. но при этом не являются частью реляционной алгебры.

4-1Л Теоретико-множественные операции на отношениях

Наиболее распросграненные операции множеств - объединение, пересечение и разность. Для произвольных множеств R и S они определяются следующим образом.

Ли 5, объединение R и S- это множество элементов, входящих или в Л, или в S, или в оба множества. Элемент входит в объединение только один раз, лаже если он входит и в Л, и в 5.

Rr\S, пересечение R н S- это множество элеметов, входящих и в Л, и в 5,

R - S, разность R н 5-это множество элементов, которые аходяг в R, но не входят в S. Заметим, чго R ~ S отличается от 5 - Л; второе выражение обозначает лиюжество элементов, входящих в S. но не входящих в Л

При применении этих операций к отношениям необходимо соблю.гать ряд условий.

L Ли i должны иметь схемы с идентичными множествами атрибутов.

2. Перед вычислением теоретико-множественного объединения, пересечения или разности множеств кортежей столбцы Л и 5 должны быть расположены так, чтобы порядок атрибутов был одинаков в обоих отношениях.

Иногда нужно вычислить объединение, пересечение или разность отношений, имеющих одинаковое число атрибутов с различными именами. В таком случае применяется оператор переименования (см. раадел 4.LS) ют изменения схемы одного или обоих отношений.

пате

address

gender \ birthdate

Carrie Fisher j 123 Maple St.. Hollywood Mark Кэтт i 456 Oak Rd., Brentwood

9/g/gg

8/8/88

Отношение Л

name

address

i gender j birthdate

Carrie Fisher Harrison Ford

i 123 Maple St.. Hollywood . F ; 9/9/99

i 789 Palm Dr., Beverly Hills ! M 7/7/77

Отношение S