Базы данных. Вводный курс

         

N-декомпозируемые отношения


Начнем с еще одного определения.

В переменной отношения R с атрибутами (возможно, составными) A и B MVD A

B называется тривиальной, если либо A
B, либо A UNION B совпадает с заголовком отношения R.

Тривиальная MVD всегда удовлетворяется. При A

B она вырождается в тривиальную FD. В случае A UNION B = HR требования многозначной зависимости соблюдаются очевидным образом.

Для примера n-декомпозируемого отношения при n > 2 рассмотрим пятый вариант переменной отношения СЛУЖ_ПРО_ЗАДАН, в которой имеется единственно возможный ключ {СЛУ_НОМ, ПРО_НОМ, СЛУ_ЗАДАН} и отсутствуют нетривиальные MVD. Пример значения переменной отношения приведен на .

Как показано на , результат естественного соединения проекций СЛУЖ_ПРО_НОМ и ПРО_НОМ_ЗАДАН почти совпадает с телом исходного отношения СЛУЖ_ПРО_ЗАДАН, но в нем присутствует один лишний кортеж, который исчезнет после выполнения заключительного естественного соединения с проекцией СЛУЖ_ЗАДАНИЕ. Читателям предлагается убедиться, что исходное отношение будет восстановлено при любом порядке естественного соединения трех проекций.



Наследование типов сущности и типов связи


Сущность может быть расщеплена на два или большее число взаимно исключающих подтипов, каждый из которых включает общие атрибуты и/или связи. Эти общие атрибуты и/или связи явно определяются один раз на более высоком уровне. В подтипах могут определяться собственные атрибуты и/или связи. В принципе, подтипизация может продолжаться на более низких уровнях, но опыт использования ER-модели при проектировании баз данных показывает, что в большинстве случаев оказывается достаточно двух-трех уровней.

Если у типа сущности  A имеются подтипы  B1, B2,..., Bn, то: (a) любой экземпляр типа сущности  B1, B2,..., Bn является экземпляром типа сущности  A (включение);(b) если a является экземпляром типа сущности  A, то a является экземпляром некоторого подтипа  сущности  Bi (i = 1, 2, ..., n) (отсутствие собственных экземпляров у супертипа сущности);(c) ни для каких подтипов  Bi и Bj (i, j = 1, 2, ..., n) не существует экземпляра, типом которого одновременно являются типы сущности  Bi и Bj (разъединенность подтипов).

Тип сущности, на основе которого определяются подтипы, называется супертипом. Как мы видели выше, подтипы должны образовывать полное множество, т. е. любой экземпляр  супертипа должен относиться к некоторому подтипу. Иногда для обеспечения такой полноты приходится определять дополнительный подтип  ПРОЧИЕ.

Пример супертипа  ЛЕТАТЕЛЬНЫЙ АППАРАТ и его подтипов  АЭРОПЛАН, ВЕРТОЛЕТ, ПТИЦЕЛЕТ и ПРОЧИЕ показан на . У подтипа  АЭРОПЛАН имеются два собственных подтипа – ПЛАНЕР и МОТОРНЫЙ САМОЛЕТ. Для супертипа сущности  ЛЕТАТЕЛЬНЫЙ АППАРАТ определен атрибут максимальная дальность полета и необязательная связь «многие ко многим» с типом сущности  ПИЛОТ. Эти атрибут и связь наследуется всеми подтипами этого супертипа сущности. У непосредственного подтипа сущности  АЭРОПЛАН определяется один дополнительный атрибут, так что в совокупности у данного типа сущности имеются два атрибута максимальная дальность полета и размах крыльев и одна унаследованная связь с типом сущности  ПИЛОТ.

У подтипа второго уровня МОТОРНЫЙ


У подтипа второго уровня МОТОРНЫЙ САМОЛЕТ  супертипа  АЭРОПЛАН определяется один дополнительный атрибут  мощность мотора и одна дополнительная (обязательная) связь с типом сущности  АЭРОДРОМ. Тем самым, у типа сущности  МОТОРНЫЙ САМОЛЕТ имеются три атрибута: два унаследованных – максимальная дальность полета и размах крыльев и один собственный – мощность мотора, а также две связи: одна унаследованная – с типом сущности ПИЛОТ и одна собственная – с типом сущности  АЭРОДРОМ. И так далее. Понятно, что для типа сущности  ПРОЧИЕ, скорее всего, бессмысленно определять собственные атрибуты и связи, так что свойства этого типа будут совпадать со свойствами его супертипа.



Рис. 10.12.  Супертипы и подтипы сущности

Как же следует понимать диаграмму, представленную на ? Если начинать от супертипа, то диаграмма изображает ЛЕТАТЕЛЬНЫЙ АППАРАТ, который должен быть АЭРОПЛАНОМ, ВЕРТОЛЕТОМ, ПТИЦЕЛЕТОМ или ДРУГИМ ЛЕТАТЕЛЬНЫМ АППАРАТОМ. Если начинать от подтипа (например, сущности  ВЕРТОЛЕТ), то это ВЕРТОЛЕТ, который относится к типу ЛЕТАТЕЛЬНОГО АППАРАТА. Если начинать от подтипа, который является одновременно супертипом, то это АЭРОПЛАН, который относится к типу ЛЕТАТЕЛЬНОГО АППАРАТА и должен быть ПЛАНЕРОМ или МОТОРНЫМ САМОЛЕТОМ.

В механизме наследования ER-модели допускается наличие двух или более разбиений сущности на подтипы. Например, тип сущности  ЧЕЛОВЕК может быть расщеплен на подтипы по профессиональному признаку (ПРОГРАММИСТ, ДОЯРКА и т. д.), а может быть расщеплен и по половому признаку (МУЖЧИНА, ЖЕНЩИНА).


Неформальное введение в реляционную модель данных


Как уже говорилось в начале этой лекции, основные идеи реляционной модели данных были предложены Эдгаром Коддом в 1969 г. . Следует заметить, что, несмотря на общепризнанную значимость этой и последующих работ Кодда, посвященных реляционной модели данных, эти работы писались на идейном уровне, не были (по теперешним меркам) глубоко технически проработанными, во многих важных местах допускали неоднозначное толкование, и поэтому эти работы невозможно было использовать как непосредственное руководство для реализации СУБД, поддерживающей реляционную модель.

За прошедшие десятилетия реляционная модель развивалась в двух направлениях. Первое направление заложил знаменитый экспериментальный проект компании IBM System R (см. лекцию 12). В этом проекте возник язык SQL, изначально основанный на идеях Кодда (который также работал в IBM), но нарушающий некоторые принципиальные предписания реляционной модели. К настоящему времени в действующем стандарте языка SQL, по сути, специфицирована некоторая собственная, законченная модель данных, обзор которой мы приведем в следующем разделе этой лекции, а более подробно обсудим в лекциях 15-23.

Второе направление, начиная с 1990-х гг., возглавляет Кристофер Дейт, к которому позже примкнул Хью Дарвен. Оба этих ученых также работали в компании IBM и до 1990-х гг. внесли большой вклад в развитие языка SQL. Однако в 1990-е гг. Дейт и Дарвен пришли к выводу, что искажения реляционной модели данных, свойственные языку SQL, достигли настолько высокого уровня, что пришло время предложить альтернативу, опирающуюся на неискаженные идеи Эдгара Кодда и обеспечивающую все возможности как SQL, так и объектно-ориентированного подхода к организации баз данных и СУБД (обзор объектно-ориентированной модели данных приводится в следующем разделе).

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

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



Неявные и явные преобразования типа или домена


В языке SQL обеспечивается возможность использования в различных операциях не только значений тех типов, для которых предопределена операция, но и значений типов, неявным или явным образом приводимых к требуемому типу.



Неявные преобразования типов в SQL


В SQL поддерживается совместимость некоторых типов данных за счет неявного преобразования значений одного типа к значениям другого типа данных (например, при необходимости FLOAT неявно приводится к DOUBLE). Опишем наиболее важные правила совместимости типов, принятые в SQL:1999. Начнем с определения приводимости типов. Тип данных A приводим к типу данных B в том и только в том случае, когда в любом месте, где ожидается значение типа B, может быть использовано значение типа A.

Основные правила приводимости типов состоят в следующем. Типы символьных строк. Тип CHARACTER (x) приводим к любому типу CHARACTER (y), если y

x. Типы VARCHAR (x) и CHARACTER (x) приводимы к любому типу VARCHAR (y), если y
x. Типы CHARACTER (x) и VARCHAR (x) приводимы к любому типу CLOB.Типы битовых строк. Тип BIT (x) приводим к любому типу BIT (y), если y
x. Типы BIT VARYING (x) и BIT (x) приводимы к любому типу BIT VARYING (y), если y
x.Типы BLOB. Тип BLOB (x) приводим к любому типу BLOB (y), если y
x.Типы точных чисел. Тип EN (p1, s1) приводим к любому типу EN (p2, s2), у которого s2
s1 и p2 определяется в реализации. Тип EN (p, s) приводим к любому типу приблизительных чисел AN (p1), где p1 определяется в реализации.Типы приблизительных чисел. Тип AN (p1) приводим к любому типу AN (p2), если p2
p1.



Неклассические статьи и другие материалы, доступные в Internet


3.1. С.Д. Кузнецов. Операционная система UNIX,

Свободно доступные материалы курса. Помимо прочего, можно ознакомиться с основными идеями операционной системы Multics и более подробно разобраться с организацией файловой системы ОС UNIX

3.2. http://www.multicians.org/

Официальный сайт любителей ОС Multics. Здесь можно прочитать многие оригинальные статьи, написанные разработчиками системы во время реализации проекта.

3.3. Сергей Кузнецов. Третий манифест Дейта и Дарвена. Открытые системы, N 4, 2000 г.

В этой статье пересказываются, обсуждаются и комментируются основные идеи, изложенные в книге Криса Дейта и Хью Дарвена “The Third Manifesto: Foundation for Future Database Systems”.

3.4. Сергей Кузнецов. Третий манифест Кристофера Дейта и Хью Дарвена: немного формализма.

Это дополненный комментариями перевод двух глав из книги Криса Дейта и Хью Дарвена “The Third Manifesto: Foundation for Future Database Systems”. В частности, в статье содержится описание Алгебры A в авторском изложении.

3.5. Сергей Кузнецов. Основы современных баз данных. Лекция 8. Ingres: общая организация системы, основы языка Quel.

3.6. Сергей Кузнецов. Развитие идей и приложений реляционной СУБД System R.

Это мой обзор 20-летней давности. По-моему, это единственное издание на русском языке, в котором подробно анализируются принципы организации System R.

3.7. Воссоединение SQL в 1995 г.: люди, проекты, политика. Под редакцией Пола МакДжонса, перевод Сергея Кузнецова.

3.8. Сергей Кузнецов. Основы современных баз данных. Лекция 14. Стандартный язык баз данных SQL.

В этой лекции моего старого курса можно найти описание средств определения схемы, предусмотренных в стандарте SQL/89. Иногда бывает полезно сравнить старое и новое.

