Индивидуальные типы
Напомним, что индивидуальным типом называется UDT, основанный на единственном встроенном типе (например, INTEGER). Значения такого типа нельзя прямо использовать в операциях соответствующего базового типа, однако допускается явное приведение значений индивидуального типа к базовому типу. Поясним это на примерах.
Пусть заданы следующие определения индивидуальных типов:
CREATE TYPE EMP_NO AS INTEGER FINAL; CREATE TYPE DEPT_NO AS INTEGER FINAL; CREATE TYPE PRO_NO AS INTEGER FINAL;
Таблицу EMP можно определить следующим образом (упрощенный вариант):
CREATE TABLE EMP ( EMP_ID EMP_NO, EMP_NAME VARCHAR(20), DEPT_ID DEPT_NO, PRO_ID PRO_NO);
Такое определение таблицы приведет к тому, что хотя все три индивидуальных типа делены на одном и том же базовом типе INTEGER, попытка выполнить запрос
SELECT EMP_NAME FROM EMP WHERE EMP_ID > DEPT_ID;
будет отвергнута системой (и это правильно, поскольку, скорее всего, запрос задан по ошибке). Но если действительно требуется сравнивать идентификаторы служащих с идентификаторами их отделов, то можно воспользоваться конструкцией явного приведения типа:
SELECT EMP_NAME FROM EMP WHERE CAST (EMP_ID TO INTEGER) > CAST (DEPT_ID TO INTEGER);
Аналогичным образом будет отвергнут запрос
SELECT EMP_NAME, EMP_ID + 5 FROM EMP WHERE DEPT_ID > 630;
Чтобы указать системе, что действительно требуется выполнить операции целочисленного сложения и сравнения над значениями индивидуальных типов, запрос нужно переписать следующим образом:
SELECT EMP_NAME, CAST (EMP_ID TO INTEGER) + 5 FROM EMP WHERE CAST (DEPT_ID TO INTEGER) > 630;
У читателей могут возникнуть два законных вопроса: почему, вопреки обыкновению, мы не привели формальные синтаксические правила операции определения индивидуального типа?что означает ключевое слово FINAL в приведенных примерах определения индивидуальных типов?
На оба эти вопроса достаточно дать один (возможно, неожиданный) ответ. С формальной точки зрения индивидуальный тип данных является частным случаем структурного типа данных.
Обе разновидности UDT определяются единым синтаксисом, который мы обсудим в следующих подразделах. В частности, ключевое слово FINAL играет важную роль в определении структурного типа, указывая на тот факт, что этот тип может использоваться только для создания объектов, а не для порождения новых типов на основе механизма наследования. При определении индивидуальных типов механизм наследования не используется, и поэтому в определении любого индивидуального типа должно присутствовать ключевое слово FINAL. Далее, поскольку индивидуальный тип является частным типом структурного типа, для индивидуального типа можно определять методы.
В своих книгах главный редактор стандартов SQL Джим Мелтон постоянно подчеркивает семантическое сходство понятий индивидуального типа данных и домена в смысле SQL (лекция 15). Более того, утверждается, что в следующих версиях стандарта SQL использование доменов будет сначала объявлено нежелательным, а потом и вовсе будет запрещено. Но я полагаю, что сделать это совсем непросто.
Напомним, что в случае использования SQL-домена: в определении домена указывается базовый встроенный тип данных и, возможно, ограничение допустимых значений, которое распространяется на любой столбец, определенный на данном домене;для значений столбца, определенного на домене, допускаются все операции, разрешенные для базового типа.
Естественно, эти возможности могут использоваться текущими пользователями стандарта SQL. В то же время в случае использования индивидуального типа данных: в определении индивидуального типа указывается только базовый тип данных; если столбец определяется на индивидуальном типе данных, то для него обязательно придется специфицировать собственное ограничение целостности;для значений столбца, определенного на индивидуальном типе данных, не допускаются операции соответствующего базового типа (если не использовать операцию явного приведения типов).
Здесь явно имеются противоречия, для сглаживания которых требуется модифицировать понятие индивидуального типа данных.
Индивидуальный откат транзакции
Для обеспечения возможности индивидуального отката транзакции по общему журналу все записи в журнале от данной транзакции связываются в обратный список. В начале списка для незавершенных транзакций находится запись о последнем изменении базы данных, произведенном данной транзакцией. Заметим, что в этом случае хронологически последние записи могут быть еще не вытолкнуты во внешнюю память журнала и могут находиться в буфере основной памяти. Для закончившихся транзакций (индивидуальные откаты которых уже невозможны) началом списка является запись о конце транзакции, которая обязательно вытолкнута во внешнюю память журнала, т.е. весь список находится во внешней памяти. Концом списка всегда служит первая запись об изменении базы данных, произведенном данной транзакцией. Обычно в каждой записи проставляется уникальный идентификатор транзакции, чтобы можно было восстановить прямой список записей об изменениях базы данных данной транзакцией.
Итак, индивидуальный откат транзакции (еще раз подчеркнем, что это возможно только для незавершенных транзакций) выполняется следующим образом:
Выбирается очередная журнальная запись из списка данной транзакции.
Выполняется противоположная по смыслу операция: вместо операции INSERT
выполняется соответствующая операция DELETE, вместо операции DELETE
выполняется INSERT, и вместо прямой операции UPDATE
– обратная операция UPDATE, восстанавливающая предыдущее состояние объекта базы данных.
Любая из этих обратных операций также журнализуется. Собственно для индивидуального отката это не нужно, но при выполнении индивидуального отката транзакции может произойти мягкий сбой, при восстановлении после которого потребуется откатить транзакции, для которых не полностью выполнен индивидуальный откат.
При успешном завершении отката в журнал заносится запись о конце транзакции. С точки зрения журнала такая транзакция является зафиксированной.
Следует подчеркнуть, что здесь речь идет о логических операциях низкого уровня, т.е. уровня RSS, а не SQL.
Интерфейс RSS
Следует заметить, что описываемый в этом подразделе интерфейс RSS не соответствует в точности ни одной из публикаций, посвященных System R, а является скорее некоторой компиляцией, согласующейся с завершающими публикациями.
На уровне RSS отсутствует именование объектов базы данных, употребляемое на уровне SQL. Вместо имен объектов используются их уникальные идентификаторы, являющиеся прямыми или косвенными адресами внутренних описателей объектов во внешней памяти для постоянных объектов или в основной памяти для временных объектов. Замена имен объектов базы данных на их идентификаторы производится компилятором SQL на основе информации, черпаемой им из системных таблиц-каталогов.
Можно выделить следующие группы операций:
операции сканирования таблиц и списков;
операции создания и уничтожения постоянных и временных объектов базы данных;
операции модификации таблиц и списков;
операция добавления поля к таблице;
операции управления прохождением транзакций;
операция явной синхронизации.
Интерпретация операции ограничения
В лекции 4 мы определяли операцию ограничения r WHERE comp, где r – отношение, а comp – простое условие ограничения вида (a comp-op b), где а и b – имена атрибутов ограничиваемого отношения, для которых осмыслена операция сравнения comp-op, либо вида (a comp-op const), где а – имя атрибута ограничиваемого отношения, а const – литерально заданная константа. Операцией сравнения comp-op может быть «=», «
Для иллюстрации будем использовать отношение СЛУЖАЩИЕ_1 {СЛУ_НОМЕР, СЛУ_ИМЯ, СЛУ_ЗАРП, РУК_НОМ} (). Атрибут РУК_НОМ содержит уникальные номера служащих, являющихся руководителями проектов, и определен на том же домене, что и СЛУ_НОМЕР. Мы снова предположим (для упрощения примеров), что множества значений доменов, на которых определены атрибуты отношения СЛУЖАЩИЕ_1, ограничены значениями, содержащимися в теле этого отношения. Начнем с обсуждения операции WHERE с условием вида a comp-op const.
Предположим, что мы хотим найти всех служащих с заработной платой, равной 20000.00 руб. Возьмем отношение ЗАРП_20000 {СЛУ_ЗАРП}. Мы видим, что результат операции СЛУЖАЩИЕ_1 <AND> ЗАРП_20000 в точности совпадает с результатом операции СЛУЖАЩИЕ_1 WHERE СЛУ_ЗАРП = 20000.00 ().
Рис. 5.8. Выражение WHERE (a = const) через <AND>
Если требуется найти служащих, чья заработная плата превышает 20000.00 руб., то возьмем отношение ЗАРП_БОЛЬШЕ_20000 (). Тогда снова результат операции СЛУЖАЩИЕ_1 <AND> ЗАРП_БОЛЬШЕ_20000.00 будет совпадать с результатом операции СЛУЖАЩИЕ_1 WHERE СЛУ_ЗАРП > 20000.00 ().
Рис. 5.9. Выражение WHERE (a > const) через <AND>
Понятно, что аналогичным образом выражаются через <AND> операции ограничения с условиями вида a comp_op const, в которых comp_op является «<», «
Возьмем отношение ЗАРП_НЕ_22000 (). Результат операции СЛУЖАЩИЕ_1 <AND> ЗАРП_НЕ_22000 будет совпадать с результатом операции СЛУЖАЩИЕ_1 WHERE СЛУ_ЗАРП 22000.00 ().
Рис. 5.10. Выражение WHERE (a
Теперь обратимся к ограничениям с простым условием вида a comp-op b. Опять начнем со случая, когда comp-op = «=». Предположим, что нам требуется найти данные о служащих, являющихся руководителями проектов, т. е. выполнить операцию СЛУЖАЩИЕ_1 WHERE СЛУ_НОМЕР = РУК_НОМ. Утверждается, что результат этой операции совпадает с результатом следующего выражения:
СЛУЖАЩИЕ_1 <AND> ((((СЛУЖАЩИЕ_1 <REMOVE> СЛУ_НОМЕР) <REMOVE> СЛУ_ИМЯ) <REMOVE> СЛУ_ЗАРП) <RENAME> (РУК_НОМ, СЛУ_НОМЕР))
Результат вычисления правого операнда операции <AND> и окончательный результат операции показаны на .
Конечно же, можно выразить операцию СЛУЖАЩИЕ_1 WHERE СЛУ_НОМЕР = РУК_НОМ через операцию <AND>, используя «константное» отношение. Для этого можно воспользоваться отношением СЛУ_НОМЕР_РУК_НОМ, показанным на . Очевидно, что в результате выполнения операции СЛУЖАЩИЕ_1 <AND> СЛУ_НОМЕР_РУК_НОМ будет получен тот же результат, что показан на .
Рис. 5.11. Выражение WHERE (a = b) через <REMOVE>, <RENAME> и <AND>
Чтобы показать возможность выполнения операции ограничения вида r WHERE (a > b), предположим, что имеется отношение СЛУЖАЩИЕ_2 {СЛУ_НОМЕР, СЛУ_ИМЯ, СЛУ_ЗАРП, СЛУ_ПРЕМ} (), причем атрибут СЛУ_ПРЕМ содержит значения премиального вознаграждения служащего. Естественно, атрибуты СЛУ_ЗАРП и СЛУ_ПРЕМ определены на одном и том же домене (напомним, что в целях наших примеров мы предполагаем, что множество значений доменов ограничено значениями, содержащимися в теле примерного отношения). Пусть нас интересуют данные о служащих, получающих дополнительные вознаграждения в размере, превышающем размер основной зарплаты, т. е. нам нужен результат операции СЛУЖАЩИЕ_2 WHERE (СЛУ_ПРЕМ > СЛУ_ЗАРП).
Рис. 5.12. Константное отношение СЛУ_НОМЕР_РУК_НОМ
Возьмем отношение ПРЕМ_БОЛЬШЕ_ЗАРП {СЛУ_ПРЕМ, СЛУ_ЗАРП}, тело которого включает все соответствующие заголовку кортежи {b, s} такие, что b > s. Другими словами, отношение ПРЕМ_БОЛЬШЕ_ЗАРП снова является литеральной константой типа отношения с двумя атрибутами СЛУ_ПРЕМ и СЛУ_ЗАРП. Конечно, даже в случае нашего примера мощность тела этого отношения достаточно велика. Тело отношения ПРЕМ_БОЛЬШЕ_ЗАРП показано в средней части .
Результат выполнения операции СЛУЖАЩИЕ_2 <AND> ПРЕМ_БОЛЬШЕ_ЗАРП показан в нижней части . Мы видим, что он совпадает с результатом операции СЛУЖАЩИЕ_2 WHERE (СЛУ_ПРЕМ > СЛУ_ЗАРП).
Аналогичным образом через операции Алгебры A выражаются операции ограничения, условия сравнения которых вида a comp_op b базируются на операциях сравнения «<», «
Рис. 5.13. Выражение WHERE (a > b) через <AND>
Инвариант класса
Под инвариантом класса в OCL понимается условие, которому должны удовлетворять все объекты данного класса. Если говорить более точно, инвариант класса – это логическое выражение, вычисление которого должно давать true при создании любого объекта данного класса и сохранять истинное значение в течение всего времени существования этого объекта. При определении инварианта требуется указать имя класса и выражение, определяющее инвариант указанного класса. Синтаксически это выглядит следующим образом:
context <class_name> inv: <OCL-выражение>
Здесь <class-name> является именем класса, для которого определяется инвариант, inv – ключевое слово, говорящее о том, что определяется именно инвариант, а не ограничение другого вида, и context – ключевое слово, которое говорит о том, что контекстом следующего после двоеточия OCL-выражения являются объекты класса <class-name>, т. е. OCL-выражение должно принимать значение true для всех объектов этого класса.
Заметим, что OCL является типизированным языком, поэтому у каждого выражения имеется некоторый тип. Естественно, что OCL-выражение в инварианте класса должно быть логического типа.
В общем случае OCL-выражение в определении инварианта основывается на композиции операций, которым посвящена большая часть определения языка. В спецификации языка эти операции условно разделены на следующие группы: операции над значениями предопределенных в UML (скалярных) типов данных;операции над объектами; операции над множествами;операции над мультимножествами;операции над последовательностями.
Последовательно обсудим эти группы операций.
Исчисление доменов
В исчислении доменов областью определения переменных являются не отношения, а домены. Применительно к базе данных СЛУЖАЩИЕ-ПРОЕКТЫ можно говорить, например, о доменных переменных ИМЯ (значения – допустимые имена) или НОСЛУ (значения – допустимые номера служащих).
Исчисление кортежей
Для определения кортежной переменной используется оператор RANGE. Например, для того чтобы определить переменную СЛУЖАЩИЙ, областью определения которой является отношение СЛУЖАЩИЕ, нужно употребить конструкцию
RANGE СЛУЖАЩИЙ IS СЛУЖАЩИЕ
Как уже говорилось, из этого определения следует, что в любой момент времени переменная СЛУЖАЩИЙ представляет некоторый кортеж отношения СЛУЖАЩИЕ. При использовании кортежных переменных в формулах можно ссылаться на значение атрибута переменной (это аналогично тому, как, например, при программировании на языке C можно сослаться на значение поля структурной переменной). Например, для того, чтобы сослаться на значение атрибута СЛУ_ИМЯ переменной СЛУЖАЩИЙ, нужно употребить конструкцию СЛУЖАЩИЙ.СЛУ_ИМЯ.
Используемая терминология
Несмотря на то, что при реализации System R использовался подход, несколько отличающийся от реляционного подхода Кодда (отсюда и пошли расхождения между реляционной моделью данных и моделью данных SQL), мы будем активно пользоваться терминами реляционной модели. К таким терминам относятся названия реляционных операций – ограничение, проекция, соединение; названия теоретико-множественных операций – объединение, пересечение, взятие разности и т.д.
В тех случаях, когда терминология System R расходится с реляционной терминологией, предпочтение будет отдаваться терминологии System R. В частности, это касается использования термина «поле таблицы» вместо термина «атрибут отношения». В самой System R при переходе к коммерческим системам также произошла некоторая смена терминологии. В частности, появилась тенденция к употреблению терминов, более привычных в среде пользователей IBM: файл, запись и т.д. Здесь будут использоваться термины System R, более близкие реляционным системам. Опишем некоторые основные термины System R, опираясь в основном не на теоретические соображения, а на практические аспекты соответствующих понятий.
Базовым понятием System R является понятие таблицы
(приближенный к реализации аналог основного понятия реляционного подхода отношения; иногда, в зависимости от контекста, мы будем использовать и этот термин). Таблица – это регулярная структура данных, состоящая из конечного набора однотипных записей – кортежей. Каждый кортеж одной таблицы состоит из конечного (и одинакового) числа полей кортежа, причем i-тое поле каждого кортежа одной таблицы может содержать данные только одного типа, и набор допустимых типов данных в System R предопределен и фиксирован.
В силу регулярности структуры таблицы понятие поля кортежа расширяется до понятия поля таблицы. Тогда i-тое поле таблицы можно трактовать как набор одноместных кортежей, полученных выборкой i-тых полей из каждого кортежа этой таблицы, т.е. в общепринятой терминологии как проекцию таблицы на i-тый атрибут.
В терминологию System R не входит понятие домена, оно заменяется здесь понятием типа поля, т.е. типом данных, хранение которых в данном поле допускается (это не вполне эквивалентная замена, но такова реальность System R).
Таблицы, составляющие базу данных System R, могут физически храниться в одном или нескольких сегментах, каждому из которых соответствует отдельный файл внешней памяти. Сегменты разбиваются на страницы, в которых располагаются кортежи таблиц и вспомогательные служебные структуры данных – индексы. Соответственно, каждый сегмент содержит две группы страниц – страницы данных и страницы индексной информации. Страницы каждой группы имеют фиксированный размер, но страницы с индексной информацией меньше по размеру, чем страницы данных. В страницах данных могут располагаться кортежи более чем одной таблицы (это очень важное свойство физической организации баз данных System R; следующие из этой организации преимущества разъясним позже).
Этим, конечно, не исчерпывается набор понятий System R, но остальные термины мы будем пояснять по ходу изложения, поскольку для этого требуется соответствующий понятийный контекст.
Истинная реляционная модель
Дейт и Дарвен очень подробно и тщательно разработали предлагаемый ими вариант реляционной модели данных. В последнем издании книги , изданном в крупном формате, около 600 страниц, причем это очень насыщенный текст. Поэтому в кратком очерке истинной реляционной модели, предлагаемом в этом разделе, мы можем описать только ее самые общие и внешние черты. За подробностями отсылаю читателей к .
Истинно целые типы
Тип INTEGER служит для представления целых чисел. Точность чисел (число сохраняемых бит) определяется в реализации. При определении столбца данного типа достаточно указать просто INTEGER.Тип SMALLINT также служит для представления целых чисел. Точность определяется в реализации, но она не должна быть больше точности типа INTEGER. При определении столбца указывается просто SMALLINT.Литералы типов целых чисел представляются в виде строк символов, изображающих десятичные числа; в начале строки могут присутствовать символы «+» или «-» (если символ знака отсутствует, подразумевается «+»). Примеры литералов типов INTEGER и SMALLINT: 1826545, 876.
Истоки и краткая история объектно-реляционных баз данных
Пальму первенства в области объектно-реляционных систем управления базами данных (ОРСУБД) оспаривают два весьма известных специалиста в области технологии баз данных – Майкл Стоунбрейкер (Michael Stonebraker) и Вон Ким (Won Kim).
Исторический очерк
Завершим обсуждение возможностей применения операций обновления к виртуальным таблицам небольшим экскурсом в историю. На протяжении более чем тридцатилетней истории реляционных баз данных вопрос о возможности однозначной интерпретации операций обновления баз данных через виртуальные таблицы интересовал многих исследователей. Причины этого интереса состоят в следующем.
Во-первых, как отмечалось в лекции 4, одной из наиболее привлекательных черт реляционной алгебры является замкнутость относительно понятия отношения. В любой алгебраической операции, операндом которой является отношение, в качестве операнда можно использовать алгебраическое выражение. С другой стороны, имеется явное неравноправие по отношению к операциям обновления. Мы можем вставлять, модифицировать и удалять кортежи в базовых отношениях, но не можем (в общем случае) применять эти операции к алгебраическим выражениям. Хотелось максимальным образом устранить подобное неравноправие.
Во-вторых, на первый взгляд задача не является слишком трудной (по крайней мере, если оставаться в пределах реляционной алгебры). Действительно, базовых операций совсем немного, и каждая базовая операция очень проста.
К сожалению, это ощущение простоты проблемы оказалось обманчивым. Было выполнено множество исследований, опубликовано множество статей (нам кажется нецелесообразным приводить список этих статей в данном курсе), но так и не удалось обнаружить полное множество алгебраических выражений, для которых возможна однозначная интерпретация операций обновления. На мой взгляд, данная ситуация оказала заметное влияние на подход к решению проблемы применимости операций обновления к виртуальным таблицам, которым руководствуются разработчики языка SQL.
В двух первых международных стандартах (SQL/89 и SQL/92) к виду таких виртуальных таблиц предъявлялись чрезмерно строгие требования. Это показывают даже те простые примеры, которые приводились в начале данного раздела. И конечно, наличие таких ограничений в стандарте языка приводило к тому, что в реализациях SQL появлялось много расширений, которые поддерживались только отдельными компаниями-производителями СУБД.
Создается впечатление, что когда более десяти лет назад был инициирован проект нового стандарта SQL-3 (который в конце концов привел к появлению SQL:1999), разработчики находились в состоянии растерянности.
Кстати, одна из идей, включавшихся в ранние варианты проекта SQL-3, состояла в том, чтобы расширить определение представляемой таблицы средствами, позволяющими явно специфицировать действия, которые нужно предпринимать при выполнении над представлением операций INSERT, UPDATE и DELETE. Другими словами, предлагалось переложить решение проблемы на плечи пользователей СУБД. Конечно, это радикальный подход, но, с другой стороны, он мог бы привести к полной анархии.
Как можно заметить, в официально принятом стандарте SQL:1999 используется некоторый компромиссный подход. В стандарте не фиксируются жесткие правила, ограничивающие вид виртуальных таблиц, к которым применимы операции обновления. Вместо этого сформулирован ряд рекомендаций, которыми следует руководствоваться производителям СУБД. Нельзя утверждать, что такое решение является идеальным, но более удачного решения найти не удалось.
Будем считать, что тем, кто пользуется представлением MORE_RICH_EMP, неизвестно ограничение EMP_SAL < 20000.00, на котором основывается представление MIDDLE_RICH_EMP.
Избыточность Алгебры A
В формальной математической логике стандартным базисом для выражения всех возможных булевских функций является набор {NOT, AND, OR} (отрицание, дизъюнкция и конъюнкция). Известно, что этот набор традиционен, но избыточен, поскольку верны тождества A AND B
Избыточность операции переименования
Наконец, покажем, что избыточна и операция <RENAME>. Для иллюстрации снова воспользуемся отношением СЛУЖАЩИЕ из . Пусть нам нужен результат операции СЛУЖАЩИЕ <RENAME> (ПРО_НОМ, НОМЕР_ПРОЕКТА) (мы по-прежнему предполагаем, что множество значений домена атрибута ПРО_НОМ ограничено значениями, представленными в теле отношения СЛУЖАЩИЕ). Возьмем бинарное отношение ПРО_НОМ_НОМЕР_ПРОЕКТА (), где каждый из кортежей содержит два одинаковых значения номера проекта и в тело отношения входят все значения домена атрибута ПРО_НОМ. Тогда, как показано на , вычисление выражения (СЛУЖАЩИЕ <AND> ПРО_НОМ_НОМЕР_ПРОЕКТА) <REMOVE> (ПРО_НОМ) приводит к желаемому результату.
Рис. 5.15. Избыточность операции <RENAME>
Тем самым, можно сократить набор операций Алгебры A до двух операций: <sh> (или <pi>) и <REMOVE>.
Изменение набора табличных ограничений
Действие по изменению набора табличных ограничений специфицируется в следующем синтаксисе:
base_table_constraint_alternation_action ::= ADD [ CONSTRAINT ] base_table_constraint_definition | DROP CONSTRAINT constraint_name { RESTRICT | CASCADE }
Действие ADD [ CONSTRAINT ] позволяет добавить к набору существующих ограничений таблицы новое ограничение целостности. Можно считать, что новое ограничение добавляется через AND к конъюнкции существующих ограничений, как если бы оно определялось в составе оператора CREATE TABLE. Но здесь имеется одно существенное отличие. Если внимательно посмотреть на все возможные виды табличных ограничений, можно убедиться, что любое из них удовлетворяется на пустой таблице. Поэтому, какой бы набор табличных ограничений ни был определен при создании таблицы, это определение является допустимым и не препятствует выполнению оператора CREATE TABLE. При добавлении нового табличного ограничения с использованием действия ADD [ CONSTRAINT ] мы имеем другую ситуацию, поскольку таблица, скорее всего, уже содержит некоторый набор строк, для которого условное выражение нового ограничения может принять значение false. В этом случае выполнение оператора ALTER TABLE, включающего действие ADD [ CONSTRAINT ], отвергается.
Выполнение действия DROP CONSTRAINT приводит к отмене определения существующего табличного ограничения. Можно отменить определение только именованных табличных ограничений. Спецификации RESTRICT и CASCADE осмыслены только в том случае, если отменяемое ограничение является ограничением возможного ключа (UNIQUE или PRIMARY KEY). При указании RESTRICT действие отвергается, если на данный возможный ключ ссылается хотя бы один внешний ключ. При указании CASCADE действие DROP CONSTRAINT выполняется в любом случае, и все определения таких внешних ключей также отменяются.
Изменение определения базовой таблицы
Оператор изменения определения базовой таблицы ALTER TABLE имеет следующий синтаксис:
base_table_alteration ::= ALTER TABLE base_table_name column_alteration_action | base_table_constraint_alternation_action
Как видно из этого синтаксического правила, при выполнении одного оператора ALTER TABLE может быть выполнено либо действие по изменению определения столбца, либо действие по изменению определения табличного ограничения целостности.
Изменение определения домена
Для изменения характеристик ранее определенного домена используется оператор SQL ALTER DOMAIN. Синтаксис этого оператора выглядит следующим образом:
domain_alternation ::= ALTER DOMAIN domain_name domain_alternation_action domain_alternation_action ::= domain_default_alternation_action | domain_constraint_alternation_action
Как видно из синтаксических правил, при изменении определения домена можно выполнить действие по изменению раздела значения по умолчанию либо изменить ограничение домена. Для первого варианта действует следующий синтаксис:
domain_default_alternation_action ::= SET default_definition | DROP DEFAULT
В случае установки нового значения по умолчанию (SET) это значение автоматически применяется ко всем столбцам, определенным на данном домене. Более точно, это значение становится новым значением по умолчанию. Операция не оказывает влияния на состояние существующих строк таблиц базы данных. В случае отмены раздела значения по умолчанию в определении домена (DROP) существовашее значение домена по умолчанию становится значением по умолчанию каждого столбца, который определен на данном домене и для которого не специфицировано собственное значение по умолчанию.
Действие по изменению ограничения домена определяется следующим синтаксисом:
domain_constraint_alternation_action ::= ADD domain_constraint_definition | DROP CONSTRAINT constraint_name
Действие по добавлению нового определения ограничения домена (ADD) приводит к тому, что новое условие добавляется через AND к существующему ограничению домена. Если к моменту выполнения соответствующего оператора ALTER DOMAIN существуют столбцы некоторых таблиц, текущие значения которых противоречат новому ограничению, то СУБД должна отвергнуть этот оператор ALTER DOMAIN. Действие по отмене ограничения домена (DROP) приводит к исчезновению соответствующей части общего ограничения соответствующего домена, что, естественно, не влияет на существующие значения столбцов имеющихся таблиц.
Изменение текущих идентификаторов пользователей и имен ролей
Как мы отмечали ранее в этом разделе, в SQL:1999 специфицированы некоторые операторы, позволяющие изменять текущий идентификатор пользователя и текущее имя роли SQL-сессии.
Изолированность транзакций
В многопользовательских системах с одной базой данных одновременно может работать несколько пользователей или прикладных программ. Предельной задачей системы является обеспечение изолированности пользователей, т.е. создание достоверной и надежной иллюзии того, что каждый из пользователей работает с базой данных в одиночку.
В связи со свойством сохранения целостности базы данных транзакции являются подходящими единицами изолированности пользователей. Действительно, если с каждым сеансом работы пользователя или приложений с базой данных ассоциируется транзакция, то каждый пользователь начинает работу с согласованным состоянием базы данных, т.е. с таким состоянием, в котором база данных могла бы находиться, даже если бы пользователь работал с ней в одиночку.
При соблюдении обязательного требования поддержки целостности базы данных возможно наличие нескольких уровней изолированности транзакций. Заметим, что впервые эти уровни изолированности транзакций были установлены и описаны участниками проекта System R.
Явная инициация транзакции
Для явного образования транзакции поддерживается оператор START TRANSACTION, определяемый следующими синтаксическими правилами:
START TRANSACTION mode_commalist
Этот оператор очень похож на SET TRANSACTION. Единственное (хотя и очень существенное) отличие состоит в том, что выполнение оператора START TRANSACTION приводит не только к установке характеристик транзакции, но и к реальной инициации транзакции.
Явные преобразования типов или доменов и оператор CAST
Неявные преобразования типов не всегда удобны, недостаточно гибки и иногда могут вызывать ошибки. Поэтому, как показывает предыдущий подраздел, число допустимых неявных преобразований типов в SQL весьма ограничено. Однако в SQL существует специальный оператор CAST, с помощью которого можно явно преобразовывать типы или домены в более широких пределах допускаемых преобразований. Конструкция имеет следующий синтаксис:
CAST ({scalar-expression | NULL } AS {data_type | domain_name})
Оператор преобразует значение заданного скалярного выражения к указанному типу или к базовому типу указанного домена. Результатом применения оператора CAST к неопределенному значению является неопределенное значение. Для значений, отличных от неопределенных, в стандарте приводятся подробные правила выполнения преобразований, которые интуитивно понятны.
Поясним действие оператора CAST в наиболее важных случаях. Примем следующие обозначения типов данных:
EN – точные числовые типы (Exact Numeric)
AN – приблизительные числовые типы (Approximate Numeric)
C – типы символьных строк (Character)
FC – типы символьных строк постоянной длины (Fixed-length Character)
VC – типы символьных строк переменной длины (Variable-length Character)
B – типы битовых строк (Bit String)
FB – типы битовых строк постоянной длины (Fixed-length Bit String)
VB – типы битовых строк переменной длины (Variable-length Bit String)
D – тип Date
T – типы Time
TS – типы Timestamp
YM – типы Interval Year-Month
DT – типы Interval Day-Time
Пусть TD – это тип данных, к которому производится преобразование, а SD – тип данных операнда. Тогда допустимы следующие комбинации («да» означает безусловную допустимость, «нет» – безусловную недопустимость и «?» – допустимость с оговорками).
| Да | Да | Да | Да | Нет | Нет | Нет | Нет | Нет | ? | ? |
| Да | Да | Да | Да | Нет | Нет | Нет | Нет | Нет | Нет | Нет |
| Да | Да | ? | ? | Да | Да | Да | Да | Да | Да | Да |
| Нет | Нет | Да | Да | Да | Да | Нет | Нет | Нет | Нет | Нет |
| Нет | Нет | Да | Да | Нет | Нет | Да | Нет | Да | Нет | Нет |
| Нет | Нет | Да | Да | Нет | Нет | Нет | Да | Да | Нет | Нет |
| Нет | Нет | Да | Да | Нет | Нет | Да | Да | Да | Нет | Нет |
| ? | Нет | Да | Да | Нет | Нет | Нет | Нет | Нет | Да | Нет |
| ? | Нет | Да | Да | Нет | Нет | Нет | Нет | Нет | Нет | Да |
По поводу ячеек таблицы, содержащих знак вопроса, необходимо сделать несколько оговорок: если TD – интервал и SD – тип точных чисел, то TD должен содержать единственное поле даты-времени; если TD – тип точных чисел и SD – интервал, то SD должен содержать единственное поле даты-времени; если SD – тип символьных строк и TD – тип символьных строк постоянной или переменной длины, то набор символов SD и TD должен быть одним и тем же.
Языки запросов
Но обеспечение целостности данных – это далеко не все, что обычно требуется от СУБД. Начнем с того, что даже в нашем примере пользователю информационной системы будет не слишком просто получить, например, общую численность отдела, в котором работает Петр Иванович Сидоров. Придется сначала узнать номер отдела, в котором работает указанный служащий, а затем установить численность этого отдела. Было бы гораздо проще, если бы СУБД позволяла сформулировать такой запрос на языке, более близком пользователям. Такие языки называются языками запросов к базам данных. Например, на языке запросов SQL наш запрос можно было бы выразить в следующей форме (запрос1):
SELECT ОТД_РАЗМЕР FROM СЛУЖАЩИЕ, ОТДЕЛЫ WHERE СЛУ_ИМЯ = 'ПЕТР ИВАНОВИЧ СИДОРОВ' AND СЛУ_ОТД_НОМЕР = ОТД_НОМЕР;
Это пример запроса на языке SQL с полусоединением: c одной стороны, запрос адресуется к двум файлам – СЛУЖАЩИЕ и ОТДЕЛЫ, но с другой стороны, данные выбираются только из файла ОТДЕЛЫ. Условие СЛУ_ОТД_НОМЕР = ОТД_НОМЕР всего лишь «ограничивает» интересующий нас набор записей об отделах до одной записи, если Петр Иванович Сидоров действительно работает на данном предприятии. Если же Петр Иванович Сидоров не работает на предприятии, то условие СЛУ_ИМЯ = 'ПЕТР ИВАНОВИЧ СИДОРОВ' не будет удовлетворяться ни для одной записи файла СЛУЖАЩИЕ, и поэтому запрос выдаст пустой результат.
Возможна и другая формулировка того же запроса (запрос2):
SELECT ОТД_РАЗМЕР FROM ОТДЕЛЫ WHERE ОТД_НОМЕР = (SELECT СЛУ_ОТД_НОМЕР FROM СЛУЖАЩИЕ WHERE СЛУ_ИМЯ = 'ПЕТР ИВАНОВИЧ СИДОРОВ');
Это пример запроса на языке SQL с вложенным подзапросом. Во вложенном подзапросе выбирается значение поля СЛУ_ОТД_НОМЕР из записи файла СЛУЖАЩИЕ, в которой значение поля СЛУ_ИМЯ равняется строковой константе 'ПЕТР ИВАНОВИЧ СИДОРОВ'. Если такая запись существует, то она единственная, поскольку поле СЛУ_ИМЯ является уникальным ключом файла СЛУЖАЩИЕ. Тогда результатом выполнения подзапроса будет единственное значение – номер отдела, в котором работает Петр Иванович Сидоров.
Во внешнем запросе это значение будет ключом доступа к файлу ОТДЕЛЫ, и снова будет выбрана только одна запись, поскольку поле ОТД_НОМЕР является уникальным ключом файла ОТДЕЛЫ. Если же на данном предприятии Петр Иванович Сидоров не работает, то подзапрос выдаст пустой результат, и внешний запрос тоже выдаст пустой результат.
Приведенные примеры показывают, что при формулировке запроса с использованием SQL можно не задумываться о том, как будет выполняться этот запрос. Среди метаданных базы данных будет содержаться информация о том, что поле СЛУ_ИМЯ является ключевым для файла СЛУЖАЩИЕ (т. е. по заданному значению имени служащего можно быстро найти соответствующую запись или убедиться в том, что запись с таким значением поля СЛУ_ИМЯ в файле отсутствует), а поле ОТД_НОМЕР – ключевое для файла ОТДЕЛЫ (и более того, оба ключа в соответствующих файлах являются уникальными), и система сама воспользуется этим. Можно формально доказать, что формулировки запрос1 и запрос2 эквивалентны, т. е. вне зависимости от состояния данных всегда производят один и тот же результат. Наиболее вероятным способом выполнения запроса в обеих формулировках будет выборка записи из файла СЛУЖАЩИЕ со значением поля СЛУ_ИМЯ, равным строке 'ПЕТР ИВАНОВИЧ СИДОРОВ', взятие из этой записи значения поля СЛУ_ОТД_НОМЕР и выборка из таблицы ОТДЕЛЫ записи с таким же значением поля ОТД_НОМ.
Если же, например, возникнет потребность в получении списка служащих, не соответствующих занимаемой должности, то достаточно обратиться к системе с запросом (запрос3):
SELECT СЛУ_ИМЯ, СЛУ_НОМЕР FROM СЛУЖАЩИЕ WHERE СЛУ_СТАТ = "НЕТ";
и система сама выполнит необходимый полный просмотр файла СЛУЖАЩИЕ, поскольку поле СЛУ_СТАТ не является ключевым, и другого способа выполнения не существует.
Категории связей. Связь-зависимость
В диаграмме классов могут участвовать связи трех разных категорий: зависимость (dependency), обобщение (generalization) и ассоциация (association). При проектировании реляционных БД наиболее важны вторая и третья категории связей, поэтому о связях-зависимостях будет сказано только самое основное.
Зависимостью называют связь по применению, когда изменение в спецификации одного класса может повлиять на поведение другого класса, использующего первый класс. Чаще всего зависимости применяют в диаграммах классов, чтобы отразить в сигнатуре операции одного класса тот факт, что параметром этой операции могут быть объекты другого класса. Понятно, что если интерфейс второго класса изменяется, это влияет на поведение объектов первого класса. Простой пример диаграммы классов со связью-зависимостью показан на .
Рис. 11.4. Диаграмма классов со связью-зависимостью
Зависимость показывается прерывистой линией со стрелкой, направленной к классу, от которого имеется зависимость. Очевидно, что связи-зависимости существенны для объектно-ориентированных систем (в том числе и для ООБД). При проектировании реляционных БД непонятно, что делать с зависимостями (как воспользоваться этой информацией в реляционной БД?).
Классические статьи в русских переводах.
2.1. Э.Ф. Кодд. Реляционная модель данных для больших совместно используемых банков данных. СУБД № 1 1995 г.
Первое широко доступное описание исходной реляционной модели, сделанное ее изобретателем.
2.2. Э.Ф. Кодд. Расширение реляционной модели для лучшего отражения семантики. СУБД, N 5, 1996 г.
2.3. М. М. Злуф. Query-by-Example: язык баз данных. СУБД, N 3, 1996 г.
2.4. Чен П.П. Модель “сущность-связь” – шаг к единому представлению данных. СУБД, N 3, 1995 г.
Я очень рекомендую прочитать эту классическую статью, изданную впервые в 1976 г. Мне кажется, что она во многом проясняет процесс развития семантических диаграммных моделей.
2.5. Д.Д. Чамберлин, М.М.Астрахан, К.П.Эсваран, П.П.Грифитс, Р.А.Лори, Д.В.Мел, П.Райшер, Б.В.Вейд. SEQUEL 2: унифицированный подход к определению, манипулированию и контролю данных. СУБД No. 1, 1996.
2.6. М. Аткинсон и др. Манифест систем объектно-ориентированных баз данных, СУБД, No. 4, 1995
2.7. Стоунбрейкер М. и др. Системы баз данных третьего поколения: манифест”, СУБД, No. 2, 1995,
2.8. Х. Дарвин, К. Дейт. Третий манифест, СУБД, No. 1, 1996
Это один из ранних вариантов (хотя и не самый ранний вариант) Третьего манифеста. Насколько я помню, эта статья не произвела большого впечатления. Тогда мы еще наблюдали большой энтузиазм относительно системы объектно-ориентированных баз данных. Казалось, что они действительно смогут заменить системы реляционных баз данных.
2.9. Д. Чемберлин. “Анатомия объектно-реляционных баз данных”, СУБД, No. 1-2, 1998
Классы, атрибуты, операции
Классом называется именованное описание совокупности объектов с общими атрибутами, операциями, связями и семантикой. Графически класс изображается в виде прямоугольника. У каждого класса должно быть имя (текстовая строка), уникально отличающее его от всех других классов. При формировании имен классов в UML допускается использование произвольной комбинации букв, цифр и даже знаков препинания. Однако на практике рекомендуется использовать в качестве имен классов короткие и осмысленные прилагательные и существительные, каждое из которых начинается с заглавной буквы. Примеры описания классов показаны на .
Рис. 11.1. Примеры описания классов
Атрибутом класса называется именованное свойство класса, описывающее множество значений, которые могут принимать экземпляры этого свойства. Класс может иметь любое число атрибутов (в частности, не иметь ни одного атрибута). Свойство, выражаемое атрибутом, является свойством моделируемой сущности, общим для всех объектов данного класса. Так что атрибут является абстракцией состояния объекта. Любой атрибут любого объекта класса должен иметь некоторое значение.
Имена атрибутов представляются в разделе класса, расположенном под именем класса. Хотя UML не накладывает ограничений на способы создания имен атрибутов (имя атрибута может быть произвольной текстовой строкой), на практике рекомендуется использовать короткие прилагательные и существительные, отражающие смысл соответствующего свойства класса. Первое слово в имени атрибута рекомендуется писать с прописной буквы, а все остальные слова – с заглавной. Пример описания класса с указанными атрибутами показан на .
Рис. 11.2. Класс Человек с указанными именами атрибутов
Операцией класса называется именованная услуга, которую можно запросить у любого объекта этого класса. Операция – это абстракция того, что можно делать с объектом. Класс может содержать любое число операций (в частности, не содержать ни одной операции). Набор операций класса является общим для всех объектов данного класса.
Операции класса определяются в разделе, расположенном ниже раздела с атрибутами. При этом можно ограничиться только указанием имен операций, оставив детальную спецификацию выполнения операций на более поздние этапы моделирования. Для именования операций рекомендуется использовать глагольные формы, соответствующие ожидаемому поведению объектов данного класса. Описание операции может также содержать ее сигнатуру, т. е. имена и типы всех параметров, а если операция является функцией, то и тип ее значения. Класс Человек с определенными операциями показан на .
Рис. 11.3. Класс Человек с операциями
Для класса Человек мы определили три операции: выдатьВозраст, сохранитьТекущийДоход, выдатьОбщийДоход. В операции выдатьВозраст используются значение атрибута датаРождения и значение текущей даты. Операция сохранитьТекущийДоход позволяет зафиксировать в состоянии объекта сумму и дату поступления дохода данного человека. Операция выдатьОбщийДоход выдает суммарный доход данного человека за указанное время. Заметим, что состояние объекта меняется при выполнении только второй операции. Результаты первой и третьей операций формируются на основе текущего состояния объекта.
Книги на русском языке:
1.1. К. Дейт. Введение в системы баз данных. 2-е изд., М.: Наука.1980.-
1.2. К. Дейт. Введение в системы баз данных. 6-е изд., М.; СПб.: Вильямс.- 2000.
Обратите внимание, что я не рекомендую читать в связи с введением в реляционную модель данных седьмое издание этой книги Дейта, вышедшее на русском языке в издательстве «Вильямс» в 2001 г. По моему мнению, лучше всего реляционная модель была представлена в четвертом и пятом изданиях, которые на русском языке не издавались. Седьмое же издание мне менее всего нравится с методической точки зрения. В этих книгах Кристофера Дейта можно найти варианты реляционной алгебры, отличные от изложенных в данном курсе. Для полноты картины этот материал стоит изучить.
1.3. К. Дейт. Введение в системы баз данных. 7-е изд., М.; СПб.: Вильямс.- 2001; – 8-е изд. – М.; СПб.: Вильямс, 2005
Пожалуй, материалы по поводу проектирования реляционных баз данных путем нормализации лучше всего изложены Дейтом именно в седьмом и восьмом изданиях его основной книги. С моей точки зрения, он слишком сильно оценивает “научность” и строгость этой дисциплины, но это несущественно. Кроме того, при чтении соответствующих глав книги не следует обращать внимания на некоторые особенности изложения, проистекающие из Третьего манифеста, как и на погрешности перевода (в восьмом издании их почти нет).
1.4. К. Дейт. Руководство по реляционной системе DB2. М.: Финансы и статистика. 1988
С моей точки зрения, это очень хорошая книга. Она переведена М.Р. Когаловским. Было очень интересно проследить, как идеи System R реализовались в полноценном коммерческом продукте. Кроме того, тогда было странно, что компания IBM отказалась от некоторых удачных идей (например, тогда в DB2 не поддерживались триггеры).
1.5. [4] К. Дейт, Хью Дарвен. Основы будущих систем баз данных. Третий манифест. М: Янус-К, 2004.
Авторы считают эту книгу просто изложением реляционной модели данных в современном понимании. Скромно замечу, что мне выпала честь переводить и редактировать перевод этой книги.
1.6. Д. Мейер. Теория реляционных баз данных. М., Мир, 1987.
Это единственная переведенная на русский язык книга, целиком посвященная теоретическим вопросам проектирования реляционных баз данных. Я не слишком рекомендую читать эту книгу сразу целиком (если, конечно, удастся ее найти), поскольку написана она достаточно сумбурно, но просмотреть ее полезно. Это позволит оценить стиль типичного теоретика баз данных и уровень сложности теории.
1.7. Вендров А.М. CASE-технологии. Современные методы и средства проектирования информационных систем. М., Финансы и статистика, 1998.
1.8. Вендров А.М. Проектирование программного обеспечения экономических информационных систем. М., Финансы и статистика, 2000.
В книгах А.М. Вендрова дается широкий обзор современных технологий проектирования информационных систем. Автор руководствуется собственным практическим опытом, и в его изложении сглаживаются терминологические и концессионные барьеры между разными подходами. Кроме того, эти книги изначально написаны на русском языке, а не переведены с английского, поэтому читаются без затруднений.
1.9. Фаулер М., Скотт К. UML в кратком изложении. Применение стандартного языка объектного моделирования. М., Мир, 1999.
Многие мои коллеги считают, что это лучшая книга про UML, переведенная на русский язык. Она написана четко, без повторов и философских отклонений от темы. Конечно, книга не может улучшить язык, но она помогает понять его в том виде, в каком он существует. Кстати, переводил книгу А.М. Вендров.
1.10. Буч Г Объектно-ориентированный анализ и проектирование с примерами приложений на C++. 2-е изд. М., Издательство Бином, СПб., Невский диалект, 1999.
1.11. Буч Г., Рамбо Д., Джекобсон А. Язык UML: руководство пользователя. М., ДМК, 2000.
Было бы просто неприлично не предложить в качестве дополнительной литературы по UML книги отцов-основателей этого языка. Хотя, честно говоря, я не в восторге от этих книг (как в русском переводе, так и на языке оригинала). Конечно, каждая книга полностью соответствует своему названию, но почему-то эти книги очень трудно и скучно читаются подряд, и в них очень трудно отыскать конкретную информацию.
1.12. М.Р. Когаловский. Энциклопедия технологий баз данных. М. Финансы и статистика, 2002.
Одна из немногих книг, которые полезно всегда иметь под рукой специалистам в области баз данных.
1.13. Гектор Гарсиа-Молина, Джеффри Ульман, Дженифер Уидом. Системы баз данных. Полный курс. Москва, Санкт-Петербург, Киев, Вильямс, 2003.
Это действительно полный курс. Во многих университетах мира именно по этой книге читаются курсы по тематике баз данных.
1.14. С.Д. Кузнецов. Базы данных: языки и модели. Москва, Бином, 2008
1.15. С.Д. Кузнецов. Основы баз данных. 2-е изд. Москва, Бином, 2007
Конструкторы значения строки и таблицы
Чтобы завершить обсуждение выражений запросов (с учетом того, что конструкция соединенных таблиц (joined_table) отложена на лекцию 19), нам осталось рассмотреть конструкции table_value_constructor и TABLE table_name.
В определении конструктора значения-таблицы используется конструктор значения-строки, который строит упорядоченный набор скалярных значений, представляющий строку (возможно и использование подзапроса):
row_value_constructor ::= row_value_constructor_element | [ ROW ] (row_value_constructor_element_comma_list) | row_subquery row_value_constructor_element ::= value_expression | NULL | DEFAULT
Заметим, что значение элемента по умолчанию можно использовать только в том случае, когда конструктор значения-строки применяется в операторе INSERT (тогда этим значением будет значение по умолчанию соответствующего столбца).
Конструктор значения-таблицы производит таблицу на основе заданного набора конструкторов значений-строк:
table_value_constructor ::= VALUES row_value_constructor_comma_list
Конечно, для того чтобы корректно построить таблицу, требуется, чтобы строки, производимые всеми конструкторами строк, были одной и той же степени и чтобы типы (или домены) соответствующих столбцов являлись приводимыми.
Наконец, конструкция TABLE table_name является сокращенной формой записи выражения SELECT * FROM table_name.
Корректные и некорректные декомпозиции отношений. Теорема Хита
На приведены две возможные декомпозиции отношения СЛУЖАЩИЕ_ПРОЕКТЫ (для экономии места мы сократили и слегка изменили тело отношения из ).
Рис. 7.3. Две возможные декомпозиции отношения СЛУЖАЩИЕ_ПРОЕКТЫ
Анализ показывает, что в случае декомпозиции (1) мы не потеряли информацию о служащих – про каждого из них можно узнать имя, размер зарплаты, номер выполняемого проекта и имя руководителя проекта. Вторая декомпозиция не дает возможности получить данные о проекте служащего, поскольку Иванов и Иваненко получают одинаковую зарплату, следовательно, эта декомпозиция приводит к потере информации. Что же привело к тому, что одна декомпозиция является декомпозицией без потерь, а вторая – нет?
Заметим, что при проведении декомпозиции мы использовали операцию взятия проекции. Каждое из отношений СЛУЖ, СЛУ_ПРО и ЗАРП_ПРО является проекцией исходного отношения СЛУЖАЩИЕ_ПРОЕКТЫ. В случае декомпозиции (1) отсутствие потери информации означает, что в результате естественного соединения отношений СЛУЖ и СЛУ_ПРО мы гарантированно получим отношение, заголовок и тело которого совпадают с заголовком и телом отношения СЛУЖАЩИЕ_ПРОЕКТЫ. Следует отметить, что это произойдет для любых допустимых (и согласованных) значений переменных отношений СЛУЖАЩИЕ_ПРОЕКТЫ, СЛУЖ и СЛУ_ПРО, поскольку у всех этих переменных атрибут СЛУ_НОМ является возможным ключом. Однако если выполнить естественное соединение отношений СЛУ и ЗАРП_ПРО, то будет получено отношение, показанное на .
Схема этого отношения, естественно (поскольку соединение – естественное), совпадает со схемой отношения СЛУЖАЩИЕ_ПРОЕКТЫ, но в теле появились лишние кортежи, наличие которых и приводит к утрате исходной информации. Интуитивно понятно, что это происходит потому, что в отношении ЗАРП_ПРО отсутствуют функциональные зависимости СЛУ_ЗАРП
Корректность же декомпозиции 1 следует из теоремы Хита:
Теорема Хита.
Пусть задано отношение r {A, B, C} (A, B и C, в общем случае, являются составными атрибутами) и выполняется FD A
Рис. 7.4. Результат естественного соединения отношений СЛУЖ и ЗАРП_ПРО
Тогда r = (r PROJECT {A, B}) NATURAL JOIN (r PROJECT {A, C}).
Доказательство. Прежде всего, докажем, что в теле результата естественного соединения (обозначим этот результат через r1) содержатся все кортежи тела отношения r. Действительно, пусть кортеж {a, b, c}
Для иллюстрации общего случая применения теоремы Хита рассмотрим отношение СЛУЖАЩИЕ_ОТДЕЛЫ_ПРОЕКТЫ {СЛУ_НОМ, СЛУ_ОТД, ПРО_НОМ} (). Атрибут СЛУ_ОТД содержит номера отделов, в которых работают служащие, а ПРО_НОМ – номера проектов, в которых служащие принимают участие. Каждый служащий работает только в одном отделе, т. е. имеется FD СЛУ_НОМ
Рис. 7.5. Декомпозиция без потерь по теореме Хита
В отношении СЛУЖАЩИЕ_ОТДЕЛЫ_ПРОЕКТЫ атрибут СЛУ_НОМ не является возможным ключом, но, как показано на , наличия FD СЛУ_НОМ
Для дальнейшего изложения нам потребуется ввести еще одно определение и сделать пару замечаний.
Атрибут B минимально зависит от атрибута A, если выполняется минимальная слева FD A
Например, в отношении СЛУЖАЩИЕ_ПРОЕКТЫ выполняются FD СЛУ_НОМ
Краткая история языка SQL
Язык SQL, предназначенный для взаимодействия с базами данных, появился в середине 70-х гг. (первые публикации датируются 1974 г.) и был разработан в компании IBM в рамках проекта экспериментальной реляционной СУБД System R. Исходное название языка SEQUEL (Structured English Query Language) только частично отражало суть этого языка. Конечно, язык был ориентирован главным образом на удобную и понятную пользователям формулировку запросов к реляционным БД. Но, в действительности, он почти с самого начала являлся полным языком БД, обеспечивающим помимо средств формулирования запросов и манипулирования БД следующие возможности: средства определения и манипулирования схемой БД; средства определения ограничений целостности и триггеров; средства определения представлений БД; средства определения структур физического уровня, поддерживающих эффективное выполнение запросов; средства авторизации доступа к отношениям и их полям; средства определения точек сохранения транзакции и выполнения фиксации и откатов транзакций.
В языке отсутствовали средства явной синхронизации доступа к объектам БД со стороны параллельно выполняемых транзакций: с самого начала предполагалось, что необходимую синхронизацию неявно выполняет СУБД.
В настоящее время язык SQL реализован во всех коммерческих реляционных СУБД и почти во всех СУБД, которые изначально основывались не на реляционном подходе. Все компании-производители провозглашают соответствие своей реализации стандарту SQL, и на самом деле реализованные диалекты SQL очень близки. Этого удалось добиться не сразу.
Наиболее близки к System R были две системы компании IBM – SQL/DS и DB2. Разработчики обеих систем использовали опыт проекта System R, а СУБД SQL/DS напрямую основывалась на программном коде System R. Отсюда предельная близость диалектов SQL, реализованных в этих системах, к SQL System R. Из SQL System R были удалены только те части, которые были недостаточно проработаны (например, точки сохранения) или реализация которых вызывала слишком большие технические трудности (например, ограничения целостности и триггеры).
Можно назвать этот путь к коммерческой реализации SQL движением сверху вниз.
Другой подход применялся в таких системах, как Oracle, Informix и Sybase. Несмотря на различие в способах разработки систем, реализация SQL везде происходила «снизу вверх». В первых выпущенных на рынок версиях этих систем использовалось ограниченное подмножество SQL System R. В частности, в первой известной нам реализации SQL в СУБД Oracle в операторах выборки не допускалось использование вложенных подзапросов и отсутствовала возможность формулировки запросов с соединениями нескольких отношений.
Тем не менее, несмотря на эти ограничения и на очень слабую, на первых порах, эффективность СУБД, ориентация компаний на поддержку разных аппаратных платформ и заинтересованность пользователей в переходе к реляционным системам позволили компаниям добиться коммерческого успеха и приступить к совершенствованию своих реализаций. В текущих версиях Oracle, Informix, Sybase и Microsoft SQL Server поддерживаются достаточно мощные диалекты SQL, хотя реализация иногда вызывает сомнения.
Особенностью большинства современных коммерческих СУБД, затрудняющей сравнение существующих диалектов SQL, является отсутствие единообразного описания языка. Обычно описание разбросано по разным руководствам и перемешано с описанием специфических для данной системы языковых средств, не имеющих прямого отношения к SQL. Тем не менее, можно сказать, что базовый набор операторов SQL, включающий операторы определения схемы БД, выборки и манипулирования данными, авторизации доступа к данным, поддержки встраивания SQL в языки программирования и операторы динамического SQL, в коммерческих реализациях устоялся и более или менее соответствует стандарту.
Деятельность по стандартизации языка SQL началась практически одновременно с появлением его первых коммерческих реализаций. В 1982 г. комитету по базам данных Американского национального института стандартов (ANSI) было поручено разработать спецификацию стандартного языка реляционных баз данных.
Первый документ из числа имеющихся у автора проектов стандарта датирован октябрем 1985 г. и является уже не первым проектом стандарта ANSI. Стандарт был принят ANSI в 1986 г., а в 1987 г. одобрен Международной организацией по стандартизации (ISO). Этот стандарт принято называть SQL/86.
Понятно, что в качестве основы стандарта нельзя было использовать SQL System R. Во-первых, этот вариант языка не был должным образом технически проработан. Во-вторых, его слишком сложно было бы реализовать (кто знает, как бы сложилась судьба SQL, если бы все идеи проекта System R были реализованы полностью). Поэтому за основу был взят диалект языка SQL, сложившийся в IBM к началу 1980-х гг. В сущности, этот диалект представлял собой технически проработанное подмножество SQL System R.
К 1989 г. стандарт SQL/86 был несколько расширен, и был подготовлен и принят следующий стандарт, получивший название ANSI/ISO SQL/89. Анализ доступных документов показывает, что процесс стандартизации SQL происходил очень сложно с использованием не только научных доводов. В результате SQL/89 во многих частях имеет чрезвычайно общий характер и допускает очень широкое толкование. В этом стандарте полностью отсутствуют такие важные разделы, как манипулирование схемой БД и динамический SQL. Многие важные аспекты языка в соответствии со стандартом определяются в реализации.
Возможно, наиболее важными достижениями стандарта SQL/89 являются четкая стандартизация синтаксиса и семантики операторов выборки данных и манипулирования данными и фиксация средств ограничения целостности БД. Были специфицированы средства определения первичного и внешних ключей отношений и так называемых проверочных ограничений целостности, которые представляют собой подмножество немедленно проверяемых ограничений целостности SQL System R. Средства определения внешних ключей позволяют легко формулировать требования так называемой ссылочной целостности БД. Это распространенное в реляционных БД требование можно было сформулировать и на основе общего механизма ограничений целостности SQL System R, но формулировка на основе понятия внешнего ключа более проста и понятна.
Осознавая неполноту стандарта SQL, на фоне завершения разработки этого стандарта специалисты различных компаний начали работу над стандартом SQL2. Эта работа также длилась несколько лет, было выпущено множество проектов стандарта, пока наконец в марте 1992 г. не был принят окончательный проект стандарта (SQL/92). Этот стандарт существенно полнее стандарта SQL/89 и охватывает практически все аспекты, необходимые для реализации приложений: манипулирование схемой БД, управление транзакциями (появились точки сохранения) и сессиями (сессия – это последовательность транзакций, в пределах которой сохраняются временные отношения), подключения к БД, динамический SQL. Наконец, были стандартизованы отношения-каталоги БД, что вообще-то не связано непосредственно с языком, но очень сильно влияет на реализацию.
В 1995 г. стандарт был дополнен спецификацией интерфейса уровня вызова (Call-Level Interface – SQL/CLI). SQL/CLI представляет собой набор спецификаций интерфейсов процедур, вызовы которых позволяют выполнять динамически задаваемые операторы SQL. По сути дела, SQL/CLI представляет собой альтернативу динамическому SQL. Интерфейсы процедур определены для всех основных языков программирования: С, Ada, Pascal, PL/1 и т. д. Следует заметить, что стандарт SQL/CLI послужил основой для создания повсеместно распространенных сегодня интерфейсов ODBC (Open Database Connectivity) и JDBC (Java Database Connectivity).
В 1996 г. к стандарту SQL/92 был добавлен еще один компонент – SQL/PSM (Persistent Stored Modules). Основная цель этой спецификации состоит в том, чтобы стандартизировать способы определения и использования хранимых процедур, т. е. специальным образом оформленных программ, включающих операторы SQL, которые сохраняются в базе данных, могут вызываться приложениями и выполняются внутри СУБД.
Незадолго до завершения работ по определению стандарта SQL2 была начата разработка стандарта SQL3. Первоначально планировалось завершить проект в 1995 г. и включить в язык некоторые объектные возможности: определяемые пользователями типы данных, поддержку триггеров, поддержку темпоральных свойств данных и т.
д. Реально работу над новым стандартом удалось частично завершить только в 1999 г., и по этой причине (а также в связи с проблемой 2000 года) стандарт получил название SQL:1999.
Приведем краткую характеристику текущего состояния стандарта SQL:1999 и перспектив его развития. Прежде всего, заметим, что каждый новый вариант стандарта языка SQL был существенно объемнее предыдущих версий. Так, если стандарт SQL/89 занимал около 600 страниц, то объем SQL/92 составлял на 300 с лишним страниц больше. Самые первые проекты SQL3 занимали около 1500 страниц. Это вполне естественно, потому что язык усложняется, а его спецификации становятся более детальными и точными. Но разработчики SQL3 пришли к выводу, что при таких объемах стандарта вероятность его принятия и последующей успешной поддержки заметно уменьшается. Поэтому было принято решение разбить стандарт на относительно независимые части, которые можно было бы разрабатывать и поддерживать по отдельности.
В 1999 г. были приняты пять первых частей стандарта SQL:1999. Первая часть (SQL/Framework) посвящена описанию концептуальной структуры стандарта. В этой части приводится развернутая аннотация следующих четырех частей и формулируются требования к реализациям, претендующим на соответствие стандарту.
Вторая часть SQL:1999 (SQL/Foundation) образует базис стандарта. Вводится система типов языка, формулируются правила определения функциональных зависимостей и возможных ключей, определяются синтаксис и семантика основных операторов SQL: операторов определения и манипулирования схемой базы данных;операторов манипулирования данными;операторов управления транзакциями;операторов управления подключениями к базе данных и т. д.
Третью часть занимает уточненная по сравнению с SQL/92 спецификация SQL/CLI. В четвертой части специфицируется SQL/PSM – синтаксис и семантика языка определения хранимых процедур. Наконец, в пятой части – SQL/Bindings – определяются правила связывания SQL для стандартных версий языков программирования FORTRAN, COBOL, PL/1, Pascal, Ada, C и MUMPS.
В стандарт SQL: 1999 должны были войти еще несколько частей. Среди них спецификации следующих средств: управление распределенными транзакциями (SQL/Transaction); поддержка темпоральных свойств данных (SQL/Temporal);управление внешними данными (SQL/MED);связывание с объектно-ориентированными языками программирования (SQL/OLB);поддержка оперативной аналитической обработки (SQL/OLAP).
В конце 2003 г. был принят и опубликован новый вариант международного стандарта SQL:2003. Многие специалисты считали, что в варианте стандарта, следующем за SQL:1999, будут всего лишь исправлены неточности SQL:1999. Но на самом деле, в SQL:2003 специфицирован ряд новых и важных свойств, часть из которых мы затронем в этом курсе.
Претерпела некоторые изменения общая организация стандарта. Стандарт SQL:2003 состоит из следующих частей: 9075-1, SQL/Framework;9075-2, SQL/Foundation;9075-3, SQL/CLI;9075-4, SQL/PSM;9075-9, SQL/MED;9075-10, SQL/OLB;9075-11, SQL/Schemata;9075-13, SQL/JRT;9075-14, SQL/XML.
Части 1-4 и 9-10 с необходимыми изменениями остались такими же, как и в SQL:1999. Часть 5 (SQL/Bindings) перестала существовать; соответствующие спецификации включены в часть 2. Раздел части 2 SQL:1999, посвященный информационной схеме, выделен в отдельную часть 11. Появились две новые части – 13 и 14. Часть 13 полностью называется «SQL Routines and Types Using the Java Programming Language» («Использование подпрограмм и типов SQL в языке программирования Java»). Появление такой части стандарта оправдано повышенным вниманием к языку Java со стороны ведущих производителей SQL-ориентированных СУБД. Наконец, последняя часть SQL:2003 посвящена спецификациям языковых средств, позволяющих работать с XML-документами в среде SQL.
На мой взгляд, текущее состояние процесса стандартизации языка SQL отражает текущее состояние технологии SQL-ориентированных баз данных. Ведущие поставщики соответствующих СУБД (сегодня это компании IBM, Oracle и Microsoft) стараются максимально быстро реагировать на потребности и конъюнктуру рынка и расширяют свои продукты все новыми и новыми возможностями.Очевидна потребность в стандартизации соответствующих языковых средств, но процесс стандартизации явно не поспевает за происходящими изменениями.
Критерии применимости операций обновления
Введены понятия потенциальной применимости операций обновления, применимости операций обновления, простой применимости операций обновления и применимости операции вставки. К спецификации запроса потенциально применимы операции обновления в том и только в том случае, когда выполняются следующие условия: в разделе SELECT спецификации запроса отсутствует ключевое слово DISTINCT;элемент списка выборки раздела SELECT, состоящий из ссылки на некоторый столбец, не может присутствовать в этом списке более одного раза;в спецификации запроса отсутствуют разделы GROUP BY и HAVING.
Если выражение запросов отвечает условиям потенциальной применимости операций обновления и в его разделе FROM присутствует только одна ссылка на таблицу, то к каждому столбцу выражения запроса, соответствующему одному столбцу таблицы из раздела FROM, применимы операции обновления. Если выражение запроса отвечает условиям потенциальной применимости операций обновления, но в его разделе FROM присутствуют две или более ссылки на таблицы, то операции обновления применимы к столбцу выражения запросов только при выполнении следующих условий: столбец порождается из столбца только одной таблицы из раздела FROM;эта таблица используется в выражении запросов таким образом, что сохраняются свойства ее первичного и всех возможных ключей.
Другими словами, к столбцу таблицы, которая отвечает условиям потенциальной применимости операций обновления, применимы операции обновления только в том случае, когда этот столбец может быть однозначно сопоставлен с единственным столбцом единственной таблицы, участвующей в выражении запроса, и каждая строка выражения запроса может быть однозначно сопоставлена с единственной строкой данной таблицы.
Выражение запросов удовлетворяет условию применимости операций обновления, если по крайней мере к одному столбцу выражения запросов применимы операции обновления. Выражение запросов удовлетворяет условию простой применимости операций обновления, если в разделе FROM выражения запросов содержится ссылка только на одну таблицу, и все столбцы выражения запросов удовлетворяют условию применимости операций обновления.
Выражение запросов удовлетворит условию применимости операций вставки, если оно удовлетворяет условию применимости операций обновления; каждая из таблиц, от которых зависит это выражение (т.е. таблиц, на которые имеются ссылки в разделе FROM), удовлетворяет условию применимости операций вставки и выражение запросов не содержит операций UNION, INTERSECT и EXCEPT.Конечно, это определение базируется на том факте, что для любой базовой таблицы условие применимости операции вставки удовлетворяется (при наличии привилегии INSERT, см. следующую лекцию).
Кванторы, свободные и связанные переменные
При построении WFF допускается использование кванторов существования (EXISTS) и всеобщности (FORALL). Если form – это WFF, в которой участвует переменная var, то конструкции EXISTS var (form) и FORALL var (form) представляют собой WFF. По определению, формула EXISTS var (form) принимает значение true в том и только в том случае, если в области определения переменной var найдется хотя бы одно значение (кортеж), для которого WFF form принимает значение true. Формула FORALL var (form) принимает значение true, если для всех значений переменной var из ее области определения WFF form принимает значение true.
Переменные, входящие в WFF, могут быть свободными или связанными. По определению, все переменные, входящие в WFF, при построении которой не использовались кванторы, являются свободными. Фактически, это означает, что если для какого-то набора значений свободных кортежных переменных при вычислении WFF получено значение true, то эти значения кортежных переменных могут входить в результирующее отношение. Если же имя переменной использовано сразу после квантора при построении WFF вида EXISTS var (form) или FORALL var (form), то в этой WFF и во всех WFF, построенных с ее участием, var является связанной переменной. Это означает, что такая переменная не видна за пределами минимальной WFF, связавшей эту переменную. При вычислении значения такой WFF используется не одно значение связанной переменной, а вся область ее определения.
Пусть здесь и далее в этом разделе СЛУ1 и СЛУ2 представляют собой две кортежные переменные, определенные на отношении СЛУЖАЩИЕ. Тогда WFF
EXISTS СЛУ2 (СЛУ1.СЛУ_ЗАРП > СЛУ2.СЛУ_ЗАРП)
для текущего кортежа переменной СЛУ1 принимает значение true в том и только в том случае, если во всем отношении СЛУЖАЩИЕ найдется такой кортеж (ассоциированный с переменной СЛУ2), чтобы значение его атрибута СЛУ_ЗАРП удовлетворяло внутреннему условию сравнения. Легко видеть, что эта формула принимает значение true только для тех значений кортежной переменной СЛУ1, которые соответствуют служащим, не получающим минимальную зарплату.
Соответствующее множество кортежей показано на (для тела отношения СЛУЖАЩИЕ из ).
Рис. 6.2. Примеры правильно построенных формул с кванторами
Правильно построенная формула
FORALL СЛУ2 (СЛУ1.СЛУ_ЗАРП
для текущего кортежа переменной СЛУ1 принимает значение true в том и только в том случае, если для всех кортежей отношения СЛУЖАЩИЕ (связанных с переменной СЛУ2) значения атрибута СЛУ_ЗАРП удовлетворяют условию сравнения. Снова легко видеть, что формула принимает значение true только для тех значений кортежной переменной СЛУ1, которые соответствуют служащим, получающим максимальную зарплату. Соответствующее множество кортежей показано на .
Очевидно, что показанные на отношения соответствуют условиям обеих формул. Но как в данном случае можно реализовать систему, которая по заданной формуле производит правильный результат? Наиболее очевидный способ интерпретации обеих обсуждавшихся выше формул следующий. В некотором порядке просматривать область определения свободной кортежной переменной СЛУ1. Для каждого очередного кортежа из области определения СЛУ1 просматривать область определения связанной переменной СЛУ2 до тех пор, пока не будет установлено истинностное значение формулы для данного кортежа СЛУ1 (в случае наличия квантора существования процесс просмотра для СЛУ2 можно остановить после нахождения первого кортежа, для которого значением подформулы, находящейся под знаком квантора, станет true; при наличии квантора всеобщности необходимо просмотреть всю область определения СЛУ2). Заметим, что здесь мы снова получаем два цикла, как и при интерпретации WFF с двумя свободными переменными. Но в данном случае во внешнем цикле обязательно просматривается область определения свободной переменной.
На самом деле, правильнее говорить не о свободных и связанных переменных, а о свободных и связанных вхождениях переменных. Если переменная var является связанной в WFF form, то во всех WFF, включающих form, вне form может использоваться вхождение того же имени переменной var, которое может быть свободным или связанным, но в любом случае не имеет никакого отношения к вхождению переменной var в WFF form.
Вот пример:
EXISTS СЛУ2 (СЛУ1.ПРО_НОМ = СЛУ2.ПРО_НОМ AND СЛУ1.СЛУ_НОМЕР = СЛУ2.СЛУ_НОМЕР) AND FORALL СЛУ2 (IF СЛУ1.ПРО_НОМ = СЛУ2.ПРО_НОМ THEN СЛУ1.СЛУ_ЗАРП = СЛУ2.СЛУ_ЗАРП)
Эта формула принимает значение true только для тех значений переменной СЛУ1, которые соответствуют служащим, участвующим в проектах с более чем одним участником, причем все участники проекта получают одну и ту же зарплату. Здесь мы имеем два связанных вхождения переменной СЛУ2 с совершенно разным смыслом. Грубо говоря, для текущего значения переменной СЛУ1 переменная СЛУ2 два раза «пробежит» свою область определения – первый раз при вычислении части формулы с квантором существования, а второй при вычислении части с квантором всеобщности. Кстати, к тому же результату приведет формула с одним квантором всеобщности вида:
FORALL СЛУ2 (IF (СЛУ1.ПРО_НОМ = СЛУ2.ПРО_НОМ AND СЛУ1.СЛУ_НОМЕР
Легко заметить, что кванторы можно трактовать как булевские функции (функции, принимающие значения true или false) над множеством значений связанной кортежной переменной. С тем же успехом можно ввести в реляционное исчисление числовые функции над множествами, такие, как MIN (минимальное значение), MAX (максимальное значение), AVG (среднее значение) и т. д.
В этом случае можно было бы написать, например, WFF
СЛУ1.СЛУ_ЗАРП > MIN СЛУ2.СЛУ_ЗАРП (СЛУ1.ПРО_НОМ = СЛУ2.ПРО_НОМ)
в области истинности которой содержатся все кортежи отношения СЛУЖАЩИЕ, соответствующие тем служащим, которые получают заработную плату, превышающую минимальную зарплату служащих, участвующих в том же проекте. Понятно, что для получения результирующего отношения можно интерпретировать формулу таким же образом, как в обсуждавшемся выше случае наличия кванторов.
Логическая структура файловых систем и именование файлов
Во всех современных файловых системах обеспечивается многоуровневое именование файлов за счет наличия во внешней памяти каталогов – дополнительных файлов со специальной структурой. Каждый каталог содержит имена каталогов и/или файлов, хранящихся в данном каталоге. Таким образом, полное имя файла состоит из списка имен каталогов плюс имя файла в каталоге, непосредственно содержащем данный файл.
Поддержка многоуровневой схемы именования файлов обеспечивает несколько преимуществ, основным из которых является простая и удобная схема логической классификации файлов и генерации их имен. Можно сопоставить каталог или цепочку каталогов с пользователем, подразделением, проектом и т. д. и затем образовывать в этом каталоге файлы или каталоги, не опасаясь коллизий с именами других файлов или каталогов.
Разница между способами именования файлов в разных файловых системах состоит в том, с чего начинается эта цепочка имен. В любом случае первое имя должно соответствовать корневому каталогу файловой системы. Вопрос заключается в том, как сопоставить этому имени корневой каталог – где его искать? В связи с этим имеются два радикально различных подхода.
Во многих системах управления файлами требуется, чтобы каждый архив файлов (полное дерево каталогов) целиком располагался на одном дисковом пакете или логическом диске – разделе физического дискового пакета, логически представляемом в виде отдельного диска с помощью средств операционной системы. В этом случае полное имя файла начинается с имени дискового устройства, на котором установлен соответствующий диск. Такой способ именования использовался в файловых системах компаний IBM и DEC; очень близки к этому и файловые системы, реализованные в операционных системах семейства Windows компании Microsoft. Можно назвать такую организацию поддержкой изолированных файловых систем.
Другой крайний вариант был реализован в файловых системах операционной системы Multics . Эта система заслуживает отдельного разговора, в ней был реализован целый ряд оригинальных идей, но мы остановимся только на особенностях организации архива файлов.
В файловой системе Multics пользователям обеспечивалась возможность представлять всю совокупность каталогов и файлов в виде единого дерева. Полное имя файла начиналось с имени корневого каталога, и пользователь не обязан был заботиться об установке на дисковое устройство каких-либо конкретных дисков. Сама система, выполняя поиск файла по его имени, запрашивала у оператора установку необходимых дисков. Такую файловую систему можно назвать полностью централизованной.
Конечно, во многом централизованные файловые системы удобнее изолированных: система управления файлами выполняет больше рутинной работы. В частности, администратор файловой системы автоматически оповещается о потребности установки требуемых дисковых пакетов; система обеспечивает равномерное распределение памяти на известных ей дисковых томах; возможна организация автоматического перемещения редко используемых файлов на более медленные носители внешней памяти; облегчается рутинная работа, связанная с резервным копированием.
Но в таких системах возникают существенные проблемы, если требуется перенести поддерево файловой системы на другую вычислительную установку. Поскольку файлы и каталоги любого логического поддерева могут быть физически разбросаны по разным дисковым пакетам и даже магнитным лентам, для такого переноса требуется специальная утилита, собирающая все объекты требуемого поддерева на одном внешнем носителе, не входящем в состав штатных устройств централизованной файловой системы. Конечно, даже при наличии такой утилиты выполнение процедуры физической сборки требует существенного времени.
Компромиссное решение применяется в файловых системах ОС UNIX . На базовом уровне в этих файловых системах поддерживаются изолированные архивы файлов. Один из таких архивов объявляется корневой файловой системой. Это делается на этапе генерации операционной системы, и после запуска операционная система «знает», на каком дисковом устройстве (физическом или логическом) располагается корневая файловая система.
После запуска системы можно «смонтировать» корневую файловую систему и ряд изолированных файловых систем в одну общую файловую систему. Технически это осуществляется посредством создания в корневой файловой системе специальных пустых каталогов (точек монтирования).
Специальный системный вызов mount ОС UNIX позволяет подключить к одному из пустых каталогов корневой каталог указанного архива файлов. Выполнение такого действия приводит к «наложению» корневого каталога монтируемой файловой системы на каталог точки монтирования; корневой каталог приобретает имя каталога точки монтирования. После монтирования общей файловой системы именование файлов производится так же, как если бы она с самого начала была централизованной. Если учесть, что обычно монтирование файловой системы производится при раскрутке системы (при выполнении стартового командного файла), пользователи ОС UNIX, как правило, и не задумываются о происхождении общей файловой системы.
Кроме того, поддерживается системный вызов unmount, «отторгающий» ранее смонтированную файловую систему от общей иерархии. Конечно, все это заметно облегчает перенос частей файловой системы на другие установки.
Логические выражения раздела HAVING
Приведем примеры использования в логических выражениях раздела HAVING некоторых предикатов, обсуждавшихся в предыдущей лекции. Теоретически в этих логических выражениях можно использовать все предикаты, но применение тех предикатов, которые мы проиллюстрируем, является более естественным.
Логические выражения раздела WHERE
Синтаксически логическое выражение раздела WHERE определяется как булевское выражение (boolean_value_expression), правила построения которого обсуждались в предыдущей лекции. Основой логического выражения являются предикаты. Предикат позволяет специфицировать условие, результатом вычисления которого может быть true, false или unknown. В языке SQL:1999 допустимы следующие предикаты:
predicate ::= comparison_predicate | between_predicate | null_predicate | in_predicate | like_predicate | similar_predicate | exists_predicate | unique_predicate | overlaps_predicate | quantified_comparison_predicate | match_predicate | distinct_predicate
Далее мы будем последовательно обсуждать разные виды предикатов и приводить примеры запросов с использованием базы данных СЛУЖАЩИЕ-ОТДЕЛЫ-ПРОЕКТЫ, определения таблиц которой на языке SQL были приведены в лекции 16. Для удобства повторим здесь структуру таблиц.
| EMP_NO : EM_NO |
| EMP_NAME : VARCHAR |
| EMP_BDATE : DATE |
| EMP_SAL : SALARY |
| DEPT_NO : DEPT_NO |
| PRO_NO : PRO_NO |
| DEPT_NO : DEPT_NO |
| DEPT_NAME : VARCHAR |
| DEPT_EMP_NO : INTEGER |
| DEPT_TOTAL_SAL : SALARY |
| DEPT_MNG : EMP_NO |
| PRO_NO : PRO_NO |
| PRO_TITLE : VARCHAR |
| PRO_SDATE : DATEP |
| PRO_DURAT : INTERVAL |
| PRO_MNG : EMP_NO |
| PRO_DESC : CLOB |
Столбцы EMP_NO, DEPT_NO и PRO_NO являются первичными ключами таблиц EMP, DEPT и PRO соответственно. Столбцы DEPT_NO и PRO_NO таблицы EMP являются внешними ключами, ссылающимися на таблицы DEPT и PRO соответственно (DEPT_NO указывает на отделы, в которых работают служащие, а PRO_NO – на проекты, в которых они участвуют; оба столбца могут принимать неопределенные значения). Столбец DEPT_MNG является внешним ключом таблицы DEPT (DEPT_MNG указывает на служащих, которые исполняют обязанности руководителей отделов; у отдела может не быть руководителя, и один служащий не может быть руководителем двух или более отделов). Столбец PRO_MNG является внешним ключом таблицы PRO (PRO_MNG указывает на служащих, которые являются менеджерами проектов, у проекта всегда есть менеджер, и один служащий не может быть менеджером двух или более проектов).
Лучшие (в основном, не переведенные
На русском языке издано много книг по SQL (как переводных, так и написанных отечественными авторами). Но ни одна из них мне не нравится. Вот три книги, посвященные стандарту SQL, которыми пользуюсь я сам. К сожалению, на русский язык они не переведены.
4.1. C.J. Date with Hugh Darwen. A Guide to the SQL Standard. Fourth edition. Addison-Wesley Longman, 1997.
4.2. Jim Melton, Alan R. Symon. SQL:1999. Understanding Relational Language Components. Morgan Kaufmann Publishers, 2002
4.3. Jim Melton. Advanced SQL:1999. Understanding Object-Relational and Other Advanced Features. Morgan Kaufmann Publishers, 2003
4.4. “The Object Data Standard: ODMG 3.0”. Edited by R.G.G. Cattel, Douglas K. Barry. Morgan Kauffmann Publishers, 2000
Официальная публикация стандарта ODMG 3.0. В 2001 г. мы почти полностью перевели документ на русский язык, но не смогли издать, потому что издательство Morgan Kauffmann так и не откликнулось на наши просьбы разрешить издание книги на русском языке.
4.5. C. J. Date, Hugh Darwen. “Foundation for Object/Relational Databases: The Third Manifesto”, Addison-Wesley Pub Co; (June 1998)
4.6. C. J. Date, Hugh Darwen. “Foundation for Future Database Systems: The Third Manifesto”, Addison-Wesley Pub Co; 2nd edition (2000)
Эта книга как раз переведена на русский язык. См. .
4.7. C. J. Date and Hugh Darwen. Databases, Types, and the Relational Model. The Third Manifesto. Addison Wesley; 3th edition (2006)
Научным редактором перевода является выдающийся российский математик и теоретик баз данных М.Ш. Цаленко
Манипулирование данными
Поддерживаются два класса операций:
Операции, устанавливающие адрес записи и разбиваемые на два подкласса:
прямые поисковые операторы (например, установить адрес первой записи таблицы по некоторому пути доступа); операторы, устанавливающие адрес записи при указании относительной позиции от предыдущей записи по некоторому пути доступа.
Операции над адресуемыми записями.
Вот типичный набор операций:
LOCATE FIRST
– найти первую запись таблицы T
в физическом порядке; возвращается адрес записи; LOCATE FIRST WITH SEARCH KEY EQUAL – найти первую запись таблицы T
с заданным значением ключа поиска k; возвращается адрес записи; LOCATE NEXT
– найти первую запись, следующую за записью с заданным адресом в заданном пути доступа; возвращается адрес записи; LOCATE NEXT WITH SEARCH KEY EQUAL – найти cледующую запись таблицы T
в порядке пути поиска с заданным значением k; должно быть соответствие между используемым способом сканирования и ключом k; возвращается адрес записи; LOCATE FIRST WITH SEARCH KEY GREATER – найти первую запись таблицы T
в порядке ключа поиска k
cо значением ключевого поля, большим заданного значения k; возвращается адрес записи; RETRIVE
– выбрать запись с указанным адресом; UPDATE
– обновить запись с указанным адресом; DELETE
– удалить запись с указанным адресом; STORE
– включить запись в указанную таблицу; операция генерирует и возвращает адрес записи.
Примерами типичных операций манипулирования иерархически организованными данными могут быть следующие:
найти указанный экземпляр типа дерева БД (например, отдел 310); перейти от одного экземпляра типа дерева к другому;
перейти от экземпляра одного типа записи к экземпляру другого типа записи внутри дерева (например, перейти от отдела к первому сотруднику); перейти от одной записи к другой в порядке обхода иерархии; вставить новую запись в указанную позицию; удалить текущую запись.
Вот примерный набор операций манипулирования данными:
найти конкретную запись в наборе однотипных записей (например, служащего с именем Иванов); перейти от предка к первому потомку по некоторой связи (например, к первому служащему отдела 625); перейти к следующему потомку в некоторой связи (например, от Иванова к Сидорову); перейти от потомка к предку по некоторой связи (например, найти отдел, в котором работает Сидоров); создать новую запись; уничтожить запись; модифицировать запись; включить в связь; исключить из связи; переставить в другую связь и т.д.
Манипулирование данными в истинной реляционной модели
Вообще говоря, в качестве эталонного средства манипулирования данными в истинной реляционной модели можно использовать упоминавшуюся в подразделе реляционную алгебру Кодда. Однако в Дейт и Дарвен предложили новую реляционную алгебру, названную ими Алгеброй A, которая основывается на реляционных аналогах булевских операций конъюнкции, дизъюнкции и отрицания. В лекции 5 мы опишем эту алгебру и покажем, что через ее операции выражаются все операции алгебры Кодда.
Манипулирование данными в объектной модели
В стандарте ODMG в качестве базового средства манипулирования объектными базами данных предлагается язык OQL (Object Query Language). Это небольшой, но достаточно сложный язык запросов. Разработчики в целом характеризуют его следующим образом:
OQL опирается на объектную модель ODMG (имеется в виду, что в нем поддерживаются средства доступа ко всем возможным структурам данных, допускаемых в структурной части модели).
OQL очень близок к SQL/92. Расширения относятся к объектно-ориентированным понятиям, таким как сложные объекты, объектные идентификаторы, путевые выражения, полиморфизм, вызов операций и отложенное связывание.
В OQL обеспечиваются высокоуровневые примитивы для работы с множествами объектов, но, кроме того, имеются настолько же эффективные примитивы для работы со структурами, списками и массивами.
OQL является функциональным языком, допускающим неограниченную композицию операций, если операнды не выходят за пределы системы типов. Это является следствием того факта, что результат любого запроса обладает типом, принадлежащим к модели типов ODMG, и поэтому к результату запроса может быть применен новый запрос.
OQL не является вычислительно полным языком. Он представляет собой простой язык запросов.
Операторы языка OQL могут вызываться из любого языка программирования, для которого в стандарте ODMG определены правила связывания. И, наоборот, в запросах OQL могут присутствовать вызовы операций, запрограммированных на этих языках.
В OQL не определяются явные операции обновления, а используются вызовы операций, определенных в объектах для целей обновления. В OQL обеспечивается декларативный доступ к объектам. По этой причине OQL-запросы могут хорошо оптимизироваться.
Можно легко определить формальную семантику OQL.
Объем этой лекции не позволяет привести развернутое описание языка OQL. Приведем лишь один характерный пример.
Получить номера руководителей отделов и тех служащих их отделов, зарплата которых превышает 20000 руб.
SELECT DISTINCT STRUCT ( ОТД_РУК: D.ОТД_РУК,
СЛУ: ( SELECT E
FROM D.CONSISTS_OF AS E
WHERE E.СЛУ_ЗАРП > 20000.00 ) )
FROM ОТДЕЛЫ D
Здесь предполагается, что для атомарного объектного типа ОТДЕЛ определен экстент типа множества с именем ОТДЕЛЫ. В запросе перебираются все существующие объекты типа ОТДЕЛ, и для каждого такого объекта происходит переход по связи к литеральному множеству объектов типа СЛУЖАЩИЙ, соответствующих служащим, которые работают в данном отделе. На основе этого множества формируется «усеченное» множество объектов типа СЛУЖАЩИЙ, в котором остаются только объекты-служащие с зарплатой, большей 20000.00. Результатом запроса является литеральное значение-множество, элементами которого являются значения-структуры с двумя литеральными значениями, первое из которых есть атомарное литеральное значение типа INTEGER, а второе – литеральное значение-множество с элементами-объектами типа СЛУЖАЩИЙ.
Более точно, результат запроса имеет тип set < struct { integer ОТД_РУК; bag < СЛУЖАЩИЙ > СЛУ } >.
В совокупности результатом допустимых в OQL выражений запросов могут являться:
коллекция объектов;
индивидуальный объект;
коллекция литеральных значений;
индивидуальное литеральное значение.
Манипулирование данными в SQL
Средства манипулирования данными составляют значительную часть языка SQL и сравнительно подробно обсуждаются в лекциях 17-21. Здесь же мы ограничимся общей характеристикой оператора 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 ]
Выборка данных производится из одной или нескольких таблиц, указываемых в разделе FROM
запроса. В последнем случае на первом этапе выполнения оператора SELECT
образуется одна общая таблица, получаемая из исходных таблиц путем применения операции расширенного декартова умножения. Таблицы могут быть как базовыми, реально хранимыми в базе данных (традиционными или типизированными), так и порожденными, т.е. задаваемыми в виде некоторого оператора SELECT. Это допускается, поскольку результатом выполнения оператора SELECT
в его базовой форме является традиционная таблица. Кроме того, в разделе FROM
можно указывать выражения соединения базовых и/или порожденных таблиц, результатами которых опять же являются традиционные таблицы.
На следующем шаге общая таблица, полученная после выполнения раздела, подвергается фильтрации путем вычисления для каждой ее строки логического выражения, заданного в разделе WHERE
запроса. В отфильтрованной таблице остаются только те строки общей таблицы, для которых значением логического выражения является true.
Если в операторе отсутствует раздел GROUP BY, то после этого происходит формирование результирующей таблицы запроса путем вычисления выражений, заданных в списке выборки оператора SELECT.
В этом случае список выборки вычисляется для каждой строки отфильтрованной таблицы, и в результирующей таблице появится ровно столько же строк.
При наличии раздела GROUP BY
из отфильтрованной таблицы получается сгруппированная таблица, в которой каждая группа состоит из кортежей отфильтрованной таблицы с одинаковыми значениями столбцов группировки, задаваемых в разделе GROUP BY.
Если в запросе отсутствует раздел HAVING, то результирующая таблица строится прямо на основе сгруппированной таблицы. Иначе образуется отфильтрованная сгруппированная таблица, содержащая только те группы, для которых значением логического выражения, заданного в разделе HAVING, является true.
Результирующая таблица на основе сгруппированной или отфильтрованной сгруппированной таблицы строится путем вычисления списка выборки для каждой группы. Тем самым, в результирующей таблице появится ровно столько строк, сколько групп содержалось в сгруппированной или отфильтрованной сгруппированной таблице.
Если в запросе присутствует ключевое слово DISTINCT, то из результирующей таблицы устраняются строки-дубликаты, т.е. запрос вырабатывает не мультимножество, а множество строк.
Наконец, в запросе может присутствовать еще и раздел ORDER BY. В этом случае результирующая таблица сортируется в порядке возрастания или убывания в соответствии со значениями ее столбцов, указанных в разделе ORDER BY. Результатом такого запроса является не таблица, а отсортированный список, который нельзя сохранить в базе данных. Сам же запрос, содержащий раздел ORDER BY, нельзя использовать в разделе FROM
других запросов.
Приведенная характеристика средств манипулирования данными языка SQL является не вполне точной и полной. Кроме того, она отражает семантику оператора SQL, а не то, как он обычно исполняется в SQL-ориентированных СУБД.
Манипулирование реляционными данными
Поскольку в реляционной модели данных заголовок и тело любого отношения представляют собой множества, к отношениям, вообще говоря, применимы обычные теоретико-множественные операции: объединение, пересечение, вычитание, взятие декартова произведения. Напомним, что для двух множеств S1
{s1}
и S2
{s2}
результатом операции объединения этих двух множеств S1
UNION S2
является множество S
{s}
такое, что s
S1
или s
S2.
Результатом операции пересечения S1
INTERSECT S2
является множество S
{s}
такое, что s
S1
и s
S2.
Результатом операции вычитания S1
MINUS S2
является множество S
{s}
такое, что s
S1
и s
S2. На рис. 2.4 эти операции проиллюстрированы в интуитивной графической форме. Про операцию взятия декартова произведения уже говорилось выше.
Рис. 2.4. Иллюстрация результатов теоретико-множественных операций
Понятно, что эти операции применимы к любым телам отношений, но результатом не будет являться отношение, если у отношений-операндов не совпадают заголовки. Кодд предложил в качестве средства манипулирования реляционными базами данных специальный набор операций, которые гарантированно производят отношения. Этот набор операций принято называть реляционной алгеброй Кодда, хотя он и не является алгеброй в математическом смысле этого термина, поскольку некоторые бинарные операции этого набора применимы не к произвольным парам отношений.
В алгебре Кодда имеется деcять операций: объединение (UNION), пересечение (INTERSECT), вычитание (MINUS), взятие расширенного декартова произведения (TIMES), переименование атрибутов (RENAME), проекция (PROJECT), ограничение (WHERE), соединение (
При выполнении операции объединения
(UNION) двух отношений с одинаковыми заголовками производится отношение, включающее все кортежи, входящие хотя бы в одно из отношений-операндов. Операция пересечения
(INTERSECT) двух отношений с одинаковыми заголовками производит отношение, включающее все кортежи, входящие в оба отношения-операнда. Отношение, являющееся разностью
(MINUS) двух отношений с одинаковыми заголовками, включает все кортежи, входящие в отношение-первый операнд, такие, что ни один из них не входит в отношение, являющееся вторым операндом. При выполнении декартова произведения (TIMES) двух отношений, пересечение заголовков которых пусто, производится отношение, кортежи которого производятся путем объединения кортежей первого и второго операндов. Операция переименования
(RENAME) производит отношение, тело которого совпадает с телом операнда, но имена атрибутов изменены; эта операция позволяет выполнять первые три операции над отношениями с «почти» совпадающими заголовками (совпадающими во всем, кроме имен атрибутов) и выполнять операцию TIMES
над отношениями, пересечение заголовков которых не является пустым.
Результатом ограничения
(WHERE) отношения по некоторому условию является отношение, включающее кортежи отношения-операнда, удовлетворяющее этому условию. При выполнении проекции
(PROJECT) отношения на заданное подмножество множества его атрибутов производится отношение, кортежи которого являются соответствующими подмножествами кортежей отношения-операнда. При
(
образуется результирующее отношение, кортежи которого производятся путем объединения кортежей первого и второго отношений и удовлетворяют этому условию. У операции реляционного деления (DIVIDE BY) два операнда – бинарное и унарное отношения. Результирующее отношение состоит из унарных кортежей, включающих значения первого атрибута кортежей первого операнда таких, что множество значений второго атрибута (при фиксированном значении первого атрибута) включает множество значений второго операнда. Операция присваивания
(:=) позволяет сохранить результат вычисления реляционного выражения в существующем отношении БД.
Механизмы генерации ссылочных значений
В SQL:1999 и SQL:2003 обеспечиваются три механизма назначения уникальных идентификаторов экземплярам структурных типов, ассоциированных с типизированными таблицами. Во всех типизированных таблицах, ассоциированных с данным структурным типом, должен использоваться один и тот же механизм. Предоставляются следующие альтернативы выбора ссылочных значений, которые могут являться: значениями некоторого встроенного типа SQL (user_defined_representation), которые должны генерироваться приложением каждый раз при сохранении экземпляра структурного типа как строки типизированной таблицы;значениями, порождаемыми из одного или нескольких атрибутов структурного типа;значениями, автоматически генерируемыми системой.
Как отмечалось в разделе , при определении любого максимального структурного супертипа явно или неявно задается спецификация ссылочного типа. Спецификация ссылочного типа наследуется всеми подтипами этого супертипа. При определении типизированных таблиц необходимо указать соответствующую спецификацию самоссылающегося столбца (конечно, эта спецификация логически избыточна, и, по всей вероятности, в следующих версиях стандарта SQL это требование будет ослаблено). Хотя соотношение между альтернативами спецификации ссылочного типа и спецификации самоссылающегося столбца очевидно, приведем его явно ().
| reference_type_specification | self-referencing_column |
| REF USING predefined_type | USER GENERATED |
| REF FROM commalist_of_attributes | DERIVED |
| REF IS SYSTEM GENERATED SYSTEM | GENERATED |
Если для некоторого структурного типа выбран вариант пользовательской генерации ссылочных значений, то ответственность за поддержание уникальности таких значений лежит на пользователе. Конечно, ограничения PRIMARY KEY или UNIQUE, определенные на уровне максимальной супертаблицы семейства типизированных таблиц, могут гарантировать отсутствие в любой таблице этого семейства дублирующих ссылочных значений, но в SQL:1999 отсутствуют какие-либо средства, предотвращающие повторное использование ссылочных значений из удаленных строк в самоссылающихся столбцах новых строк.
Метод временных меток
Альтернативный метод сериализации транзакций, хорошо работающий в условиях редкого возникновения конфликтов транзакций и не требующий построения графа ожидания транзакций, основан на использовании временных меток. Основная идея метода временных меток (Timestamp Ordering, TO), у которого существует множество разновидностей, состоит в следующем: если транзакция T1
началась раньше транзакции T2, то система обеспечивает такой сериальный план, как если бы транзакция T1
была целиком выполнена до начала T2.
Для этого каждой транзакции T
предписывается временная метка t(T), соответствующая времени начала выполнения транзакции T. При выполнении операции над объектом o
транзакция T
помечает его своими идентификатором, временной меткой и типом операции (чтение или изменение).
Перед выполнением операции над объектом o
транзакция T2
выполняет следующие действия:
Проверяет, помечен ли объект o
какой-либо транзакцией T1. Если не помечен, то помечает этот объект своей временной меткой и типом операции и выполняет операцию. Конец действий.
Иначе транзакция T2
проверяет, не завершилась ли транзакция T1, пометившая этот объект. Если транзакция T1
закончилась, то T2
помечает объект o
и выполняет свою операцию. Конец действий.
Если транзакция T1
не завершилась, то T2
проверяет конфликтность операций. Если операции неконфликтны, то при объекте o
запоминается идентификатор транзакции T2, остается или проставляется временная метка с меньшим значением, и транзакция T2
выполняет свою операцию.
Если операции транзакций T2
и T1
конфликтуют, то если t(T1) > t(T2)
(т.е. транзакция T1
является более «молодой», чем T2), то производится откат T1
и всех других транзакций, идентификаторы которых сохранены при объекте o, и T2
выполняет свою операцию.
Если же t(T1) < t(T2)
(T1
«старше» T2), то производится откат T2; T2
получает новую временную метку и начинается заново.
К недостаткам метода TO относятся потенциально более частые откаты транзакций, чем в случае использования синхронизационных захватов. Это связано с тем, что конфликтность транзакций определяется более грубо. Кроме того, в распределенных системах не очень просто вырабатывать глобальные временные метки с отношением полного порядка (это отдельная большая наука).
Но в распределенных системах эти недостатки окупаются тем, что не нужно распознавать тупики, а как мы уже отмечали, построение графа ожидания в распределенных системах стоит очень дорого.
Методы сериализации транзакций
Существуют два базовых подхода к сериализации транзакций – основанный на синхронизационных захватах объектов базы данных и на использовании временных меток. Суть обоих подходов состоит в обнаружении конфликтов транзакций и их устранении. Ниже мы рассмотрим эти подходы сравнительно подробно. Кроме того, кратко обсудим возможности использования версий объектов базы данных для ускорения выполнения «только читающих» транзакций, т.е. транзакций, в которых не выполняются операции изменения базы данных.
Предварительно заметим, что для каждого из подходов имеются две разновидности – пессимистическая и оптимистическая. При применении пессимистических методов, ориентированных на ситуации, когда конфликты возникают часто, конфликты распознаются и разрешаются немедленно при их возникновении. Оптимистические методы основываются на том, что результаты всех операций модификации базы данных сохраняются в рабочей памяти транзакций. Реальная модификация базы данных производится только на стадии фиксации транзакции. Тогда же проверяется, не возникают ли конфликты с другими транзакциями.
Далее мы ограничимся рассмотрением более распространенных пессимистических разновидностей методов сериализации транзакций. Пессимистические методы сравнительно просто трансформируются в свои оптимистические варианты.
Методы сериализации транзакций на основе поддержки версий объектов базы данных
Основная идея алгоритмов сериализации транзакций, описываемых в этом разделе, состоит в том, что в базе данных допускается существование нескольких «версий» одного и того же объекта. Эти алгоритмы, главным образом, направлены на преодоление конфликтов транзакций категорий R/W и W/R, позволяя выполнять операции чтения над некоторой предыдущей версией объекта базы данных. В результате операции чтения выполняются без задержек и тупиков, свойственных механизмам синхронизационных блокировок, а также без некоторых откатов, возможных при применении метода временных меток, описанного в предыдущем подразделе.
Алгоритмы управления транзакциями, основанные на поддержке версий, достаточно широко распространены в области SQL-ориентированных СУБД. В частности, подобные алгоритмы используются в СУБД Oracle и PostgreSQL. В дальнейшем в этом подразделе будем называть алгоритмы этой категории версионными
алгоритмами.
Минимальное покрытие множества функциональных зависимостей
Множество FD S2 называется покрытием множества FD S1, если любая FD, выводимая из S1, выводится также из S2.
Легко заметить, что S2 является покрытием S1 тогда и только тогда, когда S1+
Множество FD S называется минимальным в том и только в том случае, когда удовлетворяет следующим свойствам: правая часть любой FD из S является множеством из одного атрибута (простым атрибутом);детерминант каждой FD из S обладает свойством минимальности; это означает, что удаление любого атрибута из детерминанта приводит к изменению замыкания S+, т. е. порождению множества FD, не эквивалентного S;удаление любой FD из S приводит к изменению S+, т. е. порождению множества FD, не эквивалентного S.
Чтобы продемонстрировать минимальные и неминимальные множества FD, вернемся к примеру отношения СЛУЖАЩИЕ_ПРОЕКТЫ {СЛУ_НОМ, СЛУ_ИМЯ, СЛУ_ЗАРП, ПРО_НОМ, ПРОЕКТ_РУК} с . Если считать, что единственным возможным ключом этого отношения является атрибут СЛУ_НОМ, то множество FD {СЛУ_НОМ
С другой стороны, множества FD {СЛУ_НОМ
не являются минимальными. Для множества (1) в правой части первой FD присутствует множество из двух элементов. Для множества (2) удаление атрибута СЛУ_ИМЯ из детерминанта второй FD не меняет замыкание множества FD.
Для множества (3) удаление первой FD не приводит к изменению замыкания. Эти примеры показывают, что для определения минимальности множества FD не всегда требуется явное построение замыкания данного множества.
Интересным и важным является тот факт, что для любого множества FD S существует (и даже может быть построено) эквивалентное ему минимальное множество S-.
Приведем общую схему построения S- по заданному множеству FD S. Во-первых, используя правило (5) (декомпозиции), мы можем привести множество S к эквивалентному множеству FD S1, правые части FD которого содержат только одноэлементные множества (простые атрибуты). Далее, для каждой FD из S1, детерминант D {D1, D2, …, Dn} которой содержит более одного атрибута, будем пытаться удалять атрибуты Di, получая множество FD S2. Если после удаления атрибута Di S2 эквивалентно S1, то этот атрибут удаляется, и пробуется следующий атрибут. Назовем S3 множество FD, полученное путем допустимого удаления атрибутов из всех детерминантов FD множества S1. Наконец, для каждой FD f из множества S3 будем проверять эквивалентность множеств S3 и S3 MINUS {f}. Если эти множества эквивалентны, удалим f из множества S3, и в заключение получим множество S4, которое минимально и эквивалентно исходному множеству FD S.
Пусть, например, имеется отношение R {A, B, C, D} и задано множество FD S = {A
Минимальным покрытием множества FD S называется любое минимальное множество FD S1, эквивалентное S.
Поскольку для каждого множества FD существует эквивалентное минимальное множество FD, у каждого множества FD имеется хотя бы одно минимальное покрытие, причем для его нахождения не обязательно находить замыкание исходного множества.
Минимальные функциональные зависимости и вторая нормальная форма
Пусть имеется переменная отношения СЛУЖАЩИЕ_ПРОЕКТЫ_ЗАДАНИЯ {СЛУ_НОМ, СЛУ_УРОВ, СЛУ_ЗАРП, ПРО_НОМ, СЛУ_ЗАДАН}. Новые атрибуты СЛУ_УРОВ и СЛУ_ЗАДАН содержат, соответственно, данные о разряде служащего и о задании, которое выполняет служащий в данном проекте. Будем считать, что разряд служащего определяет размер его заработной платы и что каждый служащий может участвовать в нескольких проектах, но в каждом проекте он выполняет только одно задание. Тогда очевидно, что единственно возможным ключом отношения СЛУЖАЩИЕ_ПРОЕКТЫ_ЗАДАНИЯ является составной атрибут {СЛУ_НОМ, ПРО_НОМ}. Диаграмма минимального множества FD показана на , а возможное тело значения отношения – на .
Рис. 8.1. Диаграмма множества FD отношения СЛУЖАЩИЕ_ПРОЕКТЫ_ЗАДАНИЯ
Рис. 8.2. Возможное значение переменной отношения СЛУЖАЩИЕ_ПРОЕКТЫ_ЗАДАНИЯ
Многозначные зависимости и четвертая нормальная форма
Чтобы перейти к вопросам дальнейшей нормализации, рассмотрим еще одну возможную (четвертую) интерпретацию переменной отношения СЛУЖ_ПРО_ЗАДАН. Предположим, что каждый служащий может участвовать в нескольких проектах, но в каждом проекте, в котором он участвует, им должны выполняться одни и те же задания. Возможное значение четвертого варианта переменной отношения СЛУЖ_ПРО_ЗАДАН показано на .
Рис. 9.1. Возможное значение переменной отношения СЛУЖ_ПРО_ЗАДАН (четвертый вариант)
Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма
Заметим, что последний вариант переменной отношения СЛУЖ_ПРО_ЗАДАН находится в BCNF, поскольку все атрибуты заголовка отношения входят в состав единственно возможного ключа. В этом отношении вообще отсутствуют нетривиальные FD. Поэтому ранее обсуждавшиеся принципы нормализации здесь неприменимы, но, тем не менее, мы получили полезную декомпозицию. Все дело в том, что в случае четвертого варианта отношения СЛУЖ_ПРО_ЗАДАН мы имеем дело с новым видом зависимости, впервые обнаруженным Роном Фейджином в 1971 г. Фейджин назвал зависимости этого вида многозначными (multi-valued dependency – MVD). Как мы увидим немного позже, MVD является обобщением понятия FD.
В отношении СЛУЖ_ПРО_ЗАДАН выполняются две MVD: СЛУ_НОМ
(СЛУЖ_ПРО_НОМ WHERE (СЛУ_НОМ = сн AND СЛУ_ЗАДАН = сз)) PROJECT {ПРО_НОМ}
для фиксированного допустимого значения сн и любого допустимого значения сз мы всегда получим одно и то же множество значений атрибута ПРО_НОМ. Аналогично трактуется вторая MVD.
В переменной отношения R с атрибутами A, B, C (в общем случае, составными) имеется многозначная зависимость B от A (A
Многозначные зависимости обладают интересным свойством «двойственности», которое демонстрирует следующая лемма.
Лемма Фейджина
В отношении R {A, B, C} выполняется MVD A
Доказательство достаточности условия леммы. Пусть выполняется MVD A
Предположим, что для этого значения a MVD A
Таким образом, MVD A
FD является частным случаем MVD, когда множество значений зависимого атрибута обязательно состоит из одного элемента. Таким образом, если выполняется FD A
Мы видим, что отношения СЛУЖ_ПРО_НОМ и СЛУЖ_ЗАДАНИЕ не содержат MVD, отличных от FD, и именно в этом выигрывает декомпозиция из . Правомочность этой декомпозиции доказывается приведенной ниже теоремой Фейджина, которая является уточнением и обобщением теоремы Хита.
Теорема Фейджина
Пусть имеется переменная отношения R с атрибутами A, B, C (в общем случае, составными). Отношение R декомпозируется без потерь на проекции {A, B} и {A, C} тогда и только тогда, когда для него выполняется MVD A
Докажем достаточность условия теоремы. Пусть r является некоторым допустимым значением переменной отношений R. Пусть a есть значение атрибута A в некотором кортеже тела Br, {b} – множество значений атрибута B, взятых из всех кортежей тела Br, в которых значением атрибута A является a, и {c} – множество значений атрибута C, взятых из всех кортежей тела Br, в которых значением атрибута A является a. Тогда очевидно, что в тело значения r PROJECT {A, B} будут входить все кортежи вида {a, bi}, где bi
Для доказательства необходимости условия теоремы предположим, что декомпозиция переменной отношения R {A, B, C} на проекции R PROJECT {A, B} и R PROJECT {A, C} является декомпозицией без потерь для любого допустимого значения r переменной отношения R. Мы должны показать, что в теле Br значения-отношения r поддерживается ограничение
IF ({a, b1, c1};
Действительно, пусть в Br входят кортежи {a, b1, c1} и {a, b2, c2}. Предположим, что {a, b1, c2}
Теорема Фейджина обеспечивает основу для декомпозиции отношений, удаляющей «аномальные» многозначные зависимости, с приведением отношений в четвертую нормальную форму.
Переменная отношения r находится в четвертой нормальной форме (4NF) в том и только в том случае, когда она находится в BCNF, и все MVD r являются FD с детерминантами – возможными ключами отношения r.
В сущности, 4NF является BCNF, в которой многозначные зависимости вырождаются в функциональные (позволим себе на один момент отказаться от сокращений). Понятно, что отношение СЛУЖ_ПРО_ЗАДАН не находится в 4NF, поскольку детерминант MVD СЛУ_НОМ
Упражнение по ходу лекции. Пусть имеется отношение r
с атрибутами A
, B
, C
(в общем случае, составными), в котором существует FD A
. Что в этом случае можно сказать про зависимость атрибутов A
и C
?
Модель данных
В модели данных описывается некоторый набор родовых понятий и признаков, которыми должны обладать все конкретные СУБД и управляемые ими базы данных, если они основываются на этой модели. Наличие модели данных позволяет сравнивать конкретные реализации, используя один общий язык.
Хотя понятие модели данных было введено Коддом, наиболее распространенная трактовка модели данных, по-видимому, принадлежит Кристоферу Дейту, который воспроизводит ее (с различными уточнениями) применительно к реляционным БД практически во всех своих книгах (см., например, ). Согласно Дейту реляционная модель состоит из трех частей, описывающих разные аспекты реляционного подхода: структурной части, манипуляционной части и целостной части.
В структурной части модели данных фиксируются основные логические структуры данных, которые могут применяться на уровне пользователя при организации БД, соответствующих данной модели. Например, в модели данных SQL основным видом структур базы данных являются таблицы, а в объектной модели данных – объекты ранее определенных типов.
Манипуляционная часть модели данных содержит спецификацию одного или нескольких языков, предназначенных для написания запросов к БД. Эти языки могут быть абстрактными, не обладающими точно проработанным синтаксисом (что свойственно языками реляционной алгебры и реляционного исчисления, используемым в реляционной модели данных), или законченными производственными языками (как в случае модели данных SQL). Основное назначение манипуляционной части модели данных – обеспечить эталонный «модельный» язык БД, уровень выразительности которого должен поддерживаться в реализациях СУБД, соответствующих данной модели.
Наконец, в целостной части модели данных (которая явно выделяется не во всех известных моделях) специфицируются механизмы ограничений целостности, которые обязательно должны поддерживаться во всех реализациях СУБД, соответствующих данной модели. Например, в целостной части реляционной модели данных категорически требуется поддержка ограничения первичного ключа в любой переменной отношения, а аналогичное требование к таблицам в модели данных SQL отсутствует.
В этой лекции мы применим понятие модели данных для обзора как подходов, предшествовавших появлению реляционных баз данных, так и подходов, которые возникли позже. Мы не будем касаться особенностей каких-либо конкретных систем; это привело бы к изложению многих технических деталей, которые, хотя и интересны, но находятся несколько в стороне от основной цели курса.
Модель данных инвертированных таблиц
К числу наиболее известных и типичных представителей систем, в основе которых лежит эта модель данных, относятся СУБД Datacom/DB, выведенная на рынок в конце 1960-х гг. компанией Applied Data Research, Inc. (ADR) и принадлежащая в настоящее время компании Computer Associates, и Adabas (ADAptable DAtabase System), которая была разработана компанией Software AG в 1971 г. и до сих пор является ее основным продуктом.
Организация доступа к данным на основе инвертированных таблиц используется практически во всех современных реляционных СУБД, но в этих системах пользователи не имеют непосредственного доступа к инвертированным таблицам (индексам). Кстати, когда мы будем рассматривать внутренние интерфейсы реляционных СУБД, можно будет увидеть, что они очень близки к пользовательским интерфейсам систем, основанных на инвертированных таблицах.
Модель данных SQL
Как отмечалось в начале этого раздела, модель данных SQL в относительно законченном виде сложилась к 1999 г., когда был принят и опубликован стандарт SQL:1999. В приводимом в этом подразделе очерке этой модели данных мы затронем только наиболее важные, с точки зрения автора, ее черты, опуская многие менее существенные моменты.