3.9. Чтобы получить исчерпывающую информацию о стандарте любого языка, нужно читать текст его стандарта. Это всегда непросто, поскольку текст любого стандарта представляет собой сухой технический документ. Это непросто и потому, что официально распространяемые издания стандартов достаточно дорого стоят, и их нужно специально заказывать.
Однако в случае языка SQL дела обстоят несколько более благоприятно. В Internet всегда можно найти тексты проектов следующего стандарта SQL, которые в данное время обсуждаются. В частности, на сайте http://www.wiscorp.com/SQLStandards.html можно найти проект стандарта SQL:200n, практически полностью включающий SQL:1999 и SQL:2003.

3.10. Журнальные публикации К. Дейта (DBPВ, Intelligent Enterprise, сайт Фабиана Паскаля).

В Internet можно найти много публикаций Дейта, хотя все, что имеется в свободном доступе, датируется 90-ми годами. Статьи последних лет доступны на сайте Фабиана Паскаля за умеренную плату.

3.11. Сергей Кузнецов. Дубликаты, неопределенные значения, первичные и возможные ключи и другие экзотические прелести языка SQL.

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

3.12. Tom Johnson. The Fault with Defaults. Database Programming & Design On-Line, vol.11, N 2, February 1998, www.dbpd.com/9802xtra.htm. (Имеется перевод Сергея Кузнецова)

3.12. C.J. Date. The Birth of the Relational Model (Part 3 of 3). Intelligent Enterprise, Vol. 1, No 3, December 1998 (Имеется перевод на русский язык)

3.13. Michael J. Carey, David J. DeWitt, Goetz Graefe, David M. Haight, Joel E. Richardson, Daniel T. Schuh, Eugene J. Shekita, and Scott L. Vandenberg. The EXODUS Extensible DBMS Project: An Overview. Readings in object-oriented database systems. Morgan Kaufmann, 1989, pp. 474 – 499.

3.14. Ronald Fagin, Jurg Nievergelt, Nicholas Pippenger, H. Raymond Strong. Extendible Hashing-A Fast Access Method for Dynamic Files. ACM Transactions on Database Systems, Vol. 4, No. 3, September 1979, pp. 315-344.

3.15. Witold Litwin. Linear Hashing: A New Tool for File and Table Addressing. Proceedings pf the Sixth International Conference on Very Large Data Bases, October 1-3, 1980, pp. 212-223.

3.16. С. Кузнецов, П. Чардин. Семейство алгоритмов ARIES. Открытые системы, N 3, 2004, стр. 66-71. Более подробный вариант статьи опубликован на CITForum.ru

3.17. R. Bayer, E. McCreight. Organization and Maintenance of Large Ordered Indexes. Acta Informatica, Vol. 1, Fasc. 3, 1972, pp. 173-189.


Немедленная и откладываемая проверка ограничений


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

CHECK (DEPT_EMP_NO = (SELECT COUNT(*) FROM EMP WHERE DEPT_NO = EMP.DEPT_NO))

из определения таблицы DEPT. Предположим, например, что в отдел зачисляется новый служащий. Тогда нужно выполнить две операции: (a) вставить новую строку в таблицу EMP и (b) изменить соответствующую строку таблицы DEPT (прибавить единицу к значению столбца DEPT_EMP_NO). Очевидно, что в каком бы порядке ни выполнялись эти операции, сразу после выполнения первой из них ограничение целостности будет нарушено, соответствующее действие будет отвергнуто, и мы никогда не сможем принять на работу нового служащего.

Поскольку ограничения целостности, немедленная проверка которых бессмысленна, являются нужными и полезными, в язык SQL включены средства, позволяющие регулировать время проверки ограничений. Если говорить более точно, в контексте каждой выполняемой транзакции каждое ограничение целостности должно находиться в одном из двух режимов: режиме немедленной проверки (immediate) или режиме отложенной проверки (deferred). Все ограничения целостности, находящиеся в режиме немедленной проверки, проверяются при выполнении в транзакции любой операции, изменяющей состояние базы данных. Если действие операции нарушает какое-либо немедленно проверяемое ограничение целостности, то это действие отвергается. Ограничения целостности, находящиеся в режиме отложенной проверки, проверяются при завершении транзакции (выполнении операции COMMIT). Если действия этой транзакции нарушают какое-либо отложенно проверяемое ограничение целостности, то транзакция откатывается (операция COMMIT трактуется как операция ROLLBACK).


Для этого в качестве заключительной синтаксической конструкции к любому определению ограничения целостности (любого вида) может быть добавлена спецификация INITIALLY в следующей синтаксической форме:

INITIALLY { DEFERRED | IMMEDIATE } [ [ NOT ] DEFERRABLE ]

Эта спецификация указывает, в каком режиме должно находиться данное ограничение целостности в начале выполнения любой транзакции (INITIALLY IMMEDIATE означает, что в начале выполнения транзакции данное ограничение будет находиться в режиме немедленной проверки, а INITIALLY DEFERRED – что в начале любой транзакции ограничение будет находиться в режиме отложенной проверки), а также возможности смены режима этого ограничения при выполнении транзакции (DEFERRABLE означает, что для данного ограничения может быть установлен режим отложенной проверки, а NOT DEFERRABLE – что не может).

Комбинация INITIALLY DEFERRED NOT DEFERRABLE является недопустимой. Если в определении ограничения спецификация начального режима проверки отсутствует, то подразумевается наличие спецификации INITIALLY IMMEDIATE. При наличии явной или неявной спецификации INITIALLY IMMEDIATE и отсутствии явного указания возможности смены режима подразумевается наличие спецификации NOT DEFERRABLE. При наличии спецификации INITIALLY DEFERRED и отсутствии явного указания возможности смены режима подразумевается наличие спецификации DEFERRABLE.

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

SET CONSTRAINTS { constraint_name_commalist | ALL } { DEFERRED | IMMEDIATE }

Если в операторе указывается список имен ограничений целостности, то все они должны быть DEFERRABLE; если хотя бы для одного ограничения из списка это требование не выполняется, то операция SET CONSTRAINTS отвергается. При указании ключевого слова ALL режим устанавливается для всех ограничений, в определении которых явно или неявно было указано DEFERRABLE.Если в качестве желаемого режима проверки ограничений задано DEFERRED, то все указанные ограничения переводятся в режим отложенной проверки. Если в качестве желаемого режима проверки ограничений задано IMMEDIATE, то все указанные ограничения переводятся в режим немедленной проверки. При этом если хотя бы одно из этих ограничений не удовлетворяется, то операция SET CONSTRAINTS отвергается, и все указанные ограничения остаются в предыдущем режиме.

При выполнении операции COMMIT неявно выполняется операция SET CONSTRAINTS ALL IMMEDIATE. Если эта операция отвергается, то COMMIT срабатывает как ROLLBACK.


Нетранзитивные функциональные зависимости и третья нормальная форма


В произведенной декомпозиции переменной отношения СЛУЖАЩИЕ_ПРОЕКТЫ_ЗАДАНИЯ множество FD переменной отношения СЛУЖ_ПРО_ЗАДАН предельно просто – в единственной нетривиальной функциональной зависимости детерминантом является возможный ключ. При использовании этой переменной отношения какие-либо аномалии обновления не возникают. Однако переменная отношения СЛУЖ не является такой же совершенной.



Независимые проекции отношений. Теорема Риссанена


Обратите внимание, что для переменной отношения СЛУЖ {СЛУ_НОМ, СЛУ_УРОВ, СЛУ_ЗАРП}, кроме декомпозиции на отношения СЛУЖ1 {СЛУ_НОМ, СЛУ_УРОВ} и УРОВ {СЛУ_УРОВ, СЛУ_ЗАРП}, возможна и декомпозиция на отношения СЛУЖ1 {СЛУ_НОМ, СЛУ_УРОВ} и СЛУЖ_ЗАРП {СЛУ_НОМ, СЛУ_ЗАРП}. Оба отношения, полученные путем второй декомпозиции, находятся в 3NF, и эта декомпозиция также является декомпозицией без потерь. Тем не менее вторая декомпозиция, в отличие от первой, не устраняет проблемы, связанные с обновлением отношения СЛУЖ. Например, по-прежнему невозможно сохранить данные о разряде, которым не обладает ни один служащий. Посмотрим, с чем это связано.

Отношения СЛУЖ1 и УРОВ могут обновляться независимо (являются независимыми проекциями), и при этом результат их естественного соединения всегда будет таким, как если бы обновлялось исходное отношение СЛУЖ. Это происходит потому, что FD отношения СЛУЖ трансформировались в индивидуальные ограничения первичного ключа отношений СЛУЖ1 и УРОВ. При второй декомпозиции FD СЛУ_УРОВ

СЛУ_ЗАРП трансформируется в ограничение целостности сразу для двух отношений (такого рода ограничения целостности называются ограничениями базы данных, и их поддержка гораздо более накладна с технической точки зрения). Понятно, что в процессе нормализации декомпозиция отношения на независимые проекции является предпочтительной. Необходимые и достаточные условия независимости проекций отношения обеспечивает теорема Риссанена.

Теорема Риссанена

Проекции r1 и r2 отношения r являются независимыми тогда и только тогда, когда: каждая FD в отношении r логически следует из FD в r1 и r2;общие атрибуты r1 и r2 образуют возможный ключ хотя бы для одного из этих отношений.

Мы не будем приводить доказательство этой теоремы, но продемонстрируем ее верность на примере двух показанных выше декомпозиций отношения СЛУЖ. В первой декомпозиции (на проекции СЛУЖ1 и УРОВ) общий атрибут СЛУ_УРОВ является возможным (и первичным) ключом отношения УРОВ, а единственная дополнительная FD отношения СЛУЖ (СЛУ_НОМ

СЛУ_ЗАРП) логически следует из FD СЛУ_НОМ
СЛУ_УРОВ и СЛУ_УРОВ
СЛУ_ЗАРП, выполняемых для отношений СЛУЖ1 и УРОВ соответственно.
Вторая декомпозиция удовлетворяет второму условию теоремы Риссанена (СЛУ_НОМ является первичным ключом в каждом из отношений СЛУЖ1 и СЛУ_ЗАРП), но FD СЛУ_УРОВ
СЛУ_ЗАРП не выводится из FD СЛУ_НОМ
СЛУ_УРОВ и СЛУ_НОМ
СЛУ_ЗАРП.

Атомарным отношением называется отношение, которое невозможно декомпозировать на независимые проекции. Далеко не всегда для неатомарных (не являющихся атомарными) отношений требуется декомпозиция на атомарные проекции. Например, отношение СЛУЖ2 {СЛУ_НОМ, СЛУ_ЗАРП, ПРО_НОМ} с множеством FD {СЛУ_НОМ
СЛУ_ЗАРП, СЛУ_НОМ
ПРО_НОМ} не является атомарным (возможна декомпозиция на независимые проекции СЛУЖ3 {СЛУ_НОМ, СЛУ_ЗАРП} и СЛУЖ4 {СЛУ_НОМ, ПРО_НОМ}). Но эта декомпозиция не улучшает свойства отношения СЛУЖ2 и поэтому не является осмысленной. Другими словами, при выборе способа декомпозиции нужно стремиться к получению независимых проекций, но не обязательно атомарных.

  Напомним из лекции 3, что атомарность

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

  Неключевым атрибутом называется атрибут, не входящий ни в один возможный ключ.

  В определении предполагается, что у отношения имеется только один возможный ключ.

  Очевидно, что FD называется нетранзитивной тогда и только тогда, когда она не является транзитивной.

  В этом определении опять предполагается, что у отношения имеется только один возможный ключ.

  Теоретически возможная третья декомпозиция отношения СЛУЖ на отношения СЛУЖ2 {СЛУ_НОМ, СЛУ_ЗАРП} и УРОВ {СЛУ_УРОВ, СЛУ_ЗАРП} не является декомпозицией без потерь. Чтобы убедиться в этом, рассмотрите случай, когда для двух разных разрядов сотрудников назначен один и тот же размер зарплаты. Покажите также, что для этой декомпозиции не выполняются условия теоремы Хита.

  Т.е. выводится на основе аксиом Армстронга.


Нормальная форма Бойса-Кодда


Причиной отмеченных аномалий является то, что в требованиях 2NF и 3NF не требовалась минимальная функциональная зависимость от первичного ключа атрибутов, являющихся компонентами других возможных ключей. Проблему решает нормальная форма, которую исторически принято называть нормальной формой Бойса-Кодда и которая является уточнением 3NF в случае наличия нескольких перекрывающихся возможных ключей.

Переменная отношения находится в нормальной форме Бойса-Кодда (BCNF) в том и только в том случае, когда любая выполняемая для этой переменной отношения нетривиальная и минимальная FD имеет в качестве детерминанта некоторый возможный ключ данного отношения.

Переменная отношения СЛУЖ_ПРО_ЗАДАН1 может быть приведена к BCNF путем одной из двух декомпозиций: СЛУЖ_НОМ_ИМЯ {СЛУ_НОМ, СЛУ_ИМЯ} и СЛУЖ_НОМ_ПРО_ЗАДАН {СЛУ_НОМ, ПРО_НОМ, СЛУ_ЗАДАН} с множеством FD и значениями, показанными на , и СЛУЖ_НОМ_ИМЯ {СЛУ_НОМ, СЛУ_ИМЯ} и СЛУЖ_ИМЯ_ПРО_ЗАДАН {СЛУ_ИМЯ, ПРО_НОМ, СЛУ_ЗАДАН} (FD и значения результирующих переменных отношений выглядят аналогично).

Очевидно, что каждая из декомпозиций устраняет трудности, связанные с обновлением отношения СЛУЖ_ПРО_ЗАДАН1.



Нормальные формы ER-диаграмм


Как и в случае схем реляционных баз данных, для ER-диаграмм вводится понятие нормальных форм, причем их смысл очень близко соответствует смыслу нормальных форм отношений. Заметим, что определения нормальных форм ER-диаграмм делают более понятным смысл нормализации схем отношений. Мы приведем только очень краткие и неформальные определения трех первых нормальных форм. Конечно, можно было бы ввести дальнейшие нормальные формы ER-диаграмм, аналогичные нормальной форме Бойса-Кодда, 4NF и 5NF, но на практике к такой нормализации обычно не прибегают, а общие идеи после ознакомления с лекцией 9 должны быть понятны и так.



Объектная модель SQL


Объектные расширения SQL:1999 базируются на некоторой объектной модели, хотя эта модель в явном виде в стандарте не специфицируется. Объектная модель SQL не является тождественной объектным моделям какого-либо объектно-ориентированного языка программирования или какой-либо объектно-ориентрованной системы баз данных. Однако при определении объектной модели SQL участники процесса стандартизации тщательно проанализировали ряд других языков и систем с целью выяснения достоинств и недостатков их объектных моделей. По мнению авторов стандарта SQL:1999, выработанная ими объектная модель похожа на объектную модель языка Java, но при этом адаптирована к природе языка SQL как языка СУБД с наличием стабильно хранимых метаданных и данных.

Объектная модель SQL:1999 включает два основных отличительных компонента – структурные, определяемые пользователями типы данных (User Defined Type – UDT) и типизированные таблицы (Typed Table). Первый компонент позволяет определять новые типы данных, которые могут быть гораздо более сложными, чем встроенные типы данных языка SQL. При определении структурного UDT требуется специфицировать не только содержащиеся в нем элементы данных, но и семантику типа данных, т. е. его поведение на основе интерфейса вызовов методов. Второй компонент – типизированные таблицы – позволяет определять таблицы, строки которых являются экземплярами (или значениями) UDT, с которым явно ассоциируется таблица. Во многих отношениях строка типизированной таблицы похожа на объект класса в объектно-ориентированной системе.

В стандарте SQL:1999 определены два пакета объектных свойств – минимальный (PKG006) и полный (PKG007), которым должны удовлетворять SQL-ориентированные ОРСУБД, претендующие на соответствие стандарту. Ниже будут перечислены свойства, включенные в каждый из пакетов, но смысл этих свойств будет понятен только после прочтения остальных разделов.

Пакет PKG006 включает всего пять свойств: свойство S023 («Basic structured types») – возможность определять UDT и их методы с ограниченными возможностями;свойство S041 («Basic reference types») – возможность определять и использовать ссылки на экземпляры UDT, входящие в типизированные таблицы;свойство S051 («Create table of type») – возможность создания типизированных таблиц;свойство S151 («Type predicate») – возможность определения точного типа (в иерархии типов) экземпляра UDT;свойство Т041 («Basic LOB data type support») – возможность определения LOB-типов в смысле SQL (с необязательной поддержкой операций, кроме операций сохранения и полной выборки).


Пакет PKG007 содержит девять дополнительных свойств: свойство S024 («Enhanced structured types») добавляет к свойству S023 ряд развитых возможностей, в число которых входят возможности кодирования методов на языках, отличных от SQL, сравнения экземпляров UDT и передача экземпляров UDT в качестве параметров различных процедур;свойство S043 («Enhanced reference types») расширяет свойство S041 возможностями определения ссылок с областью действия, автоматической проверки законности ссылок и т. д.;свойство S071 («SQL-paths in function and type name resolution») позволяет использовать путевые выражения SQL (SQL-path) в алгоритме разрешения типа;свойство S081 («Subtables») расширяет возможности свойства S051, допуская организацию иерархии таблиц, аналогичной иерархии типов соответствующих UDT;свойство S111 («ONLY in query expressions») обеспечивает возможность выборки только экземпляров указанного типа, без экземпляров любого из его подтипов;свойство S161 («Subtype treatment») позволяет информировать среду SQL о том, что некоторый экземпляр UDT в действительности является экземпляром указанного подтипа;свойство S211 («User-defined cast functions») разрешает определять подпрограммы, преобразующие экземпляры UDT к другим типам;свойство S231 («Structured type locators») способствует доступу к экземплярам UDT из прикладных программ;свойство S023 («Transform functions») позволяет определять подпрограммы, преобразующие значения UDT в значения предопределенных типов данных, и наоборот.


Объектно-ориентированная модель данных


Если не обращать внимания на особенности объектно-ориентированной терминологии (предполагается, что читатели в общих чертах знакомы с ней), то объектно-ориентированная модель данных ODMG, специфицированная в , отличается от других двух моделей, описываемых в этом разделе, прежде всего, в одном принципиальном аспекте. В модели данных SQL и истинной реляционной модели данных база данных представляет собой набор именованных контейнеров данных одного родового типа: таблиц или отношений соответственно. В объектно-ориентированной модели данных база данных – это набор объектов (контейнеров данных) произвольного типа.



Области разумного применения файлов


После краткого экскурса в историю и современное состояние файловых систем обсудим возможные области их применения. Прежде всего, конечно, файлы используются для хранения текстовых данных: документов, текстов программ и т. д. Такие файлы обычно создаются и модифицируются с помощью различных текстовых редакторов. Эти редакторы могут быть очень простыми, такими, как ed в мире UNIX или утилиты редактирования Norton Commander, FAR Manager и других интерактивных сред Windows. Они могут быть сложными и многофункциональными, синтаксически ориентированными, как, например, GNU Emacs. Но обычно структура текстовых файлов очень проста (c точки зрения файловой системы): это либо последовательность записей, содержащих строки текста, либо последовательность байтов, среди которых встречаются специальные символы (например, символы конца строки). Конечно же, сложность логической структуры текстового файла определяется текстовым редактором, но в любом случае файловой системе она не видна.

Файлы, содержащие тексты программ, используются как входные файлы компиляторов (чтобы правильно воспринять текст программы, компилятор должен понимать логическую структуру текстового файла), которые, в свою очередь, формируют файлы, содержащие объектные модули. С точки зрения файловой системы объектные файлы также обладают очень простой структурой – последовательность записей или байтов. Система программирования накладывает на такую структуру более сложную и специфичную для этой системы структуру объектного модуля. Подчеркнем, что логическая структура объектного модуля файловой системе неизвестна; эта структура поддерживается инструментами системы программирования.

Аналогично обстоит дело с файлами, формируемыми редакторами связей (редактор связей должен понимать логическую структуру файлов объектных модулей) и содержащими образы выполняемых программ. Логическая структура таких файлов остается известной только редактору связей и загрузчику – программе операционной системы. Общая схема взаимодействия программных компонентов при построении программы показана на . Мы кратко обозначили способы использования файлов в процессе разработки программ, но можно сказать, что ситуация аналогична и в других случаях: например, при образовании и использовании файлов, содержащих графическую, аудио- и видеоинформацию.

Одним словом, файловые системы обычно обеспечивают хранение слабо структурированной информации, оставляя дальнейшую структуризацию прикладным программам. В перечисленных выше случаях использования файлов это даже хорошо, потому что при разработке любой новой прикладной системы, опираясь на простые, стандартные и сравнительно дешевые средства файловой системы, можно реализовать те структуры хранения, которые наиболее точно соответствуют специфике данной прикладной области.


Рис. 1.3.  Связи между программными компонентами по пониманию логической структуры файлов



Обнаружение тупиковых ситуаций


Основой обнаружения тупиковых ситуаций является построение (или постоянное поддержание) графа ожидания транзакций. Граф ожидания транзакций – это ориентированный двудольный граф, в котором существует два типа вершин – вершины, соответствующие транзакциям (будем изображать их прямоугольниками), и вершины, соответствующие объектам блокировок (будем изображать их окружностями). В этом графе дуги соединяют только вершины-транзакции с вершинами-объектами. Дуга из вершины-транзакции к вершине-объекту существует в том и только в том случае, если для этой транзакции имеется удовлетворенная блокировка данного объекта. Дуга из вершины-объекта к вершине-транзакции существует тогда и только тогда, когда эта транзакция ожидает удовлетворения запроса блокировки данного объекта. Легко показать, что в системе существует тупиковая ситуация в том и только в том случае, когда в графе ожидания транзакций имеется хотя бы один цикл. Простейший пример графа ожидания транзакций с циклом показан на рис. 13.6.

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

Пример применения алгоритма редукции к графу ожидания транзакций показан на рис. 13.7 (в целях упрощения примера предполагается, что все блокировки являются монопольными, т.е. для каждой вершины-объекта имеется не более одной входящей дуги). В этом случае редукция состоит в том, что, прежде всего, из графа ожидания (начальное состояние которого показано на рис. 13.7 (a)) удаляются все дуги, исходящие из вершин-транзакций, в которые не входят дуги из вершин-объектов. (Это основывается на том разумном предположении, что транзакции, не ожидающие удовлетворения запроса блокировок, могут успешно завершиться и освободить блокировки). Кроме того, удаляются дуги, входящие в вершины-транзакции, из которых не исходят, ведущие к вершинам-объектам (транзакции, ожидающие удовлетворения блокировок, но не удерживающие заблокированные объекты, не могут быть причиной тупика). Для тех вершин-объектов, для которых не осталось входящих дуг, но существуют исходящие, ориентация одной из исходящих дуг (выбираемой произвольным образом) изменяется на противоположную (это моделирует удовлетворение запроса блокировки). Состояние графа после выполнения первого шага редукции показано на рис. 13.7 (b). После этого снова повторяются описанные действия (cостояние графа после выполнения второго шага редукции показано на рис. 13.7 (c)), и так до тех пор, пока не прекратится удаление дуг. Если в графе остались дуги, то они обязательно образуют цикл (см. рис. 13.7 (c)).


Рис. 13.7. Применение алгоритма редукции к графу ожидания транзакций

Предположим теперь, что нам удалось найти цикл в графе ожидания транзакций. Что делать теперь?



Обработка нескольких триггеров, связанных с одной предметной таблицей


В SQL:1999 не запрещается определение нескольких триггеров, ассоциированных с одной предметной таблицей, относящихся к одной и той же категории (BEFORE или AFTER) и срабатывающих по одному и тому же событию. Понятно, что при возникновении условия срабатывания всех таких триггеров система должна выбрать порядок, в котором они будут выполняться.

Решение, принятое в SQL, является предельно простым, хотя и несколько странным. При определении каждого триггера фиксируется временная метка выполнения оператора CREATE TRIGGER, и все триггеры, ассоциированные с одной предметной таблицей, относящиеся к одной и той же категории (BEFORE или AFTER) и срабатывающие по одному и тому же событию, упорядочиваются в соответствии со своими временными метками. Тогда при возникновении условия срабатывания всех триггеров одной группы сначала выполняется первый триггер, затем второй и т.д. В стандарте не специфицируется точность временной метки, связываемой с триггером, и если в одной группе обнаруживаются два или более триггеров с неразличимыми временными метками, то порядок их выполнения должен определяться в реализации.

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

И еще одно интересное свойство триггеров в SQL:1999. Как уже говорилось ранее в этом разделе, каждый инициируемый SQL-оператор должен являться атомарным, т. е. если его выполнение завершается неуспешно, то в базе данных не должно остаться никаких следов подобного выполнения. Но в стандарте говорится больше: неуспешное выполнение хотя бы одного триггера из группы с одинаковым условием срабатывания должно приводить к отмене результатов выполнения инициируемых SQL-операторов всех триггеров этой группы, а также к отмене результатов выполнения самого инициирующего SQL-оператора.



Общая характеристика


Хотя понятие реляционной модели данных первым ввел основоположник реляционного подхода Эдгар Кодд, наиболее распространенная трактовка реляционной модели данных, по-видимому, принадлежит известному популяризатору идей Кодда Кристоферу Дейту, который воспроизводит ее (с различными уточнениями) практически во всех своих книгах (см., например, ). Согласно трактовке Дейта, реляционная модель состоит из трех частей, описывающих разные аспекты реляционного подхода: структурной части, манипуляционной части и целостной части.

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

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



Общая характеристика языка OCL


Более точный и лаконичный способ формулировки ограничений обеспечивает язык OCL (Object Constraints Language). Вот общая характеристика этого языка.

Из языка UML в OCL заимствованы, в первую очередь, следующие концепции: класс, атрибут, операция;объект (экземпляр класса);ассоциация; тип данных (включая набор предопределенных типов Boolean, Integer, Real и String);значение (экземпляр типа данных).

Для понимания языка OCL существенны определяемые в UML традиционные для объектных моделей данных различия между объектом некоторого класса и значением некоторого типа: объект обладает уникальным идентификатором и может сравниваться с другими объектами только по значению идентификатора; следствием этого является возможность определения операций над множествами объектов в терминах их идентификаторов;объект может быть ассоциирован через бинарную связь с другими объектами, что позволяет определить в OCL операцию перехода от данного объекта к связанным с ним объектам;в то же время значение является «чистым значением» в том смысле, что: при сравнении двух значений проверяются сами эти значения; кроме того, значения не могут участвовать в связях, поскольку понятие связи определено только для объектов классов.

В дополнение к скалярным типам данных, заимствованным из UML, в OCL предопределены структурные типы, которые являются разновидностями типов коллекций (collection): математическое множество (set), неупорядоченная коллекция, не содержащая одинаковых элементов; мультимножество (bag), неупорядоченная коллекция, которая может содержать повторяющиеся элементы-дубликаты;последовательность (sequence), упорядоченная коллекция, которая может содержать элементы-дубликаты.

В OCL элементами каждого из трех типов коллекций могут быть либо объекты, либо значения.

Язык OCL предназначен, главным образом, для определения ограничений целостности данных, соответствующих модели, которая представлена в терминах диаграммы классов UML. OCL может применяться для определения ограничений, описывающих пред- и постусловия операций классов, и ограничений, представляющих собой инварианты классов. При проектировании реляционных баз данных возможность определения пред- и постусловий операций вряд ли может оказаться существенной. С точки зрения определения ограничений целостности баз данных более важны средства определения инвариантов классов.



Общая интерпретация реляционных операций


Если не вдаваться в некоторые тонкости, которые мы рассмотрим в следующих разделах, то почти для всех операций предложенного выше набора имеется очевидная и простая интерпретация. При выполнении операции объединения (UNION) двух отношений с одинаковыми заголовками производится отношение, включающее все кортежи, которые входят хотя бы в одно из отношений-операндов.Операция пересечения (INTERSECT) двух отношений с одинаковыми заголовками производит отношение, включающее все кортежи, которые входят в оба отношения-операнда.Отношение, являющееся разностью (MINUS) двух отношений с одинаковыми заголовками, включает все кортежи, входящие в отношение-первый операнд, такие, что ни один из них не входит в отношение, которое является вторым операндом.При выполнении декартова произведения (TIMES) двух отношений, пересечение заголовков которых пусто, производится отношение, кортежи которого производятся путем объединения кортежей первого и второго операндов.Результатом ограничения (WHERE) отношения по некоторому условию является отношение, включающее кортежи отношения-операнда, удовлетворяющее этому условию.При выполнении проекции (PROJECT) отношения на заданное подмножество множества его атрибутов производится отношение, кортежи которого являются соответствующими подмножествами кортежей отношения-операнда.При соединении (JOIN) двух отношений по некоторому условию образуется результирующее отношение, кортежи которого производятся путем объединения кортежей первого и второго отношений и удовлетворяют этому условию.У операции реляционного деления (DIVIDE BY) два операнда – бинарное и унарное отношения. Результирующее отношение состоит из унарных кортежей, включающих значения первого атрибута кортежей первого операнда таких, что множество значений второго атрибута (при фиксированном значении первого атрибута) включает множество значений второго операнда.Операция переименования (RENAME) производит отношение, тело которого совпадает с телом операнда, но имена атрибутов изменены.Операция присваивания (:=) позволяет сохранить результат вычисления реляционного выражения в существующем отношении БД.


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

RENAME
WHERE = PROJECT
TIMES = JOIN = INTERSECT = DIVIDE BY
UNION = MINUS

В другой форме приоритеты операций показаны на . Вычисление выражения производится слева направо с учетом приоритетов операций и скобок.



Рис. 4.1.  Таблица приоритетов операций традиционной реляционной алгебры


Общая структура оператора выборки в языке SQL


Для выборки данных в прямом SQL используется оператор SELECT, возвращающий набор из одной или нескольких строк одинаковой структуры и задаваемый в следующем синтаксисе:

SELECT [ ALL | DISTINCT ] select_item_commalist FROM table_reference_commalist [ WHERE conditional_expression ] [ GROUP BY column_name_commalist ] [ HAVING conditional_expression ] [ ORDER BY order_item_commalist ]



Общее понятие транзакции и основные характеристики транзакций


Более точно, в современных СУБД поддерживается понятие транзакции, характеризуемое аббревиатурой ACID (Atomicy, Consistency, Isolation и Durability). В соответствии с этим понятием под транзакцией разумеется последовательность операций над базой данных, обладающая следующими свойствами.

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

Согласованность (Consistency).

В классическом смысле это свойство означает, что транзакция может быть успешно завершена с фиксацией

результатов своих операций только в том случае, когда действия операций не нарушают целостность

базы данных, т.е. удовлетворяют набору ограничений целостности, определенных для этой базы данных. Это свойство расширяется тем, что во время выполнения транзакции разрешается устанавливать точки согласованности и явным образом проверять ограничения целостности. (С точки зрения автора, в контексте баз данных термины согласованность

и целостность

эквивалентны. Единственным критерием согласованности данных является их удовлетворение ограничениям целостности, т.е. база данных находится в согласованном состоянии тогда и только тогда, когда она находится в целостном состоянии.)

Изоляция (Isolation).

Требуется, чтобы две одновременно (параллельно или квазипараллельно) выполняемые транзакции никоим образом не действовали одна на другую. Другими словами, результаты выполнения операций транзакции T1

не должны быть видны никакой другой транзакции T2

до тех пор, пока транзакция T1

не завершится успешным образом.

Долговечность (Durability).

После успешного завершения транзакции все изменения, которые были внесены в состояние базы данных операциями этой транзакции, должны гарантированно сохраняться, даже в случае сбоев аппаратуры или программного обеспечения. Этому аспекту транзакционных систем посвящается лекция 14.

Заметим, что хотя с точки зрения обеспечения целостности баз данных механизм транзакций следовало бы поддерживать в персональных СУБД, на практике это обычно не выполняется. Поэтому при переходе от персональных к многопользовательским СУБД пользователи сталкиваются с необходимостью четкого понимания природы транзакций.



Общие определения


Пусть задана переменная отношения R, и X и Y являются произвольными подмножествами заголовка R («составными» атрибутами).

В значении переменной отношения R атрибут Y функционально зависит от атрибута X в том и только в том случае, если каждому значению X соответствует в точности одно значение Y. В этом случае говорят также, что атрибут X функционально определяет атрибут Y (X является детерминантом (определителем) для Y, а Y является зависимым от X). Будем обозначать это как R.X

R.Y.

Для примера будем использовать отношение СЛУЖАЩИЕ_ПРОЕКТЫ {СЛУ_НОМ, СЛУ_ИМЯ, СЛУ_ЗАРП, ПРО_НОМ, ПРОЕКТ_РУК} (). Очевидно, что если СЛУ_НОМ является первичным ключом отношения СЛУЖАЩИЕ, то для этого отношения справедлива функциональная зависимость (Functional Dependency – FD) СЛУ_НОМ

СЛУ_ИМЯ.

На самом деле, для тела отношения СЛУЖАЩИЕ_ПРОЕКТЫ в том виде, в котором оно показано на , выполняются еще и следующие FD (1):


Рис. 7.1.  Пример возможного тела отношения СЛУЖАЩИЕ_ПРОЕКТЫ

СЛУ_НОМ

СЛУ_ИМЯ СЛУ_НОМ
СЛУ_ЗАРП СЛУ_НОМ
ПРО_НОМ СЛУ_НОМ
ПРОЕКТ_РУК {СЛУ_НОМ, СЛУ_ИМЯ}
СЛУ_ЗАРП {СЛУ_НОМ, СЛУ_ИМЯ}
ПРО_НОМ {СЛУ_НОМ, СЛУ_ИМЯ}
{СЛУ_ЗАРП, ПРО_НОМ} … ПРО_НОМ
ПРОЕКТ_РУК и т.д.

Поскольку имена всех служащих различны, то выполняются и такие FD (2):

СЛУ_ИМЯ

СЛУ_НОМ СЛУ_ИМЯ
СЛУ_ЗАРП СЛУ_ИМЯ
ПРО_НОМ и т.д.

Более того, для примера на выполняется и FD (3):

СЛУ_ЗАРП

ПРО_НОМ

Однако заметим, что природа FD группы (1) отличается от природы FD групп (2) и (3). Логично предположить, что идентификационные номера служащих должны быть всегда различны, а у каждого проекта имеется только один руководитель. Поэтому FD группы (1) должны быть верны для любого допустимого значения переменной отношения СЛУЖАЩИЕ_ПРОЕКТЫ и могут рассматриваться как инварианты, или ограничения целостности этой переменной отношения.

FD группы (2) базируются на менее естественном предположении о том, что имена всех служащих различны. Это соответствует действительности для примера из , но возможно, что с течением времени FD группы (2) не будут выполняться для какого-либо значения переменной отношения СЛУЖАЩИЕ_ПРОЕКТЫ.


Наконец, FD группы (3) основана на совсем неестественном предположении, что никакие двое служащих, участвующие в разных проектах, не получают одинаковую зарплату. Опять же, данное предположение верно для примера из , но, скорее всего, это случайное совпадение.

В дальнейшем нас будут интересовать только те функциональные зависимости, которые должны выполняться для всех возможных значений переменных отношений.

Заметим, что если атрибут A отношения R является возможным ключом, то для любого атрибута B этого отношения всегда выполняется FD A
B (в группе (1) к этим FD относятся все FD, детерминантом которых является СЛУ_НОМ). Обратите внимание, что наличие в отношении СЛУЖАЩИЕ_ПРОЕКТЫ FD ПРО_НОМ
ПРОЕКТ_РУК приводит к некоторой избыточности этого отношения. Имя руководителя проекта является характеристикой проекта, а не служащего, но в нашем случае содержится в теле отношения столько раз, сколько служащих работает над проектом.

Итак, мы будем иметь дело с FD, которые выполняются для всех возможных состояний тела соответствующего отношения и могут рассматриваться как ограничения целостности. Как показывает (неполный) список (1), таких зависимостей может быть очень много. Поскольку они трактуются как ограничения целостности, за их соблюдением должна следить СУБД. Поэтому важно уметь сократить набор FD до минимума, поддержка которого гарантирует выполнение всех зависимостей. Мы займемся этим в следующих подразделах.

FD A
B называется тривиальной, если A
B (т. е. множество атрибутов A включает множество B или совпадает с множеством B).

Очевидно, что любая тривиальная FD всегда выполняется. Например, в отношении СЛУЖАЩИЕ_ПРОЕКТЫ всегда выполняется FD {СЛУ_ЗАРП, ПРО_НОМ}
СЛУ_ЗАРП. Частным случаем тривиальной FD является A
A.

Поскольку тривиальные FD выполняются всегда, их нельзя трактовать как ограничения целостности, и поэтому они не представляют интереса с практической точки зрения. Однако в теоретических рассуждениях их наличие необходимо учитывать.


Общие принципы организации данных во внешней памяти в SQL-ориентированных СУБД


В этом разделе кратко обсуждаются основные подходы к организации данных во внешней памяти, принятые в современных SQL-ориентированных СУБД. В большинстве случаев они основаны на идеях, заложенных в System R, хотя, конечно, в любой развитой системе имеются собственные приемы, которые здесь обсуждаться не будут.

SQL-ориентированные СУБД обладают рядом особенностей, влияющих на организацию внешней памяти. Наиболее важным автору кажутся следующие особенности:

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

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

Регулярность структур данных. Поскольку основным объектом модели данных SQL является плоская таблица, основной набор объектов внешней памяти может иметь очень простую регулярную структуру.

Необходимость обеспечения возможности эффективного выполнения операторов языкового уровня как над одной таблицей (простые селекция и проекция), так и над несколькими таблицами (наиболее распространено и трудоемко соединение нескольких таблиц). Для этого во внешней памяти должны поддерживаться дополнительные «управляющие» структуры – индексы.

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

Соответственно возникают следующие разновидности объектов во внешней памяти базы данных:

строки таблиц – основная часть базы данных, большей частью непосредственно видимая пользователям;

управляющие структуры – индексы, создаваемые по инициативе пользователя (администратора) или верхнего уровня системы из соображений повышения эффективности выполнения запросов и обычно автоматически поддерживаемые нижним уровнем системы;

журнальная информация, поддерживаемая для удовлетворения потребности в надежном хранении данных;

служебная информация, поддерживаемая для удовлетворения внутренних потребностей нижнего уровня системы (например, информация о свободной памяти).



Общие синтаксические правила построения скалярных выражений


В SQL:2003 имеются девять разновидностей выражений в соответствии с девятью категориями типов данных, значения которых вырабатываются при вычислении выражения

value_expression ::= numeric_value_expression | string_value_expression | datetime_value_expression | interval_value_expression | boolean_value_expression | array_value_expression | multiset_value_expression | row_value_expression | user_defined_value_expression | reference_value_expression

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

value_expression_primary ::= unsigned_value_specification | column_reference | set_function_specification | scalar_subquery | case_expression | (value_expression) | cast_specification

В пределах этого курса можно считать, что спецификация беззнакового значения (unsigned_value_specification) – это всегда литерал соответствующего типа или вызов ниладической функции (например, CURRENT_USER). При вычислении выражения V для строки таблицы каждая ссылка на столбец (column_reference) этой таблицы, непосредственно содержащаяся в V, рассматривается как ссылка на значение данного столбца в данной строке. Агрегатные функции (функции над множествами – set_function_specification) обсуждаются в лекции 19. Если первичное выражение является скалярным подзапросом (scalar_subquery, или подзапросом, результатом которого является таблица, состоящая из одной строки и одного столбца) и результат подзапроса пуст, то результат первичного выражения – неопределенное значение. (Подзапросы обсуждаются в следующей лекции, выражения с переключателем (case_expression) рассматриваются ниже в этом разделе.)



Обзор реляционной алгебры Кодда


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

Существует много подходов к определению реляционной алгебры, которые различаются наборами операций и способами их интерпретации, но, в принципе, являются более или менее равносильными. В данном разделе мы опишем немного расширенный начальный вариант алгебры, который был предложен Коддом (будем называть ее «алгеброй Кодда»). В этом варианте набор основных алгебраических операций состоит из восьми операций, которые делятся на два класса – теоретико-множественные операции и специальные реляционные операции. В состав теоретико-множественных операций входят операции: объединения отношений;пересечения отношений;взятия разности отношений;взятия декартова произведения отношений.

Специальные реляционные операции включают: ограничение отношения;проекцию отношения;соединение отношений;деление отношений.

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



Ограничения целостности


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


В иерархической модели данных автоматически поддерживается целостность ссылок между предками и потомками. Основное правило: никакой потомок не может существовать без своего родителя.

Заметим, что аналогичная поддержка целостности по ссылкам между записями без связи «предок-потомок», не обеспечивается. Примером такой «внешней» ссылки является содержимое поля Рук_Отдел

в экземпляре типа записи Руководитель.




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

Заметим, что перечисляемые ниже характеристики в полной мере относятся и к другим не реляционным подходам к организации баз данных, которые возникли до появления реляционного подхода или почти одновременно с ним. В частности, подобными свойствами обладают системы, основанные на подходах MUMPS (наиболее известной в России является реализация этого подхода в СУБД Cache компании Intersystems) и Pick (этот подход реализован во многих СУБД, в частности, в СУБД UniVerse и UniData семейства U2 компании IBM).



Ограничения целостности и язык OCL


Как уже отмечалось, в диаграммах классов могут указываться ограничения целостности, которые должны поддерживаться в проектируемой БД. В UML допускаются два способа определения ограничений: на естественном языке и на языке OCL. На показана простая диаграмма классов Студент и Университет с ограничением, выраженным на естественном языке.


Рис. 11.13.  Ограничение, выраженное на естественном языке

В данном случае накладывается ограничение на состояние объектов классов Студент и Университет, входящих в один экземпляр ассоциации. Объект класса Студент может входить в экземпляр связи с объектом класса Университет только при условии, что размер стипендии данного студента находится в диапазоне, допустимом в данном университете.



Ограничения целостности столбца


Элемент необязательного списка ограничений целостности столбца определяется следующими синтаксическими правилами:

column_constraint_definition ::= [ CONSTRAINT constraint_name ] NOT NULL | { PRIMARY KEY | UNIQUE } | references_definition | CHECK ( conditional_expression )

Как мы увидим немного позже, любое ограничение целостности, включаемое в определение столбца, может быть эквивалентным образом выражено в виде табличного ограничения целостности. Единственный резон определения ограничений на уровне столбца состоит в том, что в этом случае в ограничении целостности не требуется явно указывать имя столбца. Тем не менее, кратко рассмотрим ограничения целостности столбца отдельно.

Ограничение NOT NULL означает, что в определяемом столбце никогда не должны содержаться неопределенные значения. Если определяемый столбец имеет имя C, то это ограничение эквивалентно следующему табличному ограничению: CHECK (C IS NOT NULL).

В определение столбца может входить одно из ограничений уникальности: ограничение первичного ключа (PRIMARY KEY) или ограничение возможного ключа (UNIQUE). Включение в определение столбца любого из этих ограничений означает требование уникальности значений определяемого столбца (т. е. во все время существования определяемой таблицы во всех ее строках значения данного столбца должны быть различны). Ограничение PRIMARY KEY, в дополнение к этому, влечет за собой ограничение NOT NULL для определяемого столбца. Эти ограничения столбца эквивалентны следующим табличным ограничениям: PRIMARY KEY (C) и UNIQUE (С).

Ограничение references_definition означает объявление определяемого столбца внешним ключом таблицы и обладает следующим синтаксисом:

references_definition ::= REFERENCES base_table_name [ (column_commalist) ] [ MATCH { SIMPLE | FULL | PARTIAL } ] [ ON DELETE referential_action ] [ ON UPDATE referential_action ]

На самом деле, данная синтаксическая конструкция работает и в случае определения внешнего ключа на уровне таблицы (в одном из определений табличных ограничений целостности).
Поэтому мы отложим обсуждение до рассмотрения этого общего случая. Пока отметим только, что при использовании конструкции на уровне определения столбца  column_commalist может содержать имя только одного столбца (потому что внешний ключ состоит из одного определяемого столбца). Ограничение эквивалентно следующему табличному ограничению: FOREIGN KEY (C) references_definition.

Проверочное ограничение CHECK (conditional_expression) приводит к тому, что в данном столбце могут находиться только те значения, для которых вычисление conditional_expression не приводит к результату false. В условном выражении проверочного ограничения столбца разрешается использовать имя только определяемого столбца. Заметим, что проверочное ограничение столбца может быть безо всяких изменений перенесено на уровень определения табличных ограничений.

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

  Заметим, что хотя столбец может получить значение NULL по умолчанию как явным, так и неявным образом, эти два случая не являются эквивалентными. Явное задание NULL в качестве значения по умолчанию запрещает наследование столбцом значения по умолчанию домена.

  В этом случае SQL опирается на семантику неопределенных значений, отличную от используемой в большинстве других случаев. Считается, что (NULL = NULL) = true и что (a = NULL) = (NULL = a) = false для любого значения a, отличного от NULL.


Ограничения целостности в истинной реляционной модели


В число обязательных требований истинной реляционной модели входит требование определения хотя бы одного возможного ключа для каждой переменной отношения (возможный ключ – это одно из подмножеств заголовка переменной отношения, обладающее упоминавшимися в подразделе свойствами первичного ключа). Кроме того, говорится, что «любое условное выражение, которое является (или логически эквивалентно) замкнутой правильно построенной формулой (WFF) реляционного исчисления, должно быть допустимо в качестве спецификации ограничения целостности» .

Средства поддержки декларативной ссылочной целостности фигурируют только в разделе рекомендуемых возможностей: «В D

[конкретную реализацию истинной реляционной модели] следует включить некоторую декларативную сокращенную форму для выражения ссылочных ограничений (называемых также ограничениями внешнего ключа)».



Ограничения целостности в модели SQL


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

Ссылочная целостность в модели данных SQL поддерживается в обязательном порядке, но в трех разных вариантах, лишь один из которых полностью соответствует реляционной модели. Это связано с уже упоминавшимся в этом разделе интенсивным использованием в SQL неопределенных значений. Подробнее особенности ограничений ссылочной целостности в SQL рассматриваются в лекции 16.

Кроме того, в SQL имеются развитые возможности явного определения ограничений целостности на уровне столбцов таблиц, на уровне таблиц целиком и на уровне базы данных.



Ограничения целостности в объектной модели


В соответствии с общей идеологией объектно-ориентированного подхода в модели ODMG два объекта считаются совпадающими в том и только в том случае, когда являются одним и тем же объектом, т.е. имеют один и тот же OID. Объекты одного объектного типа с разными OID считаются разными, даже если обладают полностью совпадающими состояниями. Поэтому в объектной модели отсутствует аналог ограничения целостности сущности реляционной модели данных. Интересно, что при определении атомарного объектного типа можно объявить ключ – набор свойств объектного класса, однозначно идентифицирующий состояние каждого объекта, входящего в экстент этого класса. Для класса может быть объявлено несколько ключей, а может не быть объявлено ни одного ключа даже при наличии определения экстента. Но при этом определение ключа не трактуется в модели как ограничение целостности; утверждается, что объявление ключа способствует повышению эффективности выполнения запросов.

Что же касается ссылочной целостности, то она поддерживается, если между двумя атомарными объектными типами определяется связь вида «один-ко-многим». В этом случае объекты на стороне связи «один» рассматриваются как предки, а объекты на стороне связи «многие» – как потомки, и ООСУБД обязана следить за тем, чтобы не образовывались потомки без предков.



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


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



Операции exists, forAll, size


В OCL определены три одноименных операции exists над множеством, мультимножеством и последовательностью, дополнительным параметром которых является логическое выражение. В результате каждой из этих операций выдается true в том и только в том случае, когда хотя бы для одного элемента входной коллекции значением логического выражения является true. В противном случае результатом операции является false. Операции forAll отличаются от операций exists тем, что в результате каждой из них выдается true в том и только в том случае, когда для всех элементов входной коллекции результатом вычисления логического выражения является true. В противном случае результатом операции будет false. Операция size применяется к коллекции и выдает число содержащихся в ней элементов.



Операции модификации таблиц и списков


Группа операций модификации таблиц и списков включает операции вставки кортежа в таблицу или список (INSERT), удаления кортежа из таблицы (DELETE) и обновления кортежа в таблице (UPDATE).

Параметрами операции вставки кортежа являются идентификатор таблицы или списка и набор значений полей кортежа. Среди значений полей могут быть литеральные неопределенные значения NULL. Естественно, при выполнении операции контролируется допустимость неопределенных значений в соответствующих полях. При занесении кортежа в кластеризованную таблицу поиск места в сегменте под кортеж производится с использованием кластеризованного индекса: система пытается вставить кортеж в страницу данных, уже содержащую кортежи с теми же или близкими значениями полей кластеризации. При занесении кортежа в некластеризованную таблицу место под кортеж выделяется в первой подходящей странице данных. Наконец, при вставке кортежа в список он помещается в конец списка.

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

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


Операции удаления и модификации кортежей допускаются только для кортежей таблиц. Естественно, что для выполнения этих операций необходимо идентифицировать соответствующий кортеж. В интерфейсе RSS допускаются два способа такой идентификации: с помощью идентификатора кортежа (явная адресация) и с использованием идентификатора открытого к этому времени сканирования. Первый вариант возможен, поскольку идентификатор кортежа сообщается как ответный параметр операции занесения кортежа в постоянную таблицу. При идентификации кортежа с помощью идентификатора сканирования имеется в виду кортеж, прочитанный с помощью последней операции NEXT. Если при такой идентификации выполняется операция DELETE

или операция UPDATE, задевающая порядок сканирования (т.е. сканирование ведется по индексу и операция модификации меняет поле кортежа, входящее в состав ключа этого индекса), то текущий кортеж сканирования теряется, и его идентификатор нельзя использовать для идентификации кортежа, пока не будет выполнена следующая операция NEXT.

Единственным параметром операции DELETE

является идентификатор кортежа или идентификатор сканирования. Параметры операции UPDATE

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

производится коррекция всех индексов, определенных на данной таблице. Операция UPDATE

также может повлечь коррекцию индексов, если затрагивает поля, входящие в состав их ключей.

Кроме описанных «атомарных» операций сканирования и модификации таблиц и списков, интерфейс RSS включает одну «макрооперацию» BUILDLIST, позволяющую за одно обращение к RSS построить список, отсортированный в соответствии со значениями заданных полей. Эта операция включает сканирование заданной таблицы или списка, создание нового списка, в который включаются указанные поля выбираемых кортежей, и сортировку построенного списка в соответствии со значениями указанных полей.Идентификатор заново построенного отсортированного списка является ответным параметром операции.

Соответственно, параметрами операции BUILDLIST

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

является признак, в соответствии со значением которого в новом списке допускаются или не допускаются кортежи-дубликаты.


Операции над множествами, мультимножествами и последовательностями


В OCL поддерживается обширный набор операций над значениями коллекционных типов данных. Обсудим только те из них, которые являются уместными в контексте данной лекции. Синтаксически операции над коллекциями записываются в нотации, аналогичной точечной, но вместо точки используется стрелка (

). Таким образом, общий синтаксис применения операции к коллекции следующий:

<коллекция>

<имя операции> (<список фактических параметров>)



Операции над объектами


В OCL определены три операции над объектами: получение значения атрибута; переход по соединению, вызов операции класса (последняя операция для целей проектирования реляционных БД несущественна).

Для записи этих трех операций используется «точечная нотация». Например, результатом выражения вида

<объект>.<имя атрибута>

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

Результатом применения к объекту операции перехода по соединению (экземпляру связи-ассоциации) является коллекция, содержащая все объекты, которые ассоциированы с данным объектом через указываемое соединение. Это соединение идентифицируется именем роли, противоположной по отношению к данному объекту. Таким образом, синтаксис выражения перехода по соединению следующий:

<объект>.<имя роли, противоположенной по отношению к объекту>



Операции над значениями предопределенных типов данных


Полагая очевидной семантику предопределенных скалярных типов данных и операций над ними, ограничимся лишь их перечислением. В OCL поддерживаются следующие заимствованные из определения UML скалярные типы данных: Boolean, Integer, Real и String.



Операции объединения, пересечения, взятия разности. Совместимость по объединению


Начнем с операции объединения отношений (все, что будет сказано по поводу объединения, верно и для операций пересечения и взятия разности отношений). Смысл операции объединения в реляционной алгебре в целом остается теоретико-множественным. Еще раз напомним (см. ), что в теории множеств: результатом объединения двух множеств A{a} и B{b} является такое множество C{c}, что для каждого с либо существует такой элемент a, принадлежащий множеству A, что c=a, либо существует такой элемент b, принадлежащий множеству B, что c=b;пересечением множеств A и B является такое множество C{c}, что для любого c существуют такие элементы a, принадлежащий множеству A, и b, принадлежащий множеству B, что c=a=b;разностью множеств A и B является такое множество C{c}, что для любого c существует такой элемент a, принадлежащий множеству A, что c=a, и не существует такой элемент b, принадлежащий B, что c=b.

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

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

Если два отношения совместимы по объединению, то при обычном выполнении над ними операций объединения, пересечения и взятия разности результатом операции является отношение с корректно определенным заголовком, совпадающим с заголовком каждого из отношений-операндов.
Напомним, что если два отношения «почти» совместимы по объединению, т. е. совместимы во всем, кроме имен атрибутов, то до выполнения операции типа объединения эти отношения можно сделать полностью совместимыми по объединению путем применения операции переименования.

Для иллюстрации операций объединения, пересечения и взятия разности предположим, что в базе данных имеются два отношения СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 и СЛУЖАЩИЕ_В_ПРОЕКТЕ_2 с одинаковыми схемами {СЛУ_НОМЕР, СЛУ_ИМЯ, СЛУ_ЗАРП, СЛУ_ОТД_НОМЕР} (имена доменов опущены по причине очевидности). Каждое из отношений содержит данные о служащих, участвующих в соответствующем проекте. На показано примерное наполнение каждого из двух отношений (некоторые служащие участвуют в обоих проектах).



Рис. 4.2.  Примерное наполнение отношений СЛУЖАЩИЕ _В_ПРОЕКТЕ_1 и СЛУЖАЩИЕ _В_ПРОЕКТЕ_2

Тогда выполнение операции СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 UNION СЛУЖАЩИЕ_В_ПРОЕКТЕ_2 позволит получить информацию обо всех служащих, участвующих в обоих проектах. Выполнение операции СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 INTERSECT СЛУЖАЩИЕ_В_ПРОЕКТЕ_2 позволит получить данные о служащих, которые одновременно участвуют в двух проектах. Наконец, операция СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 MINUS СЛУЖАЩИЕ_В_ПРОЕКТЕ_2 выработает отношение, содержащее кортежи служащих, которые участвуют только в первом проекте. Результаты этих операций показаны на .



Рис. 4.3.  Результаты выполнения операций UNION, INTERSECT и MINUS

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


Операции обновления баз данных и механизм триггеров


Термин триггер в контексте реляционных баз данных был введен в обиход участниками проекта System R (лекции 12, 15). В терминологии этого проекта триггером называлась хранимая в базе данных процедура, автоматически вызываемая СУБД при возникновении соответствующих условий.При определении триггера указывались два условия его применимости – общее условие (имя отношения и тип операции манипулирования данными) и конкретное условие (логическое выражение, построенное по правилам, близким к правилам ограничений целостности), а также действие, которое должно быть выполнено над БД при наличии условий применимости.

Конечно, термин триггер в данном контексте является жаргонным. Но, с другой стороны, он достаточно точно соответствует ситуации: для применения процедуры должны быть произведены «возбуждающие» ее действия. Как отмечалось в лекции 15, после завершения проекта System R на протяжении более десяти лет триггеры не поддерживались ни в одной коммерческой SQL-ориентированной СУБД. Но затем практически во всех ведущих СУБД механизм триггеров в том или ином виде был реализован.

В стандарте же языка SQL спецификации триггеров отсутствовали до принятия стандарта SQL:1999. По словам главного редактора стандартов SQL/92 и SQL:1999 Джима Мелтона, эта спецификация была уже полностью готова к моменту принятия SQL/92 и не вошла в текст стандарта только по причине ограниченности его объема. Однако, как мне кажется, этому препятствовали и расхождения в подходах, существовавшие между основными компаниями-производителями СУБД.

Заметим, что альтернативным термином по отношению к базам данных, содержащим триггерные процедуры, является термин активная база данных. Наверное, этот термин более точен, поскольку действительно речь идет о базах данных, содержащих процедуры, которые автоматически вызываются при срабатывании связанных с ними правил. Однако в обиходе пользователей SQL-ориентированных СУБД по-прежнему более распространен термин триггер.



Операции сканирования таблиц и списков


Операции группы сканирования позволяют последовательно, в порядке, определяемом типом сканирования, прочитать кортежи таблицы или списка, удовлетворяющие требуемым условиям. Группа включает операции OPEN, NEXT

и CLOSE, означающие, соответственно, начало сканирования, требование чтения следующего кортежа, удовлетворяющего условиям, и конец сканирования.

Для таблицы возможны два режима сканирования: прямое сканирование и сканирование через индекс. При прямом сканировании единственным параметром операции OPEN

является идентификатор таблицы (включающий и идентификатор сегмента, в котором эта таблица хранится). По причине того, что в System R допускается размещение в одной странице данных кортежей нескольких таблиц, прямое сканирование предполагает последовательный просмотр всех страниц сегмента с выделением в них кортежей, входящих в данную таблицу; это очень дорогой способ сканирования таблицы. При этом порядок выборки кортежей определяется их физическим размещением в страницах сегмента, т.е. предопределен системой.

При начале сканирования таблицы через индекс в число параметров операции OPEN

входит идентификатор какого-либо индекса, определенного ранее на полях этой таблицы. Кроме того, можно указать диапазон сканирования в терминах значений поля (полей), составляющего ключ индекса. При открытии сканирования через индекс производится начальная установка указателя сканирования в позицию листа B-дерева (см. подраздел ) индекса, соответствующую левой границе заданного диапазона. Процесс сканирования состоит в последовательном продвижении по листовым вершинам индекса до достижения правой границы диапазона сканирования с выборкой идентификаторов кортежей и чтением соответствующих кортежей. Легко видеть, что в худшем случае может потребоваться столько чтений страниц данных из внешней памяти, сколько идентификаторов кортежей было встречено, т.е. эффективность сканирования по индексу определяется «широтой» заданного диапазона сканирования. При этом, конечно, имеется то преимущество, что порядок сканирования соответствует порядку возрастания или убывания значений ключа индекса.


Наконец, при сканировании списка, как и при прямом сканировании таблицы, единственным параметром операции OPEN

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

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

Операция NEXT

выполняет чтение следующего кортежа указанного сканирования, удовлетворяющего условию данной операции. Условие представляет собой дизъюнктивную нормальную форму простых условий, накладываемых на значения указанных полей таблицы. Простое условие – это условие вида номер-поля op константа, где op

– операция сравнения <, <=, >, >=, =

или !=. Общее условие является параметром операции NEXT.

Семантика операции NEXT

следующая: начиная с текущей позиции сканирования выбираются кортежи таблицы в порядке, определяемом типом сканирования, до тех пор, пока не встретится кортеж, значения полей которого удовлетворяют указанному условию. Этот кортеж и является результатом операции. Если при выборке кортежа достигается правая граница диапазона сканирования (правая граница значения ключа при сканировании через индекс или последний кортеж таблицы или списка при прямом сканировании), то вырабатывается особый признак результата. После этого единственным разумным действием является закрытие сканирования – операция CLOSE

Операция CLOSE

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


Операции создания и уничтожения постоянных и временных объектов базы данных


Группа операций создания и уничтожения постоянных и временных объектов базы данных включает операции создания таблиц (CREATE TABLE), списков (CREATE LIST), индексов (CREATE IMAGE) и уничтожения любого из подобных объектов (DROP TABLE, DROP LIST и DROP IMAGE). Входным параметром операций создания таблиц и списков является спецификатор структуры объекта, т.е. число полей объекта и спецификаторы их типов. Кроме того, при спецификации полей таблицы указывается разрешение или запрещение наличия неопределенных значений полей в кортежах этой таблицы или списка. Неопределенные значения кодируются специальным образом. Любая операция сравнения константы данного типа с неопределенным значением по определению вырабатывает значение false, кроме операции сравнения на совпадение со специальной литеральной константой NULL.

В результате выполнения этих операций заводится описатель в служебной таблице описателей таблиц или основной памяти (в зависимости от того, создается ли постоянный объект или временный), и вырабатывается идентификатор объекта, который служит входным параметром других операций, относящихся к соответствующему объекту (в частности, параметром операции OPEN

при открытии сканирования объекта).

Входными параметрами операции CREATE IMAGE

являются идентификатор таблицы, для которой создается индекс, список номеров полей, значения которых составляют ключ индекса, и признаки упорядочения по возрастанию или убыванию для всех полей, составляющих ключ. Кроме того, может быть указан признак уникальности индекса, т.е. запрещения наличия в данном индексе ключей-дубликатов. Если операция выполняется по отношению к пустой в этот момент таблице, то выполнение операции такое же простое, как и для операций создания таблиц и списков: создается описатель в служебной таблице описателей индексов и возвращается идентификатор индекса (который, в частности, используется в качестве аргумента операции открытия сканирования таблицы через индекс).

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

Операции DROP TABLE, DROP LIST

и DROP IMAGE

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

Следует отметить, что массовые операции над постоянными объектами (CREATE IMAGE и DROP TABLE) требуют дополнительных накладных расходов в связи с необходимостью обеспечения возможности откатов транзакции, для чего требуется выполнение массовых обратных действий. Особенно сильно это затрагивает операцию уничтожения непустых таблиц, поскольку требует журнализации всех кортежей, содержащихся в них к моменту уничтожения. Поэтому, хотя уничтожение непустых таблиц и не запрещено, нужно иметь в виду, что это очень дорогостоящая операция.


Операции union, intersect, symmetricDifference


Параметрами двуместных операций union, intersect, symmetricDifference являются две коллекции, причем в OCL операции определены почти для всех возможных комбинаций типов коллекции. Не будем рассматривать все определения этих операций и кратко упомянем только две из них. Результатом операции union, определенной над множеством и мультимножеством, является мультимножество, т. е. из результата объединения таких двух коллекций дубликаты не исключаются. Результатом же операции union, определенной над двумя множествами, является множество, т. е. в этом случае возможные дубликаты должны быть исключены.



Операции управления прохождением транзакций


Каждая операция RSS выполняется в пределах некоторой транзакции. Интерфейс RSS включает набор операций управления прохождением транзакции: начать транзакцию (BEGIN TRANSACTION), закончить транзакцию (END TRANSACTION), установить точку сохранения (SAVE) и выполнить откат до указанной точки сохранения или до начала транзакции (RESTORE).

Это не отмечалось раньше, но на самом деле при вызове любой операции функции RSS, кроме BEGIN TRANSACTION, должен указываться еще один параметр – идентификатор транзакции. Этот идентификатор и вырабатывается при выполнении операции BEGIN TRANSACTION, которая сама входных параметров не требует.

В любой точке транзакции до выполнения операции END TRANSACTION

может быть выполнен откат данной транзакции, т.е. обратное выполнение всех изменений, произведенных в данной транзакции, и восстановление состояния позиций сканирования. Откат может быть произведен до начала транзакции (в этом случае о восстановлении позиций сканирования говорить бессмысленно) или до установленной ранее в транзакции точки сохранения.

Точка сохранения устанавливается с помощью операции SAVE. При выполнении этой операции запоминаются состояние сканов данной транзакции, открытых к моменту выполнения SAVE, и координаты последней записи об изменениях в базе данных в журнале, произведенной от имени данной транзакции. Ответным параметром операции SAVE

(а прямых параметров, кроме идентификатора транзакции, она не требует) является идентификатор точки сохранения. Этот идентификатор в дальнейшем может быть использован как аргумент операции RESTORE, при выполнении которой производится восстановление базы данных по журналу (с использованием записей о ее изменениях от данной транзакции) до того состояния, в котором находилась база данных к моменту установки указанной точки сохранения. Кроме того, по локальной информации в оперативной памяти, привязанной к транзакции, восстанавливается состояние ее сканов. Откат к началу транзакции инициируется также вызовом операции RESTORE, но с указанием некоторого предопределенного идентификатора точки сохранения.


При выполнении своих транзакций пользователи System R изолированы один от другого, т.е. не ощущают того, что система функционирует в многопользовательском режиме. Это достигается за счет наличия в RSS механизма неявной синхронизации. До конца транзакции никакие изменения базы данных, произведенные в пределах этой транзакции, не могут быть использованы в других транзакциях (попытка использования таких данных приводит к временным синхронизационным блокировкам этих транзакций). При выполнении операции END TRANSACTION

происходит "фиксация" изменений, произведенных в данной транзакции, т.е. они становятся видимыми в других транзакциях. Реально это означает снятие синхронизационных блокировок с объектов базы данных, изменявшихся в транзакции. Из этого следует, что после выполнения END TRANSACTION

невозможны индивидуальные откаты данной транзакции. RSS просто делает недействительным идентификатор данной транзакции, и после выполнения операции окончания транзакции отвергает все операции с таким идентификатором.


Операция collect


Аналогично набору операций select, в OCL определены три операции collect, параметрами которых являются множество, мультимножество или последовательность и некоторое выражение над элементами соответствующей коллекции. Результатом является мультимножество для операций collect, определенных над множествами и мультимножествами, и последовательность для операции collect, определенной над последовательностью. При этом результирующая коллекция соответствующего типа (коллекция значений или объектов) состоит из результатов применения выражения к каждому элементу входной коллекции. Операция collect используется, главным образом, в тех случаях, когда от заданной коллекции объектов требуется перейти к некоторой другой коллекции объектов, которые ассоциированы с объектами исходной коллекции через некоторое соединение. В этом случае выражение над элементом исходной коллекции основывается на операции перехода по соединению.



Операция деления отношений


Эта операция наименее очевидна из всех операций реляционной алгебры Кодда и поэтому нуждается в более подробном объяснении. Пусть заданы два отношения – A с заголовком {a1, a2, ..., an, b1, b2, ..., bm} и B с заголовком {b1, b2, ..., bm}. Будем считать, что атрибут bi отношения A и атрибут bi отношения B (i = 1, 2, …, m) не только обладают одним и тем же именем, но и определены на одном и том же домене. Назовем множество атрибутов {aj} составным атрибутом a, а множество атрибутов {bj} – составным атрибутом b. После этого будем говорить о реляционном делении «бинарного» отношения A{a, b} на унарное отношение B{b}.

По определению, результатом деления A на B (A DIVIDE BY B) является «унарное» отношение C{a}, тело которого состоит из кортежей v таких, что в теле отношения A содержатся кортежи v UNION w такие, что множество {w} включает тело отношения B. Операция реляционного деления не является примитивной и выражается через операции декартова произведения, взятия разности и проекции. Мы покажем это в следующей лекции.

Для иллюстрации этой операции предположим, что в базе данных служащих поддерживаются следующие отношения: СЛУЖАЩИЕ, как оно было определено ранее, и унарное отношение НОМЕРА_ПРОЕКТОВ {ПРО_НОМ} (). Тогда запрос СЛУЖАЩИЕ DIVIDE BY НОМЕРА_ПРОЕКТОВ выдаст данные обо всех служащих, участвующих во всех проектах (результат операции приведен также на ).


Рис. 4.10.  Пример реляционного деления



Операция добавления поля к существующей таблице


Операция RSS добавления поля к существующей таблице позволяет в динамике изменять схему таблицы. Параметрами операции CHANGE

являются идентификатор существующей таблицы и спецификация нового поля (его тип). При выполнении операции изменяется только описатель данной таблицы в служебной таблице описателей таблиц. До выполнения первой операции UPDATE, затрагивающей новое поле таблицы, реально ни в одном кортеже таблицы память под новое поле выделяться не будет. По умолчанию значения нового поля во всех кортежах таблицы, в которые еще не производилось явное занесение значения, считаются неопределенными. Тем самым, ни для одного поля, динамически добавленного к существующей таблице, не может быть запрещено хранение неопределенных значений.



Операция явной синхронизации


Последняя операция интерфейса RSS – операция явной синхронизации LOCK. Эта операция позволяет установить явную синхронизационную блокировку указанной таблицы (параметром операции является идентификатор таблицы). Выполнение операции LOCK

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

Из всего, что говорилось раньше по поводу подхода к синхронизации в System R и соответствующего разбиения системы на уровни, следует нелогичность наличия этой операции в интерфейсе RSS. На самом деле, логически эта операция избыточна, т.е. если бы ее не было, можно было бы реализовать SQL с использованием оставшейся части операций. Предварительно (до подробного обсуждения средств управления транзакциями в лекции 13) заметим, что операция LOCK

введена в интерфейс RSS для возможности оптимизации выполнения запросов.

Дело в том, что, как видно из описания интерфейса RSS, этот интерфейс является покортежным. Следовательно, и информация для синхронизации носит достаточно узкий характер. В то же время, на уровне SQL имеется более полная информация. Например, если обрабатывается предложение SQL DELETE FROM table_name, то известно, что будут удалены все кортежи указанной таблицы. Понятно, что как бы не реализовывался механизм синхронизации в RSS, в данном случае выгоднее сообщить сразу, что изменения касаются всей таблицы.

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



Операция ограничения


Операция ограничения WHERE требует наличия двух операндов: ограничиваемого отношения и простого условия ограничения. Простое условие ограничения может иметь: вид (a comp-op b), где i>a и i>b – имена атрибутов ограничиваемого отношения; атрибуты i>a и i>b должны быть определены на одном и том же домене, для значений базового типа данных которого поддерживается операция сравнения i>comp-op, или на базовых типах данных, над значениями которых можно выполнять эту операцию сравнения;или вид (a comp-op const), где a – имя атрибута ограничиваемого отношения, а const – литерально заданная константа; атрибут a должен быть определен на домене или базовом типе, для значений которого поддерживается операция сравнения comp-op.

Операцией сравнения comp-op могут быть «=», «

», «>», «
», «<», «
». Простые условия вычисляются в трехзначной логике (см. разд. «Реляционная модель данных», лекция 3), и в результате выполнения операции ограничения производится отношение, заголовок которого совпадает с заголовком отношения-операнда, а в тело входят те кортежи отношения-операнда, для которых значением условия ограничения является true. Тем самым, если в некоторых кортежах содержатся неопределенные значения, и по данной причине вычисление простого условия дает значение unknown, то эти кортежи не войдут в результирующее отношение.

Для обозначения вызова операции ограничения будем использовать конструкцию A WHERE comp, где A – ограничиваемое отношение, а comp – простое условие сравнения. Пусть comp1 и comp2 – два простых условия ограничения. Тогда по определению: A WHERE (comp1 AND comp2) обозначает то же самое, что и (A WHERE comp1) INTERSECT (A WHERE comp2);A WHERE (comp1 OR comp2) обозначает то же самое, что и (A WHERE comp1) UNION (A WHERE comp2);A WHERE NOT comp1 обозначает то же самое, что и A MINUS (A WHERE comp1).

Эти соглашения позволяют задействовать операции ограничения, в которых условием ограничения является произвольное булевское выражение, составленное из простых условий с использованием логических связок AND, OR, NOT и скобок.

Результат выполнения операции СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 WHERE (СЛУ_ЗАРП > 20000.00 AND (СЛУ_ОТД_НОМ = 310 OR СЛУ_ОТД_НОМ = 315)) (получить данные из отношения СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 о служащих, работающих в отделах 310 и 315 и получающих зарплату, превышающую 20 000.00 руб.) показан на .


Рис. 4.5.  Результат операции СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 WHERE (СЛУ_ЗАРП 200 > 20000.00 AND (СЛУ_ОТД_НОМ = 310 OR СЛУ_ОТД_НОМ = 315))

На интуитивном уровне операцию ограничения лучше всего представлять как взятие некоторой «горизонтальной» вырезки из отношения-операнда (выборки некоторых строк из таблицы).



Операция переименования


Пусть s обозначает результат операции r <RENAME> (A, B). Для обеспечения возможности выполнения операции требуется, чтобы существовал некоторый тип T, такой, что <A, T>

Hr, и чтобы не существовал такой тип T, что <B, T>
Hr. (Другими словами, в схеме отношения r должен присутствовать атрибут A и не должен присутствовать атрибут B.) Тогда: Hs = (Hr minus {<A, T>}) union {<B, T>}, т. е. в схеме результата B заменяет A;Bs = {ts : exists tr exists v (tr
Br and v
T and <A, T, v>
tr and ts = (tr minus {<A, T, v>}) union {<B, T, v>})}, т. е. в кортежах тела результата имя значений атрибута A меняется на B.

Операция <RENAME> производит отношение s, которое отличается от заданного отношения r только именем одного его атрибута, которое изменяется с A на B. Заголовок s такой же, как заголовок r, за исключением того, что пара <B, T> заменяет пару <A, T>. Тело s включает все кортежи тела r, но в каждом из этих кортежей триплет <B, T, v> заменяет триплет <A, T, v>.

По причине очевидности пример использования этой операции мы приводить не будем.



Операция расширенного декартова произведения и совместимость отношений относительно этой операции


Другие проблемы связаны с операцией взятия декартова произведения двух отношений. В теории множеств декартово произведение может быть получено для любых двух множеств, и элементами результирующего множества являются пары, составленные из элементов первого и второго множеств. Если говорить более точно, декартовым произведением множеств A{a} и B{b} является такое множество пар C{<c1, 2>}, что для каждого элемента <c1, c2> множества C существуют такой элемент a множества A, что c1=a, и такой элемент b множества B, что c2=b.

Поскольку отношения являются множествами, для любых двух отношений возможно получение прямого произведения. Но результат не будет отношением! Элементами результата будут не кортежи, а пары кортежей.

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

Приведем более точное определение операции расширенного декартова произведения. Пусть имеются два отношения R1{a1, a2, …, an} и R2{b1, b2, …, bm}. Тогда результатом операции R1 TIMES R2 является отношение R{a1, a2, …, an, b1, b2, …, bm}, тело которого является множеством кортежей вида {ra1, ra2, …, ran, rb1, rb2, …, rbm} таких, что {ra1, ra2, …, ran} входит в тело R1, а {rb1, rb2, …, rbm} входит в тело R2.

Но теперь возникает вторая проблема – как получить корректно сформированный заголовок отношения-результата? Поскольку схема результирующего отношения является объединением схем отношений-операндов, то очевидной проблемой может быть именование атрибутов результирующего отношения, если отношения-операнды обладают одноименными атрибутами.

Эти соображения приводят к введению понятия совместимости по взятию расширенного декартова произведения.
Два отношения совместимы по взятию расширенного декартова произведения в том и только в том случае, если пересечение множеств имен атрибутов, взятых из их схем отношений, пусто. Любые два отношения всегда могут стать совместимыми по взятию декартова произведения, если применить операцию переименования к одному из этих отношений.

Для наглядности предположим, что в придачу к введенным ранее отношениям СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 и СЛУЖАЩИЕ_В_ПРОЕКТЕ_2 в базе данных содержится еще и отношение ПРОЕКТЫ со схемой {ПРОЕКТ_НАЗВ, ПРОЕКТ_РУК} (имена доменов снова опущены) и телом, показанным на . На этом же рисунке показан результат операции СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 TIMES ПРОЕКТЫ.



Рис. 4.4.  Отношение ПРОЕКТЫ и результат операции СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 TIMES ПРОЕКТЫ

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

По поводу теоретико-множественных операций реляционной алгебры следует еще заметить, что все четыре операции являются ассоциативными. Т. е. если обозначить через OP любую из четырех операций, то (A OP B) OP C = A OP (B OP C), и, следовательно, без внесения двусмысленности можно писать A OP B OP C (A, B и C – отношения, обладающие свойствами, необходимыми для корректного выполнения соответствующей операции). Все операции, кроме взятия разности, являются коммутативными, т. е. A OP B = B OP A.

  Легко убедиться, что A INTERSECT B = A MINUS (A MINUS B) = B MINUS (B MINUS A)

.