ACID-транзакция
В SQL:1999 поддерживается классическое понимание транзакции, характеризуемое аббревиатурой ACID (от Atomicy, Consistency, Isolation и Durability). В соответствии с этим понятием под транзакцией разумеется последовательность операций (например, над базой данных), обладающая следующими свойствами. Атомарность (Atomicy). Это свойство означает, что результаты всех операций, успешно выполненных в пределах транзакции, должны быть отражены в состоянии базы данных, либо в состоянии базы данных не должно быть отражено действие ни одной операции (конечно, здесь речь идет об операциях, изменяющих состояние базы данных). Свойство атомарности, которое часто называют свойством «все или ничего», позволяет относиться к транзакции, как к динамически образуемой составной операции над базой данных.Согласованность (Consistency). В классическом смысле это свойство означает, что транзакция может быть успешно завершена с фиксацией результатов своих операций только в том случае, когда действия операций не нарушают целостность базы данных, т. е. удовлетворяют набору ограничений целостности, определенных для этой базы данных. В стандарте SQL:1999 это свойство расширяется тем, что во время выполнения транзакции разрешается устанавливать точки согласованности (см. ниже про точки сохранения) и явным образом проверять ограничения целостности.Изоляция (Isolation). Требуется, чтобы две одновременно выполняемые транзакции никоим образом не действовали одна на другую. Другими словами, результаты выполнения операций транзакции T1 не должны быть видны никакой другой транзакции T2 до тех пор, пока транзакция T1 не завершится успешным образом.Долговечность (Durability). После успешного завершения транзакции все изменения, которые были внесены в состояние базы данных операциями этой транзакции, должны гарантированно сохраняться, даже в случае сбоев аппаратуры или программного обеспечения.
Агрегатная функция GROUPING
Обсудим теперь один более тонкий вопрос. Как говорилось в лекции 16, определение столбцов DEPT_NO и EMP_BDATE таблицы EMP допускает появление в этих столбцах неопределенных значений. Поэтому тело таблицы EMP могло бы иметь, например, следующий вид:
| 2440 | 1 | 1950 | 15000.00 |
| 2441 | 1 | 1950 | 16000.00 |
| 2442 | 1 | 1960 | 14000.00 |
| 2443 | 1 | 1960 | 19000.00 |
| 2452 | 1 | NULL | 15000.00 |
| 2453 | 1 | NULL | 17000.00 |
| 2444 | 2 | 1950 | 17000.00 |
| 2445 | 2 | 1950 | 16000.00 |
| 2446 | 2 | 1960 | 14000.00 |
| 2447 | 2 | 1960 | 20000.00 |
| 2448 | 3 | 1950 | 18000.00 |
| 2449 | 3 | 1950 | 13000.00 |
| 2450 | 3 | 1960 | 21000.00 |
| 2451 | 3 | 1960 | 22000.00 |
| 2454 | NULL | 1950 | 13000.00 |
| 2455 | NULL | 1950 | 14000.00 |
| 2456 | NULL | NULL | 19000.00 |
Тогда результат запроса из имел бы следующий вид:
Рис. 20.2. Результат запроса с разделом GROUP BY ROLLUP к таблице с неопределенными значениями столбцов группировки
Очевидно, что, просматривая строки таблицы, показанной на , невозможно установить, в какой из первых трех строк неопределенное значение столбцов DEPT_NO и EMP_BDATE означает то, что эта строка является сводной для всего предприятия, а не то, что она является сводной для всех служащих с неизвестными номером отдела и годом рождения или просто для всех служащих с неизвестным номером отдела. Аналогичным образом невозможно понять, какая строка в следующей далее паре строк является сводной для всех служащих отдела номер 1, а не для всех служащих отдела номер 1 с неизвестным годом рождения.
Для того чтобы всегда можно было разобраться в результатах запросов, включающих раздел GROUP BY ROLLUP, в язык SQL была введена специальная агрегатная функция GROUPING. Эта функция применяется к столбцу, входящему в список столбцов раздела GROUP BY ROLLUP, и принимает целое значение 1 в тех строках результирующей таблицы, в которых соответствующий столбец имеет значение NULL по той причине, что строка является сводной для более обобщенной группы. В противном случае функция GROUPING принимает значение 0.
Уточним формулировку запроса из (пример 20.1.1):
SELECT DEPT_NO, EMP_BDATE, MAX (EMP_SAL) AS MAX_SAL, GROUPING (DEPT_NO) AS GDN, GROUPING (EMP_BDATE) AS GEB FROM EMP GROUP BY ROLLUP (DEPT_NO, EMP_BDATE);
Результирующая таблица для этого запроса будет иметь следующий вид:
Рис. 20.3. Результат запроса с разделом GROUP BY ROLLUP и вызовами агрегатной функции GROUPING к таблице с неопределенными значениями столбцов группировки
Анализируя значения столбцов GDN и GEB в строках таблицы, показанной на , можно убедиться, что значение столбца MAX_SAL в первой строке является максимальным значением зарплаты всех служащих предприятия, во второй строке – максимальным значением зарплаты служащих с неизвестными номером отдела и годом рождения, а в третьей строке – максимальным значением зарплаты всех служащих с неизвестным номером отдела. В следующих трех строках значения столбца MAX_SAL являются максимальными значениями зарплаты служащих с неизвестным годом рождения из отделов с номерами 1, 2 и 3 соответственно. Как видно, значения столбцов GDN и GEB являются своего рода индикаторами, указывающими на природу основных значений строки.
Агрегатные функции, группировка и условия раздела HAVING
В этом разделе мы систематически обсудим все аспекты группировки таблиц и вычисления агрегатных функций. Некоторые темы уже затрагивались на неформальном уровне в предыдущих лекциях.
Аннулирование привилегий
Для аннулирования привилегий используется оператор REVOKE, определяемый следующим синтаксическим правилом:
REVOKE [ GRANT OPTION FOR] privilege_commalist ON privilege_object FROM { PUBLIC | authID_commalist } [ GRANTED BY { CURRENT_USER | CURRENT_ROLE } ] { RESTRICT | CASCADE }
Синтаксис конструкций privilege и privilege_object такой же, как для оператора GRANT. Общий смысл операции должен быть понятен из синтаксиса: у указанных authID аннулируются указанные привилегии доступа к указанному объекту базы данных.
Первой важной особенностью оператора аннулирования привилегий является обязательность указания одного из ключевых слов RESTRICT или CASCADE. Если в операторе содержится RESTRICT, то при выполнении операции система проверит, не передавалась ли какая-либо из указанных привилегий каким-либо authID от того authID, у которого привилегия должна быть аннулирована (это вполне возможно, если ранее привилегия была передана с правом передачи). Если это действительно так, операция не выполняется; в противном случае указанные привилегии у указанных authID аннулируются. Иначе говоря, при наличии ключевого слова RESTRICT не допускается, например, ситуация, показанная на .
Рис. 22.2. Передача полученной привилегии
На этом рисунке authID1 является владельцем объекта базы данных с именем object и, следовательно, обладает всеми привилегиями над этим объектом. Пунктирной стрелкой обозначена одна из подобных привилегий pr1. От имени authID1 привилегия pr1 была передана authID2 вместе с привилегией на ее дальнейшую передачу. Наконец, от имени authID2 привилегия pr1 была передана authID3. Тогда операция аннулирования этой привилегии от имени authID1 у authID2 при наличии ключевого слова RESTRICT не будет выполнена успешно.
В той же ситуации привилегия была бы аннулирована для authID2 (и для authID3), если бы в операторе GRANT присутствовало ключевое слово CASCADE. В общем случае если выполняется операция REVOKE ... CASCADE, то указанные привилегии аннулируются у всех authID, прямо или косвенно (через промежуточные authID) получивших привилегии от текущего authID SQL-сессии, в которой выполняется данная операция.
Если в операторе содержится раздел GRANT OPTION FOR, но имеется ключевое слово RESTRICT, то указанные привилегии для указанных authID не аннулируются, но у указанных authID аннулируется привилегия передачи данных привилегий (операция должна успешно выполняться только при соблюдении обсуждавшихся ранее условий). Однако если в операторе одновременно содержатся и GRANT OPTION FOR, и CASCADE, то указанные привилегии аннулируются у всех authID, которые прямо или косвенно (через промежуточные authID) получили привилегии от текущего authID SQL-сессии, в которой выполняется данная операция.
Задание в операторе необязательного раздела GRANTED BY позволяет явно указать, что должно использоваться в качестве текущего authID – текущий пользовательский идентификатор или текущее имя роли SQL-сессии. Если раздел GRANTED BY в операторе REVOKE не содержится, то действия производятся от имени текущего authID SQL-сессии (о том, как он определяется, см. выше).
Если текущий (или указанный) authID не обладает ни одной из указанных в операторе REVOKE привилегий, то выполнение операции не производится (фиксируется ошибка). Если authID обладает некоторыми, но не всеми, привилегиями из числа указанных, то операция выполняется по отношению к этим некоторым привилегиям, но выдается предупреждение.
Возможны ситуации, когда у некоторого authID остается некоторая привилегия после выполнения операции аннулирования у этого authID этой привилегии. Одна из таких ситуаций проиллюстрирована на .
Рис. 22.3. Косвенная и прямая передача привилегий
Здесь привилегия pr1 передана от authID1 к authID2 вместе с правом на дальнейшую передачу этой привилегии. Далее, привилегия pr1 передается от authID2 к authID3. И затем выполняется прямая передача привилегии от authID1 к authID3 (на самом деле, порядок таких действий не является существенным). Теперь предположим, что от имени authID1 выполняется операция
REVOKE pr1 ON object FROM authID2 CASCADED
В соответствии с правилами SQL:1999 после выполнения этой операции authID3 будет продолжать владеть привилегией pr1 по отношению к объекту object, поскольку получил данную привилегию двумя разными способами.
Грубо говоря, операция REVOKE, выполняемая от имени authID1, выполняется только по тем путям графа идентификаторов авторизации и объектов базы данных, которые начинаются с узлов, соответствующих authID, указанных в разделе FROM этой операции.
Далее, напомним, что если при передаче от authID1 к authID2 привилегии на выполнение некоторых действий над некоторой таблицей T (например, UPDATE) явно не указывается список имен столбцов этой таблицы, то привилегия распространяется на все столбцы этой таблицы (включая столбцы, которые, возможно, еще будут созданы). Если действительно использовался такой способ передачи привилегий, то в дальнейшем можно аннулировать привилегию authID2 на модификацию отдельных (уже определенных) столбцов таблицы T, оставив привилегию на модификацию всех остальных столбцов (включая те, которые еще не созданы).
И последнее замечание. Если некоторая привилегия была передана псевдоauthID PUBLIC, то, конечно, этой привилегией обладают все authID. Но нет возможности аннулировать такую привилегию у отдельно указываемого authID. Привилегия была передана всем, и аннулировать ее можно только сразу у всех.
Аннулирование привилегий и ролей
Если от имени некоторого authID некоторые привилегии или роли были переданы одному или нескольким другим authID, то впоследствии первый authID (в сессии, где этот authID является текущим) можно изъять, или аннулировать, переданные привилегии или роли путем применения оператора REVOKE. Как и в случае передачи привилегий и ролей, способы аннулирования привилегий и ролей похожи, но между ними имеются некоторые отличия. Поэтому мы снова обсудим эти способы в отдельности.
Аннулирование ролей
Вариант оператора REVOKE, используемый для аннулирования ролей, выглядит следующим образом:
REVOKE [ ADMIN OPTION FOR ] role_name_commalist FROM { PUBLIC | authID_commalist } [ GRANTED BY { CURRENT_USER | CURRENT_ROLE } ] { RESTRICT | CASCADE }
Действие операции аннулирования ролей очень похоже на действие операции аннулирования привилегий. Отличие состоит в том, что аннулируются не привилегии, а роли, а также в том, что для аннулирования привилегии на передачу роли используется раздел ADMIN OPTION FOR.
Кстати, это один из тех случаев, когда иметь право не означает автоматически иметь возможность реализации своего права. SQL допускает, например, наличие привилегии INSERT для представления, к которому операция INSERT не применима.
Кстати, стандарт полностью отдает на волю реализации способ того, каким образом сделать неопределенным значение текущего пользовательского идентификатора SQL-сессии.
В действительности, как видно из приведенных описаний, варианты операторов GRANT и REVOKE для привилегий и ролей настолько близки, что непонятно их синтаксическое разделение, которое, очевидно, усложняет реализацию. Как кажется, это разделение не обосновано в стандарте SQL:1999.
Аномалии обновлений при наличии многозначных зависимостей и возможная декомпозиция
В новом варианте переменной отношения единственным возможным ключом является заголовок отношения {СЛУ_НОМ, ПРО_НОМ, СЛУ_ЗАДАН}. Кортеж {сн, пн, сз} входит в тело отношения в том и только в том случае, когда служащий с номером сн выполняет в проекте пн задание сз. Поскольку для каждого служащего указываются все проекты, в которых он участвует, и все задания, которые он должен выполнять в этих проектах, для каждого допустимого значения переменной отношения СЛУЖ_ПРО_ЗАДАН должно выполняться следующее ограничение (BСПЗ обозначает тело отношения):
IF ({сн, пн1, сз1}
Наличие такого ограничения (как мы скоро увидим, это ограничение порождается наличием многозначной зависимости) приводит к тому, что при работе с отношением СЛУЖ_ПРО_ЗАДАН проявляются аномалии обновления. Добавление кортежа. Если уже участвующий в проектах служащий присоединяется к новому проекту, то к телу значения переменной отношения СЛУЖ_ПРО_ЗАДАН требуется добавить столько кортежей, сколько заданий выполняет этот служащий.Удаление кортежей. Если служащий прекращает участие в проектах, то отсутствует возможность сохранить данные о заданиях, которые он может выполнять.Модификация кортежей. При изменении одного из заданий служащего необходимо изменить значение атрибута СЛУ_ЗАДАН в стольких кортежах, в скольких проектах участвует служащий.
Трудности, связанные с обновлением переменной отношения СЛУЖ_ПРО_ЗАДАН, решаются путем его декомпозиции на две переменных отношений: СЛУЖ_ПРО_НОМ {СЛУ_НОМ, ПРО_НОМ} и СЛУЖ_ЗАДАНИЕ {СЛУ_НОМ, СЛУ_ЗАДАН}. Значения этих переменных отношений, соответствующие значению переменной отношения СЛУЖ_ПРО_ЗАДАН с , показаны на .
Легко видеть, что декомпозиция, представленная на , является декомпозицией без потерь и что эта декомпозиция решает перечисленные выше проблемы с обновлением переменной отношения СЛУЖ_ПРО_ЗАДАН.
Рис. 9.2. Значения переменных отношений СЛУЖ_ПРО_НОМ и СЛУЖ_ЗАДАНИЕ Добавление кортежа. Если некоторый уже участвующий в проектах служащий присоединяется к новому проекту, то к телу значения переменной отношения СЛУЖ_ПРО_НОМ требуется добавить один кортеж, соответствующий новому проекту.Удаление кортежей. Если служащий прекращает участие в проектах, то данные о заданиях, которые он может выполнять, остаются в отношении СЛУЖ_ЗАДАНИЕ.Модификация кортежей. При изменении одного из заданий служащего необходимо изменить значение атрибута СЛУ_ЗАДАН в одном кортеже отношения СЛУЖ_ЗАДАНИЕ.
Аномалии обновлений, связанные с наличием перекрывающихся возможных ключей
Например, пусть имеется переменная отношения СЛУЖ_ПРО_ЗАДАН1 {СЛУ_НОМ, СЛУ_ИМЯ, ПРО_НОМ, СЛУ_ЗАДАН} с множеством FD, показанным на .
Рис. 8.7. Диаграмма FD отношения СЛУЖ_ПРО_ЗАДАН1
В отношении СЛУЖ_ПРО_ЗАДАН1 служащие уникально идентифицируются как по номерам удостоверений, так и по именам. Следовательно, существуют FD СЛУ_НОМ
Рис. 8.8. Возможное значение переменной отношения СЛУЖ_ПРО_ЗАДАН1
Очевидно, что, хотя в отношении СЛУЖ_ПРО_ЗАДАН1 все FD неключевых атрибутов от возможных ключей являются минимальными и транзитивные FD отсутствуют, этому отношению свойственны аномалии обновления. Например, в случае изменения имени служащего требуется обновить атрибут СЛУ_ИМЯ во всех кортежах отношения СЛУЖ_ПРО_ЗАДАН1, соответствующих данному служащему. Иначе будет нарушена FD СЛУ_НОМ
Аномалии обновлений, возникающие из-за наличия транзитивных функциональных зависимостей
Функциональные зависимости переменной отношения СЛУЖ по-прежнему порождают некоторые аномалии обновления. Они вызываются наличием транзитивной FD СЛУ_НОМ
Аномалии обновления, возникающие из-за наличия неминимальных функциональных зависимостей
Во множество FD отношения СЛУЖАЩИЕ_ПРОЕКТЫ_ЗАДАНИЯ входит много FD, в которых детерминантом является не возможный ключ отношения (соответствующие стрелки в диаграмме начинаются не с {СЛУ_НОМ, ПРО_НОМ}, т. е. некоторые функциональные зависимости атрибутов от возможного ключа не являются минимальными). Это приводит к так называемым аномалиям обновления. Под аномалиями обновления понимаются трудности, с которыми приходится сталкиваться при выполнении операций добавления кортежей в отношение (INSERT), удаления кортежей (DELETE) и модификации кортежей (UPDATE). Обсудим сначала аномалии обновления, вызываемые наличием FD СЛУ_НОМ
Аномалии, вызываемые наличием зависимости проекции/соединения
В переменной отношения СЛУЖ_ПРО_ЗАДАН выполняется PJD *({СЛУ_НОМ, ПРО_НОМ}, {ПРО_НОМ, СЛУ_ЗАДАН}, {СЛУ_НОМ, СЛУ_ЗАДАН}). Наличие такой PJD обеспечивает возможность декомпозиции отношения на три проекции, но возникает вопрос, зачем это нужно? Чем плохо исходное отношение СЛУЖ_ПРО_ЗАДАН? Ответ обычный: этому отношению свойственны аномалии обновления. Для примера предположим, что значением СЛУЖ_ПРО_ЗАДАН является отношение, показанное на .
Добавление кортежей. Если к ТСПЗ1 () добавляется кортеж <2941, 1, A>, то должен быть добавлен и кортеж <2934, 1, A>. Действительно, в теле отношения появятся кортежи <2934, 1, B>, <2941, 1, A> и <2934, 2, A>. Ограничение целостности требует включения и кортежа <2934, 1, A>. Интересно, что добавление кортежа <2934, 1, A> не нарушает ограничение целостности и, тем самым, не требует добавления кортежа <2941, 1, A>.
Рис. 9.4. Иллюстрации аномалий обновления в отношении СЛУЖ_ПРО_ЗАДАН при наличии зависимости соединенияУдаление кортежа. Если из ТСПЗ2 удаляется кортеж <2934, 1, A>, то должен быть удален и кортеж <2941, 1, A>, поскольку в соответствии с ограничением целостности наличие второго кортежа означает наличие первого. Интересно, что удаление кортежа <2941, 1, A> не нарушает ограничения целостности и не требует дополнительных удалений.
Анонимные строчные типы
Анонимный строчный тип – это конструктор типов ROW, позволяющий производить безымянные типы строк (кортежей). Любой возможный строчный тип получается путем использования конструктора ROW. При определении столбца, значения которого должны принадлежать некоторому строчному типу, используется конструкция ROW (fld1, fld2, ѕ, fldn ), где каждый элемент fldi, определяющий поле строчного типа, задается в виде тройки fldname, fldtype, fldoptions. Подэлемент fldname задает имя соответствующего поля строчного типа. Подэлемент fldtype специфицирует тип данных этого поля. В качестве типа данных поля строчного типа можно использовать любой допустимый в SQL тип данных, включая типы коллекций, определяемые пользователями типы и другие строчные типы. Необязательный подэлемент fldoptions может задаваться для указания применяемого по умолчанию порядка сортировки, если соответствующий подэлемент fldtype указывает на тип символьных строк, а также должен задаваться, если fldtype указывает на ссылочный тип (см. ниже). Степенью строчного типа называется число его полей.
Атомарность транзакций
В этом смысле под транзакцией понимается неделимая с точки зрения воздействия на БД последовательность операторов манипулирования данными (чтения, удаления, вставки, модификации), такая, что либо результаты всех операторов, входящих в транзакцию, отображаются в состоянии базы данных, либо воздействие всех этих операторов полностью отсутствует.
Лозунгом транзакции является «Все или ничего»: при завершении транзакции оператором COMMIT
(высокоуровневый аналог операции END TRANSACTION
в интерфейсе RSS, см. лекцию 12) результаты гарантированно фиксируются во внешней памяти (смысл термина commit
состоит в запросе «фиксации» результатов транзакции); при завершении транзакции оператором ROLLBACK
(высокоуровневый аналог операции RESTORE
в интерфейсе RSS, см. лекцию 12) результаты гарантированно отсутствуют во внешней памяти (смысл термина rollback
состоит в запросе ликвидации результатов транзакции).
Каким образом в СУБД поддерживаются индивидуальные откаты транзакций, описывается в лекции 14.
Атомарность значений атрибутов, первая нормальная форма отношения
Значения всех атрибутов являются атомарными (вернее, скалярными). Это следует из определения домена как потенциального множества значений скалярного типа данных, т. е. среди значений домена не могут содержаться значения с видимой структурой, в том числе множества значений (отношения). Заметим, что это не противоречит тому, что говорилось в разделе о потенциальной возможности использования при спецификации атрибутов типов данных, определяемых пользователями. Например, можно было бы добавить в схему отношения СЛУЖАЩИЕ атрибут СЛУ_ФОТО, определенный на домене (или типе данных) ФОТОГРАФИИ. Главное в атомарности значений атрибутов состоит в том, что реляционная СУБД не должна обеспечивать пользователям явной видимости внутренней структуры значения. Со всеми значениями можно обращаться только с помощью операций, определенных в соответствующем типе данных.
Принято говорить, что в реляционных базах данных допускаются только нормализованные отношения, или отношения, представленные в первой нормальной форме.
Пример ненормализованного отношения показан на . Можно сказать, что здесь мы имеем бинарное отношение, в котором значениями атрибута ОТДЕЛЫ являются отношения. Заметим, что исходное отношение СЛУЖАЩИЕ является нормализованным вариантом отношения ОТДЕЛЫ-СЛУЖАЩИЕ. Нормализованный вариант показан на .
Нормализованные отношения составляют основу классического реляционного подхода к организации баз данных. Они обладают некоторыми ограничениями (не всякую информацию удобно представлять в виде плоских таблиц), но существенно упрощают манипулирование данными. Рассмотрим, например, два идентичных оператора занесения кортежа: зачислить служащего Кузнецова (пропуск номер 3000, зарплата 25000.00) в отдел номер 320;зачислить служащего Кузнецова (пропуск номер 3000, зарплата 25000.00) в отдел номер 310.
Рис. 3.2. Ненормализованное отношение ОТДЕЛЫ-СЛУЖАЩИЕ
Рис. 3.3. Отношение СЛУЖАЩИЕ: нормализованный вариант отношения ОТДЕЛЫ-СЛУЖАЩИЕ
Если информация о служащих представлена в виде отношения СЛУЖАЩИЕ, оба оператора будут выполняться одинаково (вставить кортеж в отношение СЛУЖАЩИЕ).
Если же работать с ненормализованным отношением ОТДЕЛЫ-СЛУЖАЩИЕ, то первый оператор приведет к простой вставке кортежа, а второй – к добавлению кортежа в значение-отношение атрибута ОТДЕЛ кортежа с первичным ключом 310.
При работе с ненормализованными отношениями аналогичные затруднения возникают при выполнении операций удаления и модификации кортежей.
В лекции 16 мы обсудим различия между первичными и возможными ключами в языке SQL.
Если он является сторонником классического реляционного подхода; в языке SQL допускается определение таблиц без первичного и возможных ключей.
Кстати, заметим, что в классической реляционной модели, если при определении переменной отношения явно не указывается ее первичный ключ, то по умолчанию первичным ключом считается полный набор атрибутов заголовка отношения. Конечно, в этом случае такая переменная отношения может принимать любое значение-отношение, соответствующее заголовку, и первичный ключ не играет роль ограничения.
Эти ограничения все более ослабляются в последовательности стандартов языка SQL.
Авторизация доступа к файлам
Поскольку файловая система является общим хранилищем файлов, принадлежащих, вообще говоря, разным пользователям, системы управления файлами должны обеспечивать авторизацию доступа к файлам. В общем виде подход состоит в том, что по отношению к каждому зарегистрированному пользователю данной вычислительной системы для каждого существующего файла указываются действия, которые разрешены или запрещены данному пользователю (так называемый мандатный способ защиты – каждый пользователь имеет отдельный мандат для работы с каждым файлом или не имеет его). Применение мандатного способа защиты влечет за собой существенные накладные расходы, связанные с потребностью хранения избыточной информации и использованием этой информации для проверки правомочности доступа.
Поэтому в большинстве современных систем управления файлами применяется подход к защите файлов, впервые реализованный в ОС UNIX (так называемый дискреционный подход). В этой системе каждому зарегистрированному пользователю соответствует пара целочисленных идентификаторов: идентификатор группы, к которой относится пользователь, и его собственный идентификатор. Этими же идентификаторами снабжается каждый процесс, запущенный от имени данного пользователя и имеющий возможность обращаться к системным вызовам файловой системы. Соответственно, при каждом файле хранится полный идентификатор пользователя (собственный идентификатор плюс идентификатор группы), который создал этот файл, и помечается, какие действия с файлом может производить он сам, какие действия с файлом доступны для остальных пользователей той же группы и что могут делать с файлом пользователи других групп. Для каждого файла контролируется возможность выполнения трех действий: чтение, запись и выполнение. Хранимая информация очень компактна (два целых числа для представления идентификаторов и шкала из 9 бит для характеристики возможных действий), при проверке требуется небольшое количество действий, и этот способ контроля доступа в большинстве случаев удовлетворителен.
B+-деревья
Наиболее популярным подходом к организации индексов в базах данных является использование техники B+-деревьев. Техника B- и B+-деревьев была предложена в начале 1970-х гг. Рудольфом Байером (Rudolf Bayer) и Эдом Маккрейтом (Ed McCreight) . С точки зрения внешнего логического представления B-дерево – это сбалансированное сильно ветвистое дерево во внешней памяти. Сбалансированность означает, что длина пути от корня дерева к любому его листу одна и та же. Ветвистость дерева – это свойство каждого узла дерева ссылаться на большое число узлов-потомков. С точки зрения физической организации B-дерево представляется как мультисписочная структура страниц внешней памяти, т.е. каждому узлу дерева соответствует блок внешней памяти (страница). В B+-дереве внутренние и листовые страницы обычно имеют разную структуру.
Типовая структура внутренней страницы B+-дерева показана на рис. 12.2.
Рис. 12.2. Типовая структура внутренней страницы B+-дерева
При этом выдерживаются следующие свойства:
ключ1
ключ2
...
ключm;
в странице дерева Nm
находятся ключи k
со значениями ключm
<= k <= ключm+1.
Листовая страница обычно имеет следующую структуру, показанную на рис. 12.3.
Рис. 12.3. Структура листовой страницы B+-дерева
Листовая страница обладает следующими свойствами:
ключ1
< ключ2
< ... < ключk;
списокr
– упорядоченный список идентификаторов кортежей (tid), включающих значение ключr;
листовые страницы связаны одно- или двунаправленным списком.
Поиск в B+-дереве – это прохождение от корня к листу в соответствии с заданным значением ключа. Заметим, что поскольку B+-деревья являются сильно ветвистыми и сбалансированными, для выполнения поиска по любому значению ключа потребуется одно и то же (и обычно небольшое) число обменов с внешней памятью. Более точно, в сбалансированном дереве, где длины всех путей от корня к листу одни и те же, если во внутренней странице помещается n
ключей, то при хранении m
записей требуется дерево глубиной logn(m).
Если n достаточно велико (обычный случай), то глубина дерева невелика, и производится быстрый поиск.
Основной «изюминкой» B+- деревьев является автоматическое поддержание свойства сбалансированности. Рассмотрим, как это делается при выполнении операций занесения и удаления записей.
При занесение новой записи выполняются следующие действия.
Поиск листовой страницы. Фактически, производится обычный поиск по ключу. Если в B+-дереве не содержится ключ с заданным значением, то будет получен номер страницы, в которой ему надлежит содержаться, и соответствующие координаты внутри страницы.
Помещение записи на место. Естественно, что вся работа производится в буферах оперативной памяти. Листовая страница, в которую требуется занести запись, считывается в буфер, и в нем выполняется операция вставки. Размер буфера должен превышать размер страницы внешней памяти.
Если после выполнения вставки новой записи размер используемой части буфера не превосходит размера страницы, то на этом выполнение операции занесения записи заканчивается. Буфер может быть немедленно вытолкнут во внешнюю память или временно сохранен в основной памяти в зависимости от политики управления буферами.
Если же возникло переполнение буфера (т.е. размер его используемой части превосходит размер страницы), то выполняется расщепление страницы. Для этого запрашивается новая страница внешней памяти, используемая часть буфера разбивается примерно пополам (так, чтобы вторая половина также начиналась с ключа), и вторая половина записывается во вновь выделенную страницу, а в старой странице модифицируется значение размера свободной памяти. Естественно, модифицируются ссылки по списку листовых страниц.
Чтобы обеспечить доступ от корня дерева к заново заведенной странице, необходимо соответствующим образом модифицировать внутреннюю страницу, являющуюся предком ранее существовавшей листовой страницы, т.е. вставить в нее соответствующее значение ключа и ссылку на новую страницу. При выполнении этого действия может снова произойти переполнение теперь уже внутренней страницы, и она будет расщеплена на две.
В результате потребуется вставить значение ключа и ссылку на новую страницу во внутреннюю страницу-предка выше по иерархии и т.д.
Предельным случаем является переполнение корневой страницы B+-дерева. В этом случае она тоже расщепляется на две, и заводится новая корневая страница дерева, т.е. его глубина увеличивается на единицу.
При удалении записи выполняются следующие действия.
Поиск записи по ключу. Если запись не найдена, то удалять ничего не нужно.
Реальное удаление записи в буфере, в который прочитана соответствующая листовая страница.
Если после выполнения этой подоперации размер занятой в буфере области оказывается таковым, что его сумма с размером занятой области в листовых страницах, являющихся левым или правым братом данной страницы, больше, чем размер страницы, операция завершается.
Иначе производится слияние с правым или левым братом, т.е. в буфере производится новый образ страницы, содержащей общую информацию из данной страницы и ее левого или правого брата. Ставшая ненужной листовая страница заносится в список свободных страниц. Соответствующим образом корректируется список листовых страниц.
Чтобы устранить возможность доступа от корня к освобожденной странице, нужно удалить соответствующее значение ключа и ссылку на освобожденную страницу из внутренней страницы – ее предка. При этом может возникнуть потребность в слиянии этой страницы с ее левым или правым братом и т.д.
Предельным случаем является полное опустошение корневой страницы дерева, которое возможно после слияния последних двух потомков корня. В этом случае корневая страница освобождается, а глубина дерева уменьшается на единицу.
Как видно, при выполнении операций вставки и удаления свойство сбалансированности B+-дерева сохраняется, а внешняя память расходуется достаточно экономно.
Проблемой является то, что при выполнении операций модификации слишком часто могут возникать расщепления и слияния. Чтобы добиться эффективного использования внешней памяти с минимизацией числа расщеплений и слияний, применяются более сложные приемы, в том числе:
упреждающие расщепления, т.е. расщепления страницы не при ее переполнении, а несколько раньше, когда степень заполненности страницы достигает некоторого уровня;
переливания, т.е. поддержание равновесного заполнения соседних страниц;
слияния 3-в-2, т.е. порождение двух листовых страниц на основе содержимого трех соседних.
Следует заметить, что при организации мультидоступа к B+-деревьям, характерного при их использовании в СУБД, приходится решать ряд нетривиальных проблем. Конечно, грубые решения очевидны, например, возможен монопольный захват B+-дерева (т.е. его корневого блока) на все выполнение операции модификации. Но существуют и более тонкие решения, рассмотрение которых выходит за пределы материала этой книги.
Базовые операции Алгебры A
Материал этой лекции излагается на несколько более формальном уровне, чем в предыдущих лекциях. Используемые понятия определяются, по существу, так же, как и в лекции 3, но для удобства и обеспечения точности изложения мы повторим определения.
Пусть r – отношение, A – имя атрибута отношения r, T – имя соответствующего типа (т. е. типа или домена атрибута A), v – значение типа T. Тогда: заголовком Hr отношения r называется множество атрибутов, т.е. упорядоченных пар вида <A, T>. По определению никакие два атрибута в этом множестве не могут содержать одно и то же имя атрибута A;кортеж tr, соответствующий заголовку Hr, – это множество упорядоченных триплетов вида <A, T, v>, по одному такому триплету для каждого атрибута в Hr;тело Br отношения r – это множество кортежей tr. Заметим, что (в общем случае) могут существовать такие кортежи tr, которые соответствуют Hr, но не входят в Br.
Заметим, что заголовок – это множество (упорядоченных пар вида <A, T>), тело – это множество (кортежей tr), и кортеж – это множество (упорядоченных триплетов вида <A, T, v>). Элемент заголовка – это атрибут (т. е. упорядоченная пара вида <A,T>); элемент тела – это кортеж; элемент кортежа – это упорядоченный триплет вида <A, T, v>. Любое подмножество заголовка – это заголовок, любое подмножество тела – это тело, и любое подмножество кортежа – это кортеж.
Определим несколько основных операций (как будет показано далее, некоторые из них избыточны). Каждое из последующих определений состоит из: формальной спецификации ограничений (если они имеются), применимых к операндам соответствующей операции; формальной спецификации заголовка результата этой операции; формальной спецификации тела этого результата и неформального обсуждения формальных спецификаций.
Во всех формальных спецификациях exists обозначает квантор существования; exists tr означает «существует такой tr, что». Символ «
Поскольку некоторые базовые операции Алгебры A имеют названия обычных логических операций, чтобы избежать путаницы, имена реляционных операций берутся в угловые скобки: <NOT>, <AND>, <OR> и т. д. В исходный базовый набор операций входят операции реляционного дополнения <NOT>, удаления атрибута <REMOVE>, переименования атрибута <RENAME>, реляционной конъюнкции <AND> и реляционной дизъюнкции <OR>.
Базовые приемы
Каждый простой тип сущности превращается в таблицу. (Простым типом сущности называется тип сущности, не являющийся подтипом и не имеющий подтипов.) Имя сущности становится именем таблицы. Экземплярам типа сущности соответствуют строки соответствующей таблицы.
Каждый атрибут становится столбцом таблицы с тем же именем; может выбираться более точный формат представления данных. Столбцы, соответствующие необязательным атрибутам, могут содержать неопределенные значения; столбцы, соответствующие обязательным атрибутам, – не могут.
Компоненты уникального идентификатора сущности превращаются в первичный ключ таблицы. Если имеется несколько возможных уникальных идентификаторов, для первичного ключа выбирается наиболее характерный. Если в состав уникального идентификатора входят связи, к числу столбцов первичного ключа добавляется копия уникального идентификатора сущности, находящейся на дальнем конце связи (этот процесс может продолжаться рекурсивно, и в общем случае может привести к зацикливанию). Для именования этих столбцов используются имена концов связей и/или имена парных типов сущностей.
Связи «многие к одному» (и «один к одному») становятся внешними ключами, т. е. образуется копия уникального идентификатора сущности на конце связи «один», и соответствующие столбцы составляют внешний ключ таблицы, соответствующей типу сущности на конце связи «многие». Необязательные связи соответствуют столбцам внешнего ключа, допускающим наличие неопределенных значений; обязательные связи – столбцам, не допускающим неопределенных значений. Если между двумя типами сущности A и B имеется связь «один к одному», то соответствующий внешний ключ по желанию проектировщика может быть объявлен как в таблице A, так и в таблице B. Чтобы отразить в определении таблицы ограничение, которое заключается в том, что степень конца связи должна равняться единице, соответствующий (возможно, составной) столбец должен быть дополнительно специфицирован как возможный ключ таблицы (в случае использования языка SQL для этого служит спецификация UNIQUE – см.
лекцию 16).
Для поддержки связи « многие ко многим» между типами сущности A и B создается дополнительная таблица AB с двумя столбцами, один из которых содержит уникальные идентификаторы экземпляров сущности A, а другой – уникальные идентификаторы экземпляров сущности B. Обозначим через УИД(с) уникальный идентификатор экземпляра с некоторого типа сущности C. Тогда, если в экземпляре связи «многие ко многим» участвуют экземпляры a1, a2, ..., an типа сущности A и экземпляры b1, b2, ..., bm типа сущности B, то в таблице AB должны присутствовать все строки вида {УИД(ai), УИД(bj)} для i = 1, 2, ..., nn, j = 1, 2, ..., m. Понятно, что, используя таблицы A, B и AB, с помощью стандартных реляционных операций можно найти все пары экземпляров типов сущности, участвующих в данной связи.
Индексы создаются для первичного ключа (уникальный индекс), внешних ключей и тех атрибутов, на которых предполагается в основном базировать запросы.
Базовые средства манипулирования данными
К базовым средствам манипулирования данными языка SQL относятся «поисковые» варианты операторов UPDATE и DELETE. Эти варианты называются поисковыми, потому что при задании соответствующей операции задается логическое условие, налагаемое на строки адресуемой оператором таблицы, которые должны быть подвергнуты модификации или удалению. Кроме того, в такую категорию языковых средств входит оператор INSERT, позволяющий добавлять строки в существующие таблицы. Логично начать изложение именно с оператора INSERT, поскольку, для того чтобы можно было что-либо модифицировать в таблицах или удалять из таблиц, нужно, чтобы в таблицах содержались какие-то строки.
Более сложные элементы ER-модели
До сих пор мы рассматривали только самые основные и наиболее очевидные понятия ER-модели данных. К числу некоторых более сложных элементов модели относятся следующие. Подтипы и супертипы сущностей. Подобно тому как это делается в языках программирования с развитыми типовыми системами (например, в языках объектно-ориентированного программирования), в ER-модели поддерживается возможность определения нового типа сущности путем наследования некоторого супертипа сущности. Механизм наследования в ER-модели обладает несколькими особенностями: в частности, интересные нюансы связаны с необходимостью графического изображения этого механизма (см. ниже). Уточняемые степени связи. Иногда бывает полезно определить возможное количество экземпляров сущности, участвующих в данной связи (например, ввести ограничение, связанное с тем, что служащему разрешается участвовать не более чем в трех проектах одновременно). Для выражения этого семантического ограничения разрешается указывать на конце связи ее максимально допустимую или обязательную степень. Взаимно исключающие связи. Для заданного типа сущности можно определить такой набор типов связи с другими типами сущности, что для каждого экземпляра заданного типа сущности может (если набор связей является необязательным) или должен (если набор связей обязателен) существовать экземпляр только одной связи из этого набора.Каскадные удаления экземпляров сущностей. Некоторые связи бывают настолько сильными (конечно, в случае связи «один ко многим»), что при удалении опорного экземпляра сущности (соответствующего концу связи «один») нужно удалить и все экземпляры сущности, соответствующие концу связи «многие». Соответствующее требование каскадного удаления можно специфицировать при определении связи. Домены. Как и в случае реляционной модели данных, в некоторых случаях полезна возможность определения потенциально допустимого множества значений атрибута сущности (домена).
Эти и другие усложненные элементы модели данных «Сущность-Связь» делают ее более мощной, но одновременно несколько затрудняют ее использование. Конечно, при реальном применении ER-диаграмм для проектирования баз данных необходимо ознакомиться со всеми возможностями. Ниже мы подробнее обсудим два элемента из числа упомянутых выше – супертипы и подтипы сущности, а также приведем пример сущности с взаимно исключающими связями.
Более сложные конструкции оператора выборки
В этом разделе мы обсудим возможности языка SQL, касающиеся явного задания выражений с соединениями и порождаемых таблиц с горизонтальной связью (lateral_derived_table). Начнем с соединений.
Буферизация блоков базы данных в основной памяти и ее связь с журнализацией
Журнализация операций изменения базы данных
тесно связана не только с управлением транзакциями, но и с буферизацией блоков базы данных в основной памяти. По причинам объективно существующей разницы в скорости работы процессоров и основной памяти и устройств внешней памяти (эта разница в скорости существовала, существует, и будет существовать всегда) буферизация блоков базы данных в основной памяти является единственным реальным способом достижения приемлемой эффективности СУБД. Без поддержки буферизации базы данных СУБД работала бы со скоростью магнитных дисков, т.е. на несколько порядков медленнее, чем если бы обработка данных происходила в основной памяти.
Если бы каждая запись об изменении базы данных, которая должна поступить в журнал при выполнении любой операции обновления базы данных, реально немедленно перемещалась бы во внешнюю память, это привело бы к существенному замедлению работы системы. Фактически, тогда каждая операция обновления базы данных выполнялась бы со скоростью магнитного диска. Поэтому записи в журнал тоже буферизуются: при нормальной работе буфер выталкивается во внешнюю память журнала только при полном заполнении записями. Более точно, для буферизации записей журнала обычно используются два буфера. После полного заполнения первый буфер выталкивается на магнитный диск, и пока совершается этот обмен, журнальные записи размещаются во втором буфере. К моменту конца обмена заполняется второй буфер, он выталкивается во внешнюю память, а журнальные записи снова размещаются в первом буфере и т.д.
Здесь следует заметить, что здесь идет речь об использовании буферов (и базы данных, и журнала), располагающихся именно в физической основной памяти, управляемой непосредственно СУБД, а не виртуальной памяти СУБД, управляемой операционной системой. Использование буферов виртуальной памяти является практически бессмысленным делом, поскольку в этом случае операционная система, руководствуясь своими собственными стратегиями управления основной памяти, в любой момент может удалить буферную страницу СУБД из основной памяти и перенести ее копию во внешнюю память в область свопинга. Тогда при следующей попытке записи СУБД в эту страницу возникнет прерывание, при обработке которого операционная система подкачает страницу в основную память, выполнив совершенно не ожидаемый СУБД обмен с внешней памятью.
Нельзя надеяться на то, что операционная система настолько грамотно управляет основной памятью, что нужные страницы виртуальной памяти СУБД в нужное время будут находиться в основной памяти. Операционная система просто не обладает достаточной информацией, чтобы всегда принимать правильные решения. Правильно управлять своей буферной памятью может только сама СУБД, «отбирающая» у операционной системы часть физической основной памяти для размещения в ней буферов базы данных и журнала.
Булевские выражения
К булевским выражениям относятся выражения, вырабатывающие значения булевского типа (напомним, что булевский тип языка SQL содержит три логических значения – true, false и unknown). Булевские выражения определяются следующими синтаксическими правилами:
boolean_value_expression ::= boolean_term | boolean_value_expression OR boolean_term boolean_term ::= boolean_factor | boolean_term AND boolean_factor boolean_factor ::= [ NOT ] boolean_test boolean_test ::= boolean_primary [ IS [ NOT ] truth_value ] truth_value ::= TRUE | FALSE | UNKNOWN boolean_primary ::= predicate | (boolean_value_expression) | value_expression_primary
Выражения вычисляются слева направо с учетом приоритетов операций (наиболее высокий приоритет имеет унарная операция NOT, следующим уровнем приоритета обладает «мультипликативная» операция конъюнкции AND, и самый низкий приоритет у «аддитивной» операции дизъюнкции OR) и круглых скобок. Операции IS и IS NOT определяются следующими таблицами истинности:
| TRUE | FALSE | FALSE |
| FALSE | TRUE | FALSE |
| FALSE | FALSE | TRUE |
| FALSE | TRUE | TRUE |
| TRUE | FALSE | TRUE |
| TRUE | TRUE | FALSE |
Булевский тип
При определении столбца булевского типа указывается просто спецификация BOOLEAN. Булевский тип состоит из трех значений: true, false и unknown (соответствующие литералы обозначаются TRUE, FALSE и UNKNOWN). Поддерживается возможность построения булевских выражений, которые вычисляются в трехзначной логике. Таблицы истинности основных логических операций показаны на .
Рис. 15.2. Таблицы истинности основных логических операций в трехзначной логике
Целевые списки и выражения реляционного исчисления
Итак, WFF обеспечивают средства формулировки условия выборки из отношений БД. Чтобы можно было использовать исчисление для реальной работы с БД, требуется еще один компонент, который определяет набор и имена атрибутов результирующего отношения. Этот компонент называется целевым списком (target list).
Целевой список строится из целевых элементов, каждый из которых может иметь следующий вид: var.attr, где var – имя свободной переменной соответствующей WFF, а attr – имя атрибута отношения, на котором определена переменная var;var, что эквивалентно наличию подсписка var.attr1, var.attr2, ..., var.attrn, где {attr1, attr2, ..., attrn} включает имена всех атрибутов определяющего отношения;new_name = var.attr; new_name – новое имя соответствующего атрибута результирующего отношения.
Последний вариант требуется в тех случаях, когда в WFF используется несколько свободных переменных с одинаковой областью определения. Фактически применение целевого списка к области истинности WFF эквивалентно действию алгебраической операции проекции, а последний из приведенных вариантов представляет собой некоторую разновидность алгебраической операции переименования атрибута.
Выражением реляционного исчисления кортежей называется конструкция вида target_list WHERE WFF. Значением выражения является отношение, тело которого определяется WFF, а множество атрибутов и их имена – целевым списком.
В качестве простого примера покажем выражение реляционного исчисления кортежей, результат которого совпадает с результатом операции СЛУЖАЩИЕ DIVIDE BY НОМЕРА_ПРОЕКТОВ ( из лекции 4):
СЛУ1, СЛУ2 RANGE IS СЛУЖАЩИЕ НОМЕР_ПРОЕКТА range is НОМЕРА_ПРОЕКТОВ СЛУ1.СЛУ_НОМЕР, СЛУ1.СЛУ_ИМЯ, СЛУ1.СЛУ_ЗАРП WHERE FORALL НОМЕР_ПРОЕКТА EXISTS СЛУ2 (СЛУ1.СЛУ_НОМЕР = СЛУ2.СЛУ_НОМЕР AND СЛУ1.ПРО_НОМ = НОМЕРА_ПРОЕКТОВ.ПРО_НОМ)
Конечно, результатом этого выражения является отношение
| 2934 | Иванов | 22400.00 |
| 2935 | Петров | 29600.00 |
Это совсем не означает, что для понимания этой лекции требуется знание исчисления предикатов. Автор стремился к тому, чтобы материал лекции был в основном самодостаточным.
Через IF … THEN здесь обозначается одна и важных логических функций – импликация. По определению, IF a THEN b эквивалентно NOT a OR b. Хотя операция импликации является избыточной, она явно вводится в реляционное исчисление, поскольку часто требуется на практике для выражения условий.
Упражнение для читателей. Почему в первой формуле (с EXISTS) использовано условие СЛУ1.СЛУ_ЗАР > СЛУ2.СЛУ_ЗАРП, а второй формуле (с FORALL) – СЛУ1.СЛУ_ЗАР
Цели лекции
Следует заметить, что в этой, безусловно, перегруженной материалом лекции мы преследуем две основные цели. Первая цель состоит в том, чтобы показать читателям, что в средствах определения структурных типов SQL используются, по сути, все базовые возможности определения объектов базы данных и выборки данных, которые обсуждались в предыдущих лекциях. Более того, определенные пользователями типы в SQL являются объектами первого класса; UDT можно использовать в любой конструкции языка, в которой допускается применение предопределенного или конструируемого типа данных. Очень важно отдавать себе отчет в том, что наличие возможности определять пользовательские типы не делает язык SQL менее реляционным или более объектным. Эта возможность «всего лишь» фантастически повышает выразительную мощность языка.
Второй целью является демонстрация того, как на основе базовых механизмов языка удалось ввести дополнительные конструкции, которые действительно вплотную приближают SQL к объектному миру. Здесь, конечно, основную роль играет связка UDT и механизма типизированных таблиц, которые играют в SQL своеобразную совмещенную роль классов и коллекций объектов.
Может оказаться, что материал этой лекции покажется сложным, поскольку для его усвоения не помешало бы иметь предварительную подготовку в области полнотиповых языков программирования, объектно-ориентированных языков и систем баз данных и т. д. Хочется надеяться, что возникновение трудностей при изучении лекции не отпугнет читателей от этой темы, а напротив, послужит стимулом к изучению дополнительной литературы.
Возможна и другая опасная ситуация. Краткость и некоторая формальность изложения может создать ложное впечатление тривиальности объектных расширений SQL. В этом случае могу посоветовать перечитать предыдущие лекции курса, относящиеся к SQL, считая, что везде, где используются предопределенные или конструируемые типы, применяются некоторые UDT, а в тех случаях, где имеются таблицы, связываемые естественным соединением, используются типизированные таблицы.
Думаю, это позволит оценить мощь новых возможностей SQL.
Введя этот необходимый контекст, перейдем к описанию соответствующих механизмов SQL:1999.
Вопросы интеграции данных выходят за пределы тематики этого курса. Однако следует сделать два замечания. Во-первых, проблематика обеспечения доступа к разнородным данным через некоторую глобальную, или концептуальную схему интересует сообщество баз данных в течение нескольких десятков лет. Существовали многочисленные попытки обеспечить интеграцию баз данных, представленных во всех возможных моделях (сетевой, иерархической, реляционной, объектно-ориентированной). С точки зрения теории решение проблемы возможно, но на практике это приводит к очень сложным с технической точки зрения реализациям, обладающим крайне низкой производительностью. Во-вторых, в MCC в 1980-е годы был создан весьма успешный прототип системы, интегрирующей SQL-ориентированные базы данных. Должно быть понятно, что такая интеграция существенно проще в техническом смысле, поскольку глобальная и фрагментарные схемы представлены в близких понятиях. Похоже, что проект UniSQL в большой степени базировался и на этой работе.
Компания Illustra была создана Стоунбрейкером для коммерциализации разработанной под его руководством свободно доступной СУБД Postgres.
Конечно, это не модель данных в смысле Кодда.
Далеко не факт, что ориентация на язык Java была правильным решением. По мнению автора данного курса, причиной являются отнюдь не уникальные достоинства языка Java (обсуждение этого языка не является задачей автора), а то, что во время разработки стандарта SQL:1999 язык Java был особенно моден. Помимо прочего, заметим, что для языка Java (насколько известно автору) никогда не определялась формальная объектная модель.
Цели System R и их связь с общей организацией системы
При выполнении проекта System R преследовались следующие основные цели:
обеспечить ненавигационный интерфейс высокого уровня пользователя с системой, позволяющий достичь независимости данных и дать возможность пользователям работать максимально эффективно;
обеспечить многообразие допустимых способов использования СУБД, включая программируемые транзакции, диалоговые транзакции и генерацию отчетов;
поддерживать динамически изменяемую среду баз данных, в которой таблицы, индексы, представления, транзакции и другие объекты могут легко добавляться и уничтожаться без приостановки нормального функционирования системы;
обеспечить возможность параллельной работы с одной базой данных многих пользователей, допуская параллельную модификацию объектов базы данных при наличии необходимых средств защиты целостности базы данных;
обеспечить средства восстановления согласованного состояния баз данных после разного рода сбоев аппаратуры или программного обеспечения;
обеспечить гибкий механизм, позволяющий определять различные представления хранимых данных и ограничивать этими представлениями доступ пользователей к базе данных по выборке и модификации на основе механизма авторизации;
обеспечить производительность системы при выполнении упомянутых функций, сопоставимую с производительностью существующих СУБД низкого уровня.
Прежде всего, отметим, что при разработке System R поставленные цели в основном были достигнуты. Рассмотрим теперь, какими средствами удалось достичь этих целей, и как можно более точно интерпретировать их в контексте System R.
Основой System R является «реляционный» язык SEQUEL (который достаточно быстро был переименован в SQL). Заметим, что разработчики System R искренне считали созданный ими язык реляционным; однако, как отмечалось в предыдущих лекциях и будет более детально показано в заключительных лекциях, в этом языке в действительности нарушаются многие важные принципы реляционной модели данных. Иногда его называют языком запросов или языком манипулирования данными, но на самом деле возможности SQL гораздо шире.
Средствами SQL ( с соответствующей системной поддержкой) решаются многие из поставленных целей. Язык SQL включает средства динамической компиляции запросов, на основе чего возможно построение диалоговых систем обработки запросов. Допускается динамическая параметризация статически откомпилированных запросов, в результате чего возможно построение эффективных (не требующих динамической компиляции) диалоговых систем со стандартными наборами (параметризуемых) запросов. Средствами SQL определяются все доступные пользователю объекты баз данных: таблицы, индексы, представления. Имеются средства уничтожения любого такого объекта. Соответствующие операторы языка могут выполняться в любой момент, и возможность выполнения операции данным пользователем зависит от ранее предоставленных ему прав.
Что касается целостности баз данных, то в System R под целостным состоянием базы данных понимается состояние, удовлетворяющее набору сохраняемых при базе данных предикатов целостности. Эти предикаты, называемые в System R утверждениями целостности
(assertion), также задаются средствами языка SQL. Любой оператор языка выполняется в границах некоторой транзакции
– последовательности операторов языка, неделимой в смысле состояния базы данных. Неделимость означает, что все изменения базы данных, произведенные в пределах одной транзакции, либо целиком отображаются в состоянии базы данных, либо полностью в нем отсутствуют. Последняя возможность возникает при откате
транзакции, который может произойти по инициативе пользователя (при выполнении соответствующего оператора SQL) или по инициативе системы.
Одной из причин отката транзакции по инициативе системы является как раз нарушение целостности базы данных в результате действий данной транзакции (другие возможные условия отката транзакции по инициативе системы мы рассмотрим позже). Язык SQL System R (так мы будем называть вариант языка SQL, разработанный в проекте System R, чтобы отличать его от более поздних, «стандартных» вариантов этого языка) содержит средство установки так называемых точек сохранения
(savepoint). При инициируемом пользователем откате транзакции можно указать номер точки сохранения, выше которого откат не распространяется. Инициируемый системой откат транзакции производится до ближайшей точки сохранения, в которой условие, вызвавшее откат, уже отсутствует. В частности, откат транзакции, инициированный по причине нарушения условия целостности, производится до ближайшей точки сохранения, в которой условия целостности соблюдены.
Естественно, что для реального выполнения отката транзакции необходимо запоминать некоторую информацию о выполнении транзакции. В System R для этих и других целей используется специальный набор данных – журнал, в который помещаются записи обо всех операциях всех транзакций, изменяющих состояние базы данных. При откате транзакции происходит процесс обратного выполнения
транзакции (undo), в ходе которого в обратном порядке выполняются все изменения, запомненные в журнале.
В языке SQL System R имеется средство определения так называемых триггеров
(trigger), позволяющих автоматически поддерживать целостность базы данных при модификациях ее объектов. В SQL System R триггер – это каталогизированная операция модификации, для которой задано условие ее автоматического выполнения. Особенно существенно наличие такого механизма в связи с наличием обсуждаемых ниже представлений базы данных, которыми может быть ограничен доступ к базе данных для ряда пользователей. Возможна ситуация, когда такие пользователи просто не могут соблюдать целостность базы данных без автоматического выполнения условных воздействий, поскольку они просто «не видят» всей базы данных и, в частности, не могут представить всех ограничений ее целостности.
Язык SQL содержит средства определения представлений. Представление – это каталогизированный именованный запрос на выборку данных (из одной или нескольких таблиц). Поскольку SQL – это «реляционный» язык, результатом выполнения любого запроса на выборку является таблица, и поэтому концептуально можно относиться к любому представлению как к таблице (при определении представления можно, в частности, присвоить имена полям этой таблицы).
В языке допускается использование ранее определенных представлений практически везде, где допускается использование таблиц (с некоторыми ограничениями по поводу возможностей модификации через представления). Наличие возможности определять представления в совокупности с развитой системой авторизации позволяет ограничить доступ некоторых пользователей к базе данных выделенным набором представлений.
Авторизация доступа к базе данных также основана на средствах SQL. При создании любого объекта базы данных пользователь, выполняющий эту операцию, становится полновластным владельцем этого объекта, т.е. может выполнять по отношению к этому объекту любую допустимую операцию SQL. Далее этот пользователь может выполнить оператор SQL, означающий передачу всех его прав на этот объект (или их подмножества) любому другому пользователю. В частности, этому пользователю может быть передано право на передачу всех переданных ему прав (или их части) третьему пользователю и т.д. Одним из прав пользователя по отношению к объекту является право на изъятие у других пользователей всех или некоторых прав, которые ранее им были переданы. Эта операция распространяется транзитивно на всех дальнейших наследников этих прав.
Наличие в языке средств определения представлений и авторизации в принципе позволяет обойтись при эксплуатации System R без традиционного администратора баз данных, поскольку практически все системные действия производятся на основе средств SQL. Тем не менее, если организационно администратор баз данных требуется, то его работа достаточно упрощается за счет унифицированного набора средств управления. Кроме того, в System R каталоги баз данных поддерживаются также в виде таблиц, и к ним применены все запросы языка SQL. Заметим, что в более поздних SQL-ориентированных СУБД появился ряд дополнительных утилит, не связанных с языком SQL (например, утилиты сбора статистики или массовой загрузки базы данных), и в этих системах, видимо, без администратора базы данных не обойтись.
По части обеспечения параллельной работы многих пользователей с одной базой данных, основной подход System R состоит в том, что пользователь не обязан знать о наличии других пользователей, конкурирующих с ним за доступ к базе данных, т.е.
система ответственна за обеспечение изолированности пользователей с гарантией отсутствия их взаимного влияния в пределах транзакций. Из этого следует, во-первых, что в интерфейсе пользователя с системой (т.е. в языке SQL) не должно быть средств регулирования взаимодействий с другими пользователями и, во-вторых, что система должна обеспечить автоматическую сериализацию набора транзакций, т.е. обеспечить режим выполнения этого набора транзакций, эквивалентный по конечному результату некоторому последовательному выполнению этих транзакций. Эта проблема решается в System R за счет автоматического выполнения синхронизационных блокировок всех изменяемых объектов базы данных.
Одним из основных требований к СУБД вообще и к System R в частности является обеспечение надежности баз данных по отношению к различного рода сбоям. К таким сбоям могут относиться программные ошибки прикладного и системного уровня, сбои процессора, поломки внешних носителей и т.д. В частности, к одному из видов сбоев можно отнести упоминавшиеся выше нарушения целостности базы данных и автоматический инициируемый системой откат транзакции – это системное средство восстановления базы данных после сбоев такого рода. Как уже отмечалось, такое восстановление происходит путем обратного выполнения транзакции на основе информации о внесенных ею изменениях, запомненной в журнале. На информации журнала также основано восстановление базы данных и после сбоев другого рода.
Что касается естественных требований к эффективности системы, то здесь основные решения связаны со спецификой физической организации баз данных во внешней памяти, использованием техники индексированного доступа к данным, буферизацией используемых страниц базы данных в основной памяти и развитой техникой оптимизации SQL-запросов, производимой на стадии их компиляции.
Структурная организация System R согласуется с поставленными при ее разработке целями и выбранными решениями. Основными структурными компонентами System R являются система управления реляционными данными (Relational Data System – RDS), состоящая, по существу, из компилятора языка SQL и подсистемы поддержки откомпилированных операторов, и система управления реляционной памятью (Relational Storage System – RSS).
RSS обеспечивает интерфейс довольно низкого, но достаточного для реализации SQL уровня для доступа к хранимым в базе данным (этот внутренний интерфейс System R напоминает внешний интерфейс систем, основанных на модели инвертированных таблиц, см. лекцию 2; более подробно он описывается ниже). Синхронизация транзакций, журнализация изменений и восстановление баз данных после сбоев также относятся к числу функций RSS.
Компилятор запросов использует интерфейс RSS для доступа к разнообразной справочной информации (каталоги таблиц, индексов, прав доступа, условий целостности, условных воздействий и т.д.) и производит рабочие программы, выполняемые в дальнейшем также с использованием интерфейса RSS.
Таким образом, система естественно разделяется на два уровня – уровень управления памятью и синхронизацией, фактически, не зависящий от базового языка запросов системы, и языковый уровень (уровень SQL), на котором решается большинство проблем System R. Заметим, что эта независимость скорее условная, чем абсолютная: язык SQL можно в принципе заменить каким-либо другим языком, но он должен обладать примерно такой же семантикой.
Целостность данных
Теперь система должна «знать», что она работает с двумя информационно связанными файлами (это шаг в сторону схемы базы данных), должна иметь информацию о структуре и смысле каждого поля. Например, системе должно быть известно, что у полей СЛУ_ОТД_НОМЕР в файле СЛУЖАЩИЕ и ОТД_НОМЕР в файле ОТДЕЛЫ один и тот же смысл – номер отдела.
Кроме того, система должна учитывать, что в ряде случаев изменение данных в одном файле должно автоматически вызывать модификацию второго файла, чтобы общее содержимое файлов было согласованным. Например, если на работу принимается новый служащий, то нужно добавить запись в файл СЛУЖАЩИЕ, а также должным образом изменить поля ОТД_СЛУ_ЗАРП и ОТД_РАЗМЕР в записи файла ОТДЕЛЫ, соответствующей отделу этого служащего. Более точно, система должна руководствоваться следующими правилами: если в файле СЛУЖАЩИЕ содержится запись со значением поля СЛУ_ОТД_НОМЕР, равным n, то и в файле ОТДЕЛЫ должна содержаться запись со значением поля ОТД_НОМЕР, также равным n;если в файле ОТДЕЛЫ содержится запись со значением поля ОТД_РУК, равным m, то и в файле СЛУЖАЩИЕ должна содержаться запись со значением поля СЛУ_НОМЕР, также равным m; в следующих лекциях мы увидим, что правила (1) и (2) являются частными случаями общего правила ссылочной целостности: поле СЛУ_ОТД_НОМЕР содержит «ссылки» на записи таблицы ОТДЕЛЫ, и поле ОТД_РУК содержит «ссылки» на записи таблицы СЛУЖАЩИЕ;при любом корректном состоянии информационной системы значение поля ОТД_СЛУ_ЗАРП любой записи отд_k файла ОТДЕЛЫ должно быть равно сумме значений поля СЛУ_ЗАРП всех тех записей файла СЛУЖАЩИЕ, в которых значение поля СЛУ_ОТД_НОМЕР совпадает со значением поля ОТД_НОМЕР записи отд_k;при любом корректном состоянии информационной системы значение поля ОТД_РАЗМЕР любой записи отд_k файла ОТДЕЛЫ должно быть равно числу всех тех записей файла СЛУЖАЩИЕ, в которых значение поля СЛУ_ОТД_НОМЕР совпадает со значением поля ОТД_НОМЕР записи отд_k; в следующих лекциях мы увидим, что правила (3) и (4) представляют собой примеры общих ограничений целостности базы данных.
Понятие согласованности, или целостности, данных является ключевым понятием баз данных. Фактически, если информационная система (даже такая простая, как в нашем примере) поддерживает согласованное хранение данных в нескольких файлах, можно говорить о том, что она поддерживает базу данных (БД). Если же некоторая вспомогательная система управления данными позволяет работать с несколькими файлами, обеспечивая их согласованность, можно назвать ее системой управления базами данных (СУБД).
Уже только требование поддержания согласованности данных в нескольких файлах не позволяет при построении информационной системы обойтись библиотекой функций: такая система должна обладать некоторыми собственными данными (их принято называть метаданными), определяющими целостность данных. В нашем примере информационная система должна отдельно сохранять метаданные о структуре файлов СЛУЖАЩИЕ и ОТДЕЛЫ, а также правила, определяющие условия целостности данных в этих файлах (принято считать, что правила также составляют часть метаданных).
Целостность сущности и ссылок
Наконец, в целостной части реляционной модели данных фиксируются два базовых требования целостности, которые должны поддерживаться в любой реляционной СУБД. Первое требование называется требованием целостности сущности (entity integrity). Объекту или сущности реального мира в реляционных БД соответствуют кортежи отношений. Конкретно требование состоит в том, что любой кортеж любого значения-отношения любой переменной отношения должен быть отличим от любого другого кортежа этого значения отношения по составным значениям заранее определенного множества атрибутов переменной отношения, т. е., другими словами, любая переменная отношения должна обладать первичным ключом. Как мы видели в предыдущем разделе, это требование автоматически удовлетворяется, если в системе не нарушаются базовые свойства отношений.
На самом деле, требование целостности сущности полностью звучит следующим образом: у любой переменной отношения должен существовать первичный ключ, и никакое значение первичного ключа в кортежах значения-отношения переменной отношения не должно содержать неопределенных значений. Чтобы эта формулировка была полностью понятна, мы должны хотя бы кратко обсудить понятие неопределенного значения (NULL).
Конечно, теоретически любой кортеж, заносимый в сохраняемое отношение, должен содержать все характеристики моделируемой им сущности реального мира, которые мы хотим сохранить в базе данных. Однако на практике не все эти характеристики могут быть известны к тому моменту, когда требуется зафиксировать сущность в базе данных. Простым примером может быть процедура принятия на работу человека, размер заработной платы которого еще не определен. В этом случае служащий отдела кадров, который заносит в отношение СЛУЖАЩИЕ кортеж, описывающий нового служащего, просто не может обеспечить значение атрибута СЛУ_ЗАРП (любое значение домена РАЗМЕРЫ_ВЫПЛАТ будет неверно характеризовать зарплату нового служащего).
Эдгар Кодд предложил использовать в таких случаях неопределенные значения.
Неопределенное значение не принадлежит никакому типу данных и может присутствовать среди значений любого атрибута, определенного на любом типе данных (если это явно не запрещено при определении атрибута). Если a – это значение некоторого типа данных или NULL, op – любая двуместная «арифметическая» операция этого типа данных (например, +), а lop – операция сравнения значений этого типа (например, =), то по определению:
a op NULL = NULL NULL op a = NULL a lop NULL = unknown
NULL lop a = unknown
Здесь unknown – это третье значение логического, или булевского, типа, обладающее следующими свойствами:
NOT unknown = unknown true AND unknown = unknown true OR unknown = true false AND unknown = false false OR unknown = unknown
(напомним, что операции AND и OR являются коммутативными). В данной лекции нам достаточно приведенного краткого введения в неопределенные значения, но в следующих лекциях мы будем неоднократно возвращаться к этой теме.
Так вот, первое из требований — требование целостности сущности — означает, что первичный ключ должен полностью идентифицировать каждую сущность, а поэтому в составе любого значения первичного ключа не допускается наличие неопределенных значений. (В классической реляционной модели это требование распространяется и на возможные ключи; как будет показано в следующих лекциях, в SQL-ориентированных СУБД такое требование для возможных ключей не поддерживается.)
Второе требование, которое называется требованием целостности по ссылкам (referential integrity), является более сложным. Очевидно, что при соблюдении нормализованности отношений сложные сущности реального мира представляются в реляционной БД в виде нескольких кортежей нескольких отношений. Например, представим, что требуется представить в реляционной базе данных сущность ОТДЕЛ с атрибутами ОТД_НОМЕР (номер отдела), ОТД_РАЗМ (количество служащих) и ОТД_СЛУ (множество служащих отдела). Для каждого служащего нужно хранить СЛУ_НОМЕР (номер служащего), СЛУ_ИМЯ (имя служащего) и СЛУ_ЗАРП (заработная плата служащего).
Как мы увидим в лекции 8, при правильном проектировании соответствующей БД в ней появятся два отношения: ОТДЕЛЫ {ОТД_НОМЕР, ОТД_РАЗМ} (первичный ключ – {ОТД_НОМЕР}) и СОТРУДНИКИ {СЛУ_НОМЕР, СЛУ_ИМЯ, СЛУ_ЗАРП, СЛУ_ОТД_НОМ} (первичный ключ – {СЛУ_НОМЕР}).
Как видно, атрибут СЛУ_ОТД_НОМ вводится в отношение СЛУЖАЩИЕ не потому, что номер отдела является собственным свойством служащего, а лишь для того, чтобы иметь возможность при необходимости восстановить полную сущность ОТДЕЛ. Значение атрибута СЛУ_ОТД_НОМ в любом кортеже отношения СЛУЖАЩИЕ должно соответствовать значению атрибута ОТД_НОМ в некотором кортеже отношения ОТДЕЛЫ. Атрибут такого рода (возможно, составной) называется внешним ключом (foreign key), поскольку его значения однозначно характеризуют сущности, представленные кортежами некоторого другого отношения (т. е. задают значения их первичного ключа). Конечно, внешний ключ может быть составным, т. е. состоять из нескольких атрибутов. Говорят, что отношение, в котором определен внешний ключ, ссылается на соответствующее отношение, в котором такой же атрибут является первичным ключом.
Требование целостности по ссылкам, или требование целостности внешнего ключа, состоит в том, что для каждого значения внешнего ключа, появляющегося в кортеже значения-отношения ссылающейся переменной отношения, либо в значении-отношении переменной отношения, на которую указывает ссылка, должен найтись кортеж с таким же значением первичного ключа, либо значение внешнего ключа должно быть полностью неопределенным (т. е. ни на что не указывать). Для нашего примера это означает, что если для служащего указан номер отдела, то этот отдел должен существовать.
Заметим, что, как и первичный ключ, внешний ключ должен специфицироваться при определении переменной отношения и представляет собой ограничение на допустимые значения-отношения этой переменной. Другими словами, определение внешнего ключа представляет собой определение ограничения целостности базы данных.
Ограничения целостности сущности и по ссылкам должны поддерживаться СУБД.
Для соблюдения целостности сущности достаточно гарантировать отсутствие в любой переменной отношения значений-отношений, содержащих кортежи с одним и тем же значением первичного ключа (и запрещать вхождение в значение первичного ключа неопределенных значений). С целостностью по ссылкам дело обстоит несколько сложнее.
Понятно, что при обновлении ссылающегося отношения (вставке новых кортежей или модификации значения внешнего ключа в существующих кортежах) достаточно следить за тем, чтобы не появлялись некорректные значения внешнего ключа. Но как быть при удалении кортежа из отношения, на которое ведет ссылка?
Здесь существуют три подхода, каждый из которых поддерживает целостность по ссылкам. Первый подход заключается в том, что вообще запрещается производить удаление кортежа, для которого существуют ссылки (т. е. сначала нужно либо удалить ссылающиеся кортежи, либо соответствующим образом изменить значения их внешнего ключа). При втором подходе при удалении кортежа, на который имеются ссылки, во всех ссылающихся кортежах значение внешнего ключа автоматически становится полностью неопределенным. Наконец, третий подход (каскадное удаление) состоит в том, что при удалении кортежа из отношения, на которое ведет ссылка, из ссылающегося отношения автоматически удаляются все ссылающиеся кортежи.
В развитых реляционных СУБД обычно можно выбрать способ поддержания целостности по ссылкам для каждого случая определения внешнего ключа. Конечно, для принятия такого решения необходимо анализировать требования конкретной прикладной области.
Целостность в реляционной модели данных
Кодд предложил два декларативных механизма поддержки целостности реляционных баз данных, которые затверждены в реляционной модели данных и должны поддерживаться в любой реализующей ее СУБД: ограничение целостности сущности, или ограничение первичного ключа и ограничение ссылочной целостности, или ограничение внешнего ключа. Мы снова оставим подробности и формализмы на лекцию 3 и приведем здесь только изложение общих идей.
Ограничение целостности сущности звучит следующим образом: для заголовка любого отношения базы данных должен быть явно или неявно определен первичный ключ, являющийся таким минимальным подмножеством заголовка отношения, что в любом теле этого отношения, которое может появиться в базе данных, значение первичного ключа в любом кортеже этого тела является уникальным, т.е. отличается от значения первичного ключа в любом другом кортеже. Под минимальностью первичного ключа понимается то, что если из множества атрибутов первичного ключа удалить хотя бы один атрибут, то ограничение целостности изменится, т.е. в БД смогут появляться тела отношений, которые не допускались исходным первичным ключом.
Если первичный ключ не объявляется явно, то в качестве первичного ключа отношения принимается весь его заголовок. Понятно, что поскольку по определению любое тело отношения с заданным заголовком является множеством, следовательно, в нем отсутствуют дубликаты, и первичный ключ, совпадающий с заголовком отношения, всегда обладает свойством уникальности. Должно быть понятно, что в этом случае определение первичного ключа не задает никакого ограничения целостности.
Чтобы пояснить смысл ограничения ссылочной целостности, нужно сначала ввести понятие внешнего ключа. В принципе при использовании реляционной модели данных можно хранить все данные, соответствующие предметной области в одной таблице. Пример такой базы данных демонстрировался в лекции 1 на , где в одном файле (интуитивном аналоге отношения) хранилась информация и о служащих, и об отделах, в которых они работают.
Как было показано в лекции 1, такой подход приводит к избыточности хранения (данные об отделе повторяются в каждой записи о служащем этого отдела) и усложняет выполнение некоторых операций.
На для хранения информации о служащих и отделах использовалось два файла, в одном из которых хранились данные, индивидуальные для каждого служащего, а во втором – данные об отделах. Для возможности получения полной информации о служащих и отделах, в которых они работают, в файле СЛУЖАЩИЕ
содержалось поле СЛУ_ОТД_НОМЕР, содержащее для каждого служащего его уникальный номер отдела. В то же время, в файле ОТДЕЛЫ
имелось поле ОТД_НОМЕР, являющееся уникальным ключом этого файла. На самом деле, введя файлы СЛУЖАЩИЕ
и ОТДЕЛЫ, а также обеспечив связь между ними с помощью полей СЛУ_ОТД_НОМЕР
и ОТД_НОМЕР, мы смогли обеспечить табличное представление иерархии ОТДЕЛ-СЛУЖАЩИЕ. Если говорить в терминах реляционной модели данных, то в отношении ОТДЕЛЫ
поле ОТД_НОМЕР
является первичным ключом, а в отношении СЛУЖАЩИЕ
поле СЛУ_ОТД_НОМЕР
является внешним ключом, ссылающимся на отношение ОТДЕЛЫ.
Более точно, внешним ключом отношения R1, ссылающимся на отношение
R2, называется подмножество заголовка HR1, которое совпадает с первичным ключом отношения R2
(с точностью до имен атрибутов). Тогда ограничение ссылочной целостности реляционной модели данных можно сформулировать следующим образом: в любом теле отношения R1, которое может появиться в базе данных, для «не пустого»
значения внешнего ключа, ссылающегося на отношение R2, в любом кортеже этого тела должен найтись кортеж в теле отношения R2, которое содержится в базе данных, с совпадающим значением первичного ключа. Легко заметить, что это почти то же самое ограничение, о котором говорилось в подразделе :
никакой потомок не может существовать без своего родителя, но немного уточненное – ссылки на родителя должны быть корректными.
Обозначение s
означает, что элемент s
принадлежит множеству S.
Обозначение s
означает, что элемент s
не принадлежит множеству S.
Понятие «пустого», или неопределенного значения мы уточним в лекции 3.
Численные выражения
Численное выражение – это выражение, значение которого относится к числовому типу данных. Вот формальный синтаксис численного выражения:
numeric_value_expression> ::= numeric_term | numeric_value_expression + term | numeric_value_expression – term numeric_term ::= numeric_factor | numeric_term * numeric_factor | numeric_term / numeric_factor numeric_factor ::= [ { + | – } ] numeric_primary numeric_primary ::= value_expression_primary | numeric_value_function
Следует обратить внимание на то, что в численных выражениях SQL первичная составляющая (numeric_primary) является либо первичным выражением (см. выше), либо вызовом функции с численным значением (numeric_value_function). Из этого, в частности, следует, что в численные выражения могут входить выражения с переключателем и операции преобразования типов. Вызовы функций с численным значением определяются следующими синтаксическими правилами:
numeric_value_function ::= POSITION (character_value_expression IN character_value_expression) |{CHAR_LENGTH | CHARACTER_LENGTH } (string_value_expression) | OCTET_LENGTH (string_value_expression) | BIT_LENGTH (string_value_expression) | EXTRACT ({ datetime_field | time_zone field } FROM { datetime_value_expression | interval_value_expression }) | CARDINALITY (array_value_expression | multiset_value_expression) | ABS (numeric_value_expression) | MOD (numeric_value_expression)
Мы достаточно подробно обсуждали функции определения позиции и длины по отношению к символьным и битовым строкам при рассмотрении соответствующих типов данных; здесь приводится только уточненный синтаксис их вызова. Функция EXTRACT извлечения поля из значений дата-время или интервал позволяет получить в виде точного числа с масштабом 0 значение любого поля (года, месяца, дня и т. д.). Какой конкретный тип точных чисел будет выбран – определяется в реализации. Функции ABS и MOD возвращают абсолютное значение числа и остаток от деления одного целого значения на другое соответственно.
Декомпозиция без потерь и функциональные зависимости
Как уже отмечалось, в следующей лекции мы будем обсуждать подход к проектированию реляционных баз данных на основе нормализации, т. е. декомпозиции (разбиения путем проецирования) отношения, находящегося в предыдущей нормальной форме, на два или более отношений, удовлетворяющих требованиям следующей нормальной формы.
Считаются правильными такие декомпозиции отношения, которые обратимы, т. е. имеется возможность собрать исходное отношение из декомпозированных отношений без потери информации. Такие декомпозиции называются декомпозициями без потерь.
Диаграммы функциональных зависимостей
Далее, для иллюстраций в следующей лекции нам пригодятся диаграммы FD, с помощью которых можно наглядно представлять минимальные множества FD. Например, на приведена диаграмма минимального множества FD отношения СЛУЖАЩИЕ_ПРОЕКТЫ.
Рис. 7.6. Диаграмма минимального множества FD отношения СЛУЖАЩИЕ_ПРОЕКТЫ
В левой части диаграммы все стрелки начинаются с атрибута СЛУ_НОМ, который является единственным возможным (и, следовательно, первичным) ключом отношения СЛУЖАЩИЕ_ПРОЕКТЫ. Обратите внимание на отсутствие стрелки от СЛУ_НОМ к ПРОЕКТ_РУК. Конечно, поскольку СЛУ_НОМ является возможным ключом, должна выполняться и FD СЛУ_НОМ
Добавление, изменение или удаление определения столбца
Действие по изменению определения столбца специфицируется в следующем синтаксисе:
column_alteration_action ::= ADD [ COLUMN ] column_definition | ALTER [ COLUMN ] column_name { SET default_definition | DROP DEFAULT } | DROP [ COLUMN ] column_name { RESTRICT | CASCADE }
Итак, с использованием оператора ALTER TABLE можно добавлять к определению таблицы определение нового столбца (действие ADD) и изменять или отменять определение существующего столбца (действия ALTER и DROP соответственно).
Смысл действия ADD COLUMN почти полностью совпадает со смыслом раздела определения столбца в операторе CREATE TABLE. Указывается имя нового столбца, его тип данных или домен. Могут определяться значение по умолчанию и ограничения целостности. Однако имеется одно существенное отличие: столбец, определяемый в действии ADD оператора ALTER TABLE, добавляется к уже существующей таблице, которая, скорее всего, содержит некоторый набор строк. В каждой из существующих строк новый столбец должен содержать некоторое значение, и считается, что сразу после выполнения действия ADD этим значением является значение столбца по умолчанию. Поэтому столбец, определяемый в действии ADD, обязательно должен иметь значение по умолчанию, т. е. для него недопустима ситуация, когда значением по умолчанию явно или неявно объявлено неопределенное значение (NULL), но среди ограничений целостности столбца присутствует ограничение NOT NULL.
В действии ALTER COLUMN можно изменить (SET default_definition) или отменить определение значения по умолчанию для существующего столбца. Правила определения нового действующего значения столбца по умолчанию совпадают с соответствующими правилами, обсуждавшимися в подразделе определения столбца в операторе CREATE TABLE. Заметим, что изменение значения столбца по умолчанию не оказывает влияния на состояние существующих строк таблицы (даже если в некоторых из них хранится предыдущее значение столбца по умолчанию). Если столбец определен на домене, у которого существует значение по умолчанию, то после отмены определения значения столбца по умолчанию для этого столбца начинает действовать значение по умолчанию домена.
Действие DROP COLUMN отменяет определение существующего столбца (удаляет его из таблицы). Действие DROP COLUMN отвергается, если: (a) указанный столбец является единственным столбцом таблицы;(b) или в этом действии присутствует спецификация RESTRICT, и данный столбец используется в определении каких-либо представлений или ограничений целостности.
Если в действии присутствует спецификация CASCADE, то его выполнение порождает неявное выполнение оператора DROP для всех представлений и ограничений целостности, в определении которых используется данный столбец.
Домен
Понятие домена более специфично для баз данных, хотя и имеются аналогии с подтипами в некоторых языках программирования (более того, в своем «Третьем манифесте» , , Кристофер Дейт и Хью Дарвен вообще ликвидируют различие между доменом и типом данных). В общем виде домен определяется путем задания некоторого базового типа данных, к которому относятся элементы домена, и произвольного логического выражения, применяемого к элементу этого типа данных (ограничения домена). Элемент данных является элементом домена в том и только в том случае, если вычисление этого логического выражения дает результат истина (для логических значений мы будем попеременно использовать обозначения истина и ложь или true и false). С каждым доменом связывается имя, уникальное среди имен всех доменов соответствующей базы данных.
Наиболее правильной интуитивной трактовкой понятия домена является его восприятие как допустимого потенциального, ограниченного подмножества значений данного типа. Например, домен ИМЕНА в нашем примере определен на базовом типе символьных строк, но в число его значений могут входить только те строки, которые могут представлять имена (в частности, для возможности представления русских имен такие строки не могут начинаться с мягкого или твердого знака и не могут быть длиннее, например, 20 символов). Если некоторый атрибут отношения определяется на некотором домене (как, например, на атрибут СЛУ_ИМЯ определяется на домене ИМЕНА), то в дальнейшем ограничение домена играет роль ограничения целостности, накладываемого на значения этого атрибута.
Следует отметить также семантическую нагрузку понятия домена: данные считаются сравнимыми только в том случае, когда они относятся к одному домену. В нашем примере значения доменов НОМЕРА ПРОПУСКОВ и НОМЕРА ОТДЕЛОВ относятся к типу целых чисел, но не являются сравнимыми (допускать их сравнение было бы бессмысленно).
Еще один способ формулировки запросов
Прежде всего, на простом примере покажем, как использование ссылок на порождаемые таблицы расширяет возможности формулировки запросов.
Пример 19.14. Найти номера отделов и имена руководителей отделов, которые числятся в тех же отделах, которыми руководят, и получают зарплату, размер которой является максимальным для служащих данного отдела.
SELECT MNG.DEPT_NO, MNG.MNG_NAME FROM (SELECT DEPT.DEPT_NO, EMP.DEPT_NO, EMP_NAME, EMP_SAL FROM DEPT, EMP WHERE DEPT.DEPT_MNG = EMP.EMP_NO) AS MNG (DEPT_NO_1, DEPT_NO_2, MNG_NAME, MNG_SAL) WHERE DEPT_NO_1 = DEPT_NO_2 AND MNG_SAL = (SELECT MAX (EMP_SAL) FROM EMP WHERE EMP.DEPT_NO = DEPT_NO_1);
В этом запросе порождаемая таблица MNG содержит по одной строке для каждого служащего, являющегося руководителем отдела. Первый столбец этой таблицы – DEPT_NO_1 – содержит номер отдела, которым руководит данный служащий. В столбце DEPT_NO_1 хранятся номера отделов, в которых числятся руководители отделов, а в столбцах EMP_NAME и EMP_SAL содержатся имя служащего-руководителя отдела и размер его заработной платы соответственно.
Конечно, этот запрос можно сформулировать и без использования ссылки на порождаемую таблицу в разделе FROM, например, следующим образом (пример 19.14.1):
SELECT DEPT.DEPT_NO, EMP.EMP_NAME FROM DEPT, EMP WHERE DEPT.DEPT_MNG = EMP.EMP_NO AND DEPT.DEPT_NO = EMP.DEPT_NO AND EMP.EMP_SAL = (SELECT MAX(EMP_SAL) FROM EMP WHERE EMP.DEPT_NO = DEPT.DEPT_NO);
А вот как можно сформулировать тот же запрос с использованием раздела WITH (пример 19.14.2):
WITH MNG (DEPT_NO_1, DEPT_NO_2, MNG_NAME, MNG_SAL) AS (SELECT DEPT.DEPT_NO, EMP.DEPT_NO, EMP_NAME, EMP_SAL FROM DEPT, EMP WHERE DEPT.MNG_NO = EMP.EMP_NO), MAX_DEPT_SAL (MAX_SAL, DEPT_NO) AS (SELECT MAX (EMP_SAL), DEPT_NO FROM EMP WHERE DEPT_NO IS NOT NULL GROUP BY DEPT_NO) SELECT DEPT_NO_1, MNG_NAME FROM MNG WHERE DEPT_NO_1 = DEPT_NO_2 AND MNG_SAL = (SELECT MAX_SAL FROM MAX_DEPT_SAL WHERE MAX_DEPT_SAL.DEPT_NO = DEPT_NO_1);
Файловые системы
Историческим шагом стал переход к использованию систем управления файлами. С точки зрения прикладной программы файл – это именованная область внешней памяти, в которую можно записывать и из которой можно считывать данные. Правила именования файлов, способ доступа к данным, хранящимся в файле, и структура этих данных зависят от конкретной системы управления файлами и, возможно, от типа файла. Система управления файлами берет на себя распределение внешней памяти, отображение имен файлов в соответствующие адреса внешней памяти и обеспечение доступа к данным.
В этом разделе мы рассмотрим историю файловых систем, их основные черты и области разумного применения. Однако сначала сделаем два замечания. Во-первых, в области управления файлами исторически существует некоторая терминологическая путаница. Термин файловая система (file system) используется для обозначения программной системы, управляющей файлами, и архива файлов, хранящегося во внешней памяти. Было бы лучше в первом случае использовать термин система управления файлами, оставив за термином файловая система только второе значение. Однако принятая практика заставляет нас использовать термин файловая система в обоих смыслах. Будем надеяться, что точный смысл термина будет понятен из контекста. (Заметим, что среди непрофессионалов аналогичная путаница возникает при использовании терминов база данных и система управления базами данных. В этом курсе мы будем строго разделять эти термины.) Во-вторых, мы ограничимся описанием свойств так называемых традиционных файловых систем, не обсуждая особенности современных систем с повышенной надежностью, поскольку это заставило бы нас сильно отклониться от основной темы курса.
Первая развитая файловая система была разработана специалистами IBM в середине 60-х гг. для выпускавшейся компанией серии компьютеров «360». В этой системе поддерживались как чисто последовательные, так и индексно-последовательные файлы, а реализация во многом опиралась на возможности только появившихся к этому времени контроллеров управления дисковыми устройствами. Контроллеры обеспечивали возможность обмена с дисковыми устройствами порциями данных произвольного размера, а также индексный доступ к записям файлов, и эти функции контроллеров активно использовались в файловой системе ОS/360.
Файловая система ОS/360 обеспечила будущих разработчиков уникальным опытом использования дисковых устройств с подвижными головками, который отражается во всех современных файловых системах.
Феномен фантомов
Этому феномену подвержены транзакции, производящие выборку строк и таблиц базы данных и допускающие добавление к данным таблицам другими транзакциями строк, которые удовлетворяют условию выборки. Пример феномена фантомов показан на .
Рис. 22.6. Феномен фантомов
На этом рисунке показано, что в момент времени t0 были образованы две транзакции, T1 и T2. В момент времени t1 транзакция T2 выполняет операцию выборки строк из таблицы R по условию c. В момент времени t2 (t2>t1) транзакция T1 выполняет над таблицей R операцию обновления (вставки или модификации строк), в результате которой в таблице R появляются дополнительные строки, удовлетворяющие условию c. В момент времени t3 (t3>t2) транзакция T2 повторно выполняет операцию выборки строк из таблицы R по условию c и обнаруживает наличие в результате дополнительных фантомных строк.
В SQL феномен фантомов может наблюдаться у транзакций, выполняемых на уровне изоляции REPEATABLE READ (этот уровень изоляции, как показывает его название, гарантирует отсутствие феномена неповторяемого чтения).
Наконец, для транзакций, выполняемых на уровне изоляции SERIALIZABLE, невозможно и проявление феномена фантомов. Термин serializable (сериализуемый) используется по той причине, что при работе на данном уровне изоляции суммарный эффект выполнения набора транзакций {T1, T2, ... , Tn} идентичен эффекту некоторого последовательного выполнения этих транзакций. Это означает предельную изолированность транзакций. Общая картина взаимосвязи уровней изоляции и феноменов транзакций показана в .
| READ UNCOMMITTED | Возможно | Возможно | Возможны |
| READ COMMITTED | Невозможно | Возможно | Возможны |
| REPEATABLE READ | Невозможно | Невозможно | Возможны |
| SERIALIZABLE | Невозможно | Невозможно | Невозможны |
Феномен «грязного» чтения (dirty read)
Этому феномену подвержены транзакции, в которых допускается возможность видеть изменения объектов базы данных, производимые другими одновременно выполняемыми и еще не зафиксированными транзакциями. Простой пример феномена «грязного» чтения показан на .
Рис. 22.4. Феномен «грязного» чтения
На этом рисунке показано, что в момент времени t0 были образованы две транзакции T1 и T2. В момент времени t1 транзакция T1 успешно выполняет операцию модификации некоторого объекта базы данных O. В момент времени t2 (t2>t1) транзакция T2 читает объект O, после чего успешно завершается в момент времени t3. Транзакция же T1 завершается в момент времени t4 (t4>t3), причем в ней выполняется оператор ROLLBACK, что приводит к ликвидации в базе данных последствий изменения объекта O. В результате оказывается, что в транзакции T2 обрабатывались данные, которые реально не существуют в базе данных (отсюда и термин «грязные» данные).
В SQL феномен «грязного» чтения может наблюдаться у транзакций, выполняемых на уровне изоляции READ UNCOMMITTED. Рекомендуется использовать этот уровень изоляции только в тех транзакциях, для выполнения функций которых точные данные не обязательны (например, в транзакциях, производящих статистическую обработку).
Феномен неповторяемого чтения (unrepeatable read)
Этому феномену подвержены транзакции, читающие некоторые объекты базы данных и допускающие изменения уже прочитанных объектов другими транзакциями. Пример феномена неповторяемого чтения показан на .
Рис. 22.5. Феномен неповторяемого чтения
На этом рисунке показано, что в момент времени t0 были образованы две транзакции T1 и T2. В момент времени t1 транзакция T2 выполняет операцию чтения некоторого объекта базы данных O (например, производит выборку строки из таблицы с указанием значения первичного ключа). В момент времени t2 (t2>t1) транзакция T1 изменяет объект O (модифицирует или даже удаляет). В момент времени t3 (t3>t2) транзакция T2 повторно считывает объект O и обнаруживает, что он изменился или вовсе отсутствует. Другими словами, в транзакции T2 повторное выполнение выборки объекта базы данных O дало результат, отличный от результата первого выполнения (отсюда и происходит термин «неповторяемое чтение»).
В SQL феномен неповторяемого чтения может наблюдаться у транзакций, выполняемых на уровне изоляции READ COMMITTED (этот уровень изоляции, как показывает его название, гарантирует отсутствие феномена «грязного» чтения).
Физическая синхронизация
Поскольку в СУБД может одновременно («параллельно») выполняться несколько транзакций, вполне реальна ситуация, когда в двух одновременно выполняемых операциях требуется доступ к одному и тому же блоку базы данных (т.е. к одной и той же буферной странице, содержащей копию этого блока). Понятно, что в одновременном доступе для чтения содержимого блока ничего плохого нет, но параллельное изменение блока может привести к непредсказуемым результатам.
Следует заметить, что, вообще говоря, координацию параллельного доступа к страницам буферного пула не обеспечивает логическая синхронизация, используемая для сериализации транзакций (см. лекцию 13). Например, предположим, что в двух параллельно выполняемых транзакциях одновременно выполняются операции модификации кортежей, у одного из которых tid = (n, 1), а у другого tid = (n, 2). Если в СУБД используются блокировки на уровне кортежей, то система допустит параллельное выполнение этих двух операций, и они будут одновременно изменять страницу, содержащую копию блока базы данных с номером n. При выполнении обеих операций может потребоваться перемещение кортежей внутри этого блока, и понятно, что в результате ничего хорошего, скорее всего, не получится. Аналогично, логическая синхронизация может легко допустить параллельное выполнение нескольких операций, требующих обновления одного и того же индекса. Некоординированное параллельное обновление B-дерева с большой вероятностью приводит к разрушению его структуры.
Поэтому при выполнении операций уровня RSS необходимо поддерживать дополнительную «физическую» синхронизацию, в которой единицами блокировки служат страницы буферного пула (или блоки) базы данных. В пределах операции перед чтением из страницы буферного пула (блока базы данных) требуется запросить у подсистемы управления буферным пулом блокировку соответствующей страницы (блока) в режиме S, а перед записью в страницу (в блок) – ее блокировку в режиме X. Совместимость блокировок обычная, такая же, как в табл. 13.1.
Но блокировки страниц буферного пула нужны не только для координации параллельного доступа к страницам при параллельном выполнении транзакций. При выполнении операций уровня RSS могут возникать ошибки, обнаруживаемые в середине операции, уже после того, как одна или несколько страниц буферного пула (блоков базы данных) было изменено. Например, может выполняться операция вставки кортежа в некоторую таблицу, нарушающая уникальность некоторого индекса, определенного над этой таблицей. Нарушение уникальности этого индекса будет обнаружено при попытке вставить в него новый ключ, но до этого новый кортеж уже мог быть размещен в блоке данных, и некоторые индексы уже могли быть успешно обновлены.
При обнаружении ошибки операции нужно ликвидировать все ее следы в базе данных и выдать соответствующий код ошибки на уровень RDS. Проще всего сделать это, произведя обратные изменения всех страниц (блоков базы данных), которые были изменены при прямом выполнении операции. Но для этого требуется, чтобы все страницы (блоки базы данных), заблокированные при выполнении операции, оставались заблокированными до конца этой операции.
Тем самым, для подсистемы управления буферным пулом операции уровня RSS являются (почти) тем же, чем являются транзакции для подсистемы управления транзакциями. Достаточным условием корректного выполнения операций является соблюдение двухфазного протокола синхронизационных блокировок над страницами буферного пула в пределах операций.
Заметим (хотя и без подробных объяснений), что это условие не является необходимым. Каждую операцию уровня RSS можно разбить на последовательность «микроопераций» и потребовать соблюдения двухфазного протокола синхронизационных блокировок в пределах микроопераций. Например, операцию INSERT
уровня RSS можно разбить на следующие микрооперации:
1) нахождение блока данных для вставки;
2) вставка кортежа в найденный блок;
3) обновление индекса 1;
…….
n) обновление индекса n,
где n
– число индексов, определенных для данной таблицы.Общий принцип состоит в том, что в пределах одной микрооперации блокируются все блоки базы данных, которые обязаны быть изменены согласованным образом.
Формальные определения
Пусть требуется выполнить некоторую операцию соединения над таблицами table1 и table2. Тогда: Обозначим через CP результат выполнения запроса
SELECT * FROM table1, table2 Если задается операция JOIN (или NATURAL JOIN) без явного указания типа соединения (join_type), то по умолчанию имеется в виду INNER JOIN (или NATURAL INNER JOIN).Если в спецификации соединения (join_specification) указано ключевое слово ON, то все ссылки на столбцы, встречающиеся в условном выражении (conditional_expression), должны указывать на столбцы таблиц table1 и table2 или на столбцы таблиц внешнего запроса. Если в этом условном выражении присутствует вызов агрегатной функции, то соединенная таблица может фигурировать только в подзапросах, используемых в разделах HAVING или SELECT внешнего запроса, и ссылка на столбец в вызове функции должна указывать на столбец таблицы внешнего запроса.Для прямых соединений (CROSS JOIN) и всех других видов соединения, включающих раздел ON, заголовок результата операции совпадает с заголовком таблицы CP.Если в спецификации вида соединения присутствуют ключевые слова NATURAL или USING, то заголовок результата операции определяется следующим образом: если в спецификации вида соединения присутствует ключевое слово NATURAL, то будем называть соответствующими столбцами соединения (corresponding join column) все столбцы таблиц table1 и table2, которые имеют в заголовках этих таблиц одинаковые имена. Если в спецификации вида соединения присутствует ключевое слово USING, то будем называть соответствующими столбцами соединения (corresponding join column) все столбцы таблиц table1 и table2, имена которых входят в список имен столбцов раздела USING (эти столбцы должны быть одноименными в заголовках обеих таблиц). В обоих случаях типы данных каждой пары соответствующих столбцов должны быть совместимыми; будем называть списком выборки соответствующих столбцов соединения (select_list of corresponding join columns – SLCC) список элементов вида COALESCE (table1.c, table2.c) AS c*, где с является именем соответствующего столбца соединения.
Элементы располагаются в том порядке, в котором они появляются в заголовке таблицы table1. Обозначим через SLT1 (SLT2) список имен столбцов таблицы table1 (table2), которые не являются соответствующими столбцами соединения. Имена располагаются в том же порядке, в котором они появляются в заголовке соответствующей таблицы;заголовок результата совпадает с заголовком результата запроса
SELECT SLCC, SLT1, SLT2 FROM table1, table2; Набор строк результата (множество или мультимножество) определяется по следующим правилам. Обозначим через T следующие наборы строк: если видом соединения является UNION JOIN, то T – пусто;если видом соединения является CROSS JOIN, то T включает все строки, входящие в CP;если в спецификацию вида соединения входит раздел ON, то T включает все строки CP, для которых результатом вычисления условного выражения является true;если в спецификацию вида соединения входят разделы NATURAL или USING, и список SLCC не является пустым, то T включает все строки CP, для которых значения соответствующих столбцов соединения совпадают;если в спецификацию вида соединения входят разделы NATURAL или USING, и список SLCC является пустым, то T включает все строки CP.Обозначим через P1 (P2) набор (множество или мультимножество) всех строк таблицы table1 (table2), каждая из которых участвует в образовании некой строки T.Обозначим через U1 (U2) набор (множество или мультимножество) всех строк таблицы table1 (table2), ни одна из которых не участвует в образовании какой-либо строки T.Обозначим через X1 набор (множество или мультимножество) всех строк, образуемых из строк набора U1 путем добавления справа подстроки из неопределенных значений, содержащей столько неопределенных значений, сколько столбцов содержит таблица table2. Обозначим через X2 набор (множество или мультимножество) всех строк, образуемых из строк набора U2 путем добавления слева подстроки из неопределенных значений, содержащей столько неопределенных значений, сколько столбцов содержит таблица table1.Для соединений вида CROSS JOIN и INNER JOIN пусть S обозначает тот же набор строк, что и T.Для соединений вида LEFT OUTER JOIN пусть S обозначает набор строк, являющийся результатом выражения запросов
SELECT * FROM T UNION ALL SELECT * FROM X1; Для соединений вида RIGHT OUTER JOIN пусть S обозначает набор строк, являющийся результатом выражения запросов
SELECT * FROM T UNION ALL SELECT * FROM X2; Для соединений вида FULL OUTER JOIN пусть S обозначает набор строк, являющийся результатом выражения запросов
SELECT * FROM T UNION ALL SELECT * FROM X1 UNION ALL SELECT * FROM X2; Для соединений вида UNION JOIN пусть S обозначает набор строк, являющийся результатом выражения запросов
SELECT * FROM X1 UNION ALL SELECT * FROM X2; Если в спецификации вида соединения присутствуют ключевые слова NATURAL или USING, то результат операции совпадает с результатом выражения запросов
SELECT SLCC, SLT1, SLT2 FROM S; Во всех остальных случаях результат операции совпадает с S.
Интересно, что для этого запроса возможна альтернативная формулировка с использованием операции CROSS JOIN: SELECT * FROM table1 CROSS JOIN table2. Может возникнуть естественный вопрос: зачем вводить специальную конструкцию для декартова произведения? По мнению автора, эта конструкция была введена, главным образом, для повышения уровня общности языка SQL. Кроме того, использование явного ключевого слова CROSS JOIN является подтверждением того, что пользователь действительно может получить декартово произведение, а не упустил по ошибке раздел WHERE.
Для удобства читателей напомним, что по определению выражение COALESCE (V1, V2) эквивалентно следующему выражению с переключателем: CASE WHEN V1 IS NOT NULL THEN V1 ELSE V2 END.
Совпадают в строгом смысле, т.е. значение столбца table1.c совпадает со значением столбца table2.c тогда и только тогда, когда значением операции сравнения table1.c = table2.c является true.
Фундаментальные свойства отношений
Остановимся теперь на некоторых важных свойствах отношений, которые следуют из приведенных ранее определений.
Функциональные зависимости
Наиболее важные с практической точки зрения нормальные формы отношений основываются на фундаментальном в теории реляционных баз данных понятии функциональной зависимости. Для дальнейшего изложения нам потребуется несколько определений и утверждений (по ходу изложения мы будем пояснять их и иллюстрировать).
Гранулированные синхронизационные блокировки
Подобные рассуждения привели к разработке механизма гранулированных синхронизационных блокировок. При применении этого подхода синхронизационные блокировки могут запрашиваться по отношению к объектам разного уровня: файлам, таблицам и кортежам. Требуемый уровень объекта определяется тем, какая операция выполняется (например, для выполнения операции уничтожения таблицы объектом синхронизационной блокировки должна быть вся таблица, а для выполнения операции удаления кортежа – этот кортеж). Объект любого уровня может быть заблокирован в режиме S или X.
Для согласования блокировок разного уровня вводятся специальный протокол гранулированных блокировок и новые типы блокировок. Коротко говоря, перед установкой блокировки на некоторый объект базы данных в режиме S или X соответствующий объект верхнего уровня должен быть заблокирован в режиме IS, IX или SIX. Что же собой представляют эти режимы блокировок?
Блокировка в режиме IS (Intented for Shared lock) некоторого составного объекта o
базы данных означает намерение заблокировать некоторый объект o', входящий в o, в совместном режиме (режиме S). Например, при намерении читать кортежи из таблицы Tab
эта таблица должна быть заблокирована в режиме IS (а до этого в таком же режиме должен быть заблокирован файл, в котором располагается таблица Tab).
Блокировка в режиме IX (Intented for eXclusive lock) некоторого составного объекта o
базы данных означает намерение заблокировать некоторый объект o', входящий в o, в монопольном режиме (режиме X). Например, для удаления кортежей из таблицы Tab
эта таблица должна быть заблокирована в режиме IX (а до этого в таком же режиме должен быть заблокирован файл, в котором располагается таблица Tab).
Блокировка в режиме SIX (Shared, Intented for eXclusive lock) некоторого составного объекта o
базы данных означает совместную блокировку всего этого объекта с намерением впоследствии блокировать какие-либо входящие в него объекты в монопольном режиме (режиме X). Например, если выполняется длинная операция просмотра таблицы Tab
объект o
целиком или какой-либо объект o', входящий в o. Несовместимость блокировки объекта o
в режиме S в транзакции T1
с блокировкой этого объекта в режимах X, IX или SIX в транзакции T2, тем самым, устраняет конфликты транзакций T1
и T2
вида R/W.
Блокировка объекта o
в режиме IХ в транзакции T1
совместима с блокировкой этого же объекта в режимах IS или IX в транзакции T2. Действительно, блокировка объекта o
в режиме IX в транзакции T1
направлена на то, чтобы в этой транзакции изменять какой-либо объект o', входящий в o, а блокировка этого же объекта в режиме IS в транзакции T2
– на то, чтобы читать в транзакции T2
какой-либо объект o'', входящий в o. Если объекты o'
и o''
– разные, то конфликт транзакций T1
и T2
не возникнет. Если o'
= o'', то перед изменением этот объект будет заблокирован в транзакции T1
в режиме X, а перед чтением – в транзакции T2
в режиме S. Несовместимость этих блокировок позволит избежать конфликта транзакций T1
и T2
вида W/R, и для этого не требуется несовместимость блокировок IX и IS объекта o. Аналогично обосновывается совместимость блокировок IX и IX. Блокировка IХ не совместима с блокировкой S, поскольку иначе мог бы проявиться конфликт транзакций T1
и T2
вида W/R. Блокировка IХ не совместима с блокировкой X, поскольку иначе мог бы проявиться конфликт транзакций T1
и T2
вида W/W. Наконец, блокировка IХ не совместима с блокировкой SIX, поскольку иначе мог бы проявиться конфликт транзакций T1
и T2
вида W/R или W/W.
Блокировка объекта o
в режиме IS в транзакции T1
совместима с блокировкой этого же объекта в режимах S, IS, IX или SIX в транзакции T2. Совместимость с блокировкой в режиме S или IS уже обосновывалась. Покажем, что блокировка объекта o
в режиме IS в транзакции T1
совместима с блокировкой того же объекта в режиме IX в транзакции T2. Действительно, блокировка объекта o
в режиме IS в транзакции T1
направлена на то, чтобы в этой транзакции читать какой-либо объект o', входящий в o, а блокировка этого же объекта в режиме IX в транзакции T2
– на то, чтобы в транзакции T2
изменять какой-либо объект o'', входящий в o. Если объекты o'
и o''
– разные, то конфликт транзакций не возникнет. Если o'
= o'', то перед чтением этот объект будет заблокирован в транзакции T1
в режиме S, а перед изменением – в транзакции T2
в режиме X. Несовместимость этих блокировок позволит избежать конфликта транзакций T1
и T2
вида R/W, и для этого не требуется несовместимость блокировок IS и IX объекта o. Аналогично можно показать совместимость блокировок IS и SIX. Несовместимость блокировок IS и X очевидна, поскольку иначе мог бы проявиться конфликт транзакций T1
и T2
вида R/W.
Блокировка объекта o
в режиме SIX в транзакции T1
позволяет этой транзакции читать любой объект o', входящий в o, без его дополнительной блокировки и изменять любой объект o', входящий в o, с его предварительной блокировкой в режиме X. Эта блокировка совместима с блокировкой объекта o
в режиме IS в транзакции T2. Действительно, блокировка объекта o
в режиме IS в транзакции T2
направлена на то, чтобы в транзакции T2
читать какой-либо объект o', входящий в o. Перед этим в транзакции T2
должна быть установлена блокировка объекта o'
в режиме S. К этому моменту у объекта o'
может отсутствовать явная блокировка, установленная в транзакции T1, что, в соответствии с семантикой блокировки SIX, означает наличие неявной блокировки o'
по чтению. Очевидно, что в этом случае конфликт транзакций T1
и T2
не возникает. К этому же моменту у объекта o'
может иметься блокировка в режиме X, установленная в транзакции T1. В этом случае запрос блокировки объекта o'
в режиме S удовлетворен не будет, и конфликт транзакций T1
и T2
вида W/R будет предотвращен без потребности в несовместимости блокировок SIX и IS. Блокировка объекта o
в режиме SIX в транзакции T1
не совместима с блокировкой объекта o
в режиме X в транзакции T2, поскольку иначе мог бы проявиться конфликт транзакций T1
и T2
вида R/W. Блокировка объекта o
в режиме SIX в транзакции T1
не совместима с блокировкой объекта o
в режиме S или IS в транзакции T2, поскольку иначе мог бы проявиться конфликт транзакций T1
и T2
вида W/R при доступе к некоторым объектам o', входящим в o. Наконец, блокировка объекта o
в режиме SIX в транзакции T1
не совместима с блокировкой объекта o
в режиме IX или SIX в транзакции T2, поскольку иначе мог бы проявиться конфликт транзакций T1
и T2
вида R/W при доступе к некоторым объектам o', входящим в o.
Хэширование
Альтернативным и достаточно популярным подходом к организации индексов является использование техники хэширования. Это очень обширная тема, которая заслуживает отдельного рассмотрения. Ограничимся здесь лишь несколькими замечаниями. Общей идеей методов хэширования является применение к значению ключа некоторой функции свертки (хэш-функции), вырабатывающей значение меньшего размера. Значение хэш-функции затем используется для доступа к записи.
В самом простом, классическом случае свертка ключа используется как адрес в таблице, содержащей ключи и записи. Основным требованием к хэш-функции является равномерное распределение значение свертки (одним из распространенных видов «хороших» хэш-функций являются функции, выдающие остаток от деления значения ключа на некоторое простое число). При возникновении коллизий (одна и та же свертка для нескольких значений ключа) образуются цепочки переполнения. Главным ограничением этого метода является фиксированный размер таблицы. Если таблица заполнена слишком сильно или переполнена, но возникнет слишком много цепочек переполнения, и главное преимущество хэширования – доступ к записи почти всегда за одно обращение к таблице – будет утрачено. Расширение таблицы требует ее полной переделки на основе новой хэш-функции (со значением свертки большего размера).
Идея доступа к данным на основе хэширования настолько привлекательна (потенциальная возможность за одно обращение к памяти получить требуемые данные), что от нее невозможно отказаться при работе с данными во внешней памяти. Исходная идея кажется очевидной: если при управлении данными на основе хэширования в основной памяти хэш-функция вырабатывает адрес требуемого элемента, то при обращении к внешней памяти необходимо генерировать номер блока дискового пространства, в котором находится запрашиваемый элемент данных. Основная проблема относится к коллизиям. Если при работе в основной памяти потенциально возникающими потребностями дополнительного поиска информации при возникновении коллизий можно, вообще говоря, пренебречь (поскольку время доступа к основной памяти мало), то при использовании внешней памяти любое дополнительное обращение вызывает существенные накладные расходы.
Основные методы хэширования для поиска информации во внешней памяти направлены на решение именно этой задачи.
В основе подхода расширяемого хэширования (Extendible Hashing) лежит принцип использования деревьев цифрового поиска в основной памяти. В основной памяти поддерживается справочник, организованный на основе бинарного дерева цифрового поиска, ключами которого являются значения хэш-функции, а в листовых вершинах хранятся номера блоков записей во внешней памяти. В этом случае любой поиск в дереве цифрового поиска является «успешным», т.е. ведет к некоторому блоку внешней памяти. Входит ли в этот блок искомая запись, обнаруживается уже после прочтения блока в основную память.
Проблема коллизий переформулируется следующим образом. Как таковых, коллизий не существует. Может возникнуть лишь ситуация переполнения блока внешней памяти. Значение хэш-функции указывает на этот блок, но места для включения записи в нем уже нет. Эта ситуация обрабатывается так. Блок расщепляется на два, и дерево цифрового поиска переформируется соответствующим образом. Конечно, при этом может потребоваться расширение самого справочника.
Расширяемое хэширование хорошо работает в условиях динамически изменяемого набора записей в хранимом файле, но требует наличия в основной памяти справочного дерева.
Идея линейного хэширования (Linear Hashing) состоит в том, чтобы можно было обойтись без поддержания справочника в основной памяти. Основой метода является то, что для адресации блока внешней памяти всегда используются младшие биты значения хэш-функции. Если возникает потребность в расщеплении, то записи перераспределяются по блокам так, чтобы адресация осталась правильной.
Хранение таблиц
Существуют два принципиальных подхода к физическому хранению таблиц. Наиболее распространенным является покортежное хранение таблиц (единицей физического хранения является кортеж). Естественно, это обеспечивает быстрый доступ к целому кортежу, но при этом во внешней памяти дублируются общие значения разных кортежей одной таблицы и, вообще говоря, могут потребоваться лишние обмены с внешней памятью, если нужна часть кортежа.
Альтернативным (менее распространенным) подходом является хранение таблицы по столбцам, т.е. единицей хранения является столбец таблицы с исключенными дубликатами. Естественно, что при такой организации суммарно в среднем тратится меньше внешней памяти, поскольку дубликаты значений не хранятся; за один обмен с внешней памятью в общем случае считывается больше полезной информации. Дополнительным преимуществом является возможность использования значений столбца таблицы для оптимизации выполнения операций соединения. Но при этом требуются существенные дополнительные действия для сборки целого кортежа (или его части).
Поскольку гораздо более распространено хранение по строкам, рассмотрим немного более подробно этот способ хранения таблиц (в дополнение к тому, что говорилось в разделе ). Типовой, унаследованной от System R, структурой страницы данных является та, которая показана на рис. 12.1.
Эту организацию хранения кортежей можно в целом охарактеризовать следующим образом:
Каждый кортеж обладает уникальным идентификатором (tid), не изменяемым во все время существования кортежа и позволяющим выбрать кортеж в основную память не более чем за два обращения к внешней памяти. Структура tid следует из рис. 12.1.
Обычно каждый кортеж хранится целиком в одной странице. Из этого следует, что максимальная длина кортежа любой таблицы ограничена размерами страницы. Возникает вопрос: как быть с «длинными» данными, которые в принципе не помещаются в одной странице? Применяется несколько методов. Наиболее простым решением является хранение таких данных в отдельных (вне базы данных) файлах с заменой «длинного» данного в кортеже на имя соответствующего файла.
В некоторых системах такие данные хранились внутри базы данных в отдельном наборе страниц внешней памяти, связанном физическими ссылками. Оба эти решения сильно ограничивают возможность работы с длинными данными (как, например, удалить несколько байт из середины 2-мегабайтной строки?). В настоящее время все чаще используется метод, предложенный много лет тому назад в проекте Exodus , когда «длинные» данные организуются в виде B-деревьев последовательностей байт.
Как правило, в одной странице данных хранятся кортежи только одной таблицы. Существуют, однако, варианты с возможностью хранения в одной странице кортежей нескольких таблиц. Это вызывает некоторые дополнительные расходы по части служебной информации (при каждом кортеже нужно хранить информацию о соответствующей таблице), но зато иногда позволяет резко сократить число обменов с внешней памятью при выполнении соединений.
Изменение схемы хранимой таблицы с добавлением нового поля не вызывает потребности в физической реорганизации таблицы. Достаточно лишь изменить информацию в описателе таблицы и расширять кортежи только при занесении информации в новое поле.
Поскольку таблицы могут содержать неопределенные значения, необходима соответствующая поддержка на уровне хранения. Обычно это достигается путем хранения соответствующей шкалы при каждом кортеже, который в принципе может содержать неопределенные значения.
Проблема распределения памяти в страницах данных связана с проблемами синхронизации и журнализации и не всегда тривиальна. Например, если в ходе выполнения транзакции некоторая страница данных опустошается, то ее нельзя перевести в статус свободных страниц до конца транзакции, поскольку при откате транзакции удаленные при прямом выполнении транзакции и восстановленные при ее откате кортежи должны получить те же самые идентификаторы.
Распространенным способом повышения эффективности СУБД является кластеризация таблицы по значениям одного или нескольких столбцов. Полезной для оптимизации соединений является совместная кластеризация нескольких таблиц.
С целью использования возможностей распараллеливания обменов с внешней памятью иногда применяют схему декластеризованного хранения таблиц: кортежи с общим значением столбца декластеризации размещают на разных дисковых устройствах, обмены с которыми можно выполнять параллельно.
Что же касается хранения таблицы по столбцам, то основная идея состоит в совместном хранении всех значений одного (или нескольких) столбцов. Для каждого кортежа таблицы хранится кортеж той же степени, состоящий из ссылок на места расположения соответствующих значений столбцов.
Иерархическая модель данных
Типичным представителем (наиболее известным и распространенным) является СУБД IMS (Information Management System) компании IBM. Первая версия системы появилась в 1968 г.
Иерархические структуры данных
Иерархическая БД состоит из упорядоченного набора деревьев; более точно, из упорядоченного набора нескольких экземпляров одного типа дерева. Тип дерева состоит из одного «корневого» типа записи и упорядоченного набора из нуля или более типов поддеревьев (каждое из которых является некоторым типом дерева). Тип дерева в целом представляет собой иерархически организованный набор типов записи.
На рис. 2.1 показан пример типа дерева (схемы иерархической БД). Здесь тип записи Отдел
является предком для типов записи Руководитель
и Служащие, а Руководитель
и Служащие
– потомки типа записи Отдел. Смысл полей типов записей в основном должен быть понятен по их именам. Поле Рук_Отдел
типа записи Руководитель
содержит номер отдела, в котором работает служащий, являющийся данным руководителем (предполагается, что он работает не обязательно в том же отделе, которым руководит). Между типами записи поддерживаются связи (правильнее сказать, типы
связей, поскольку реальные связи появляются в экземплярах типа дерева).
Рис. 2.1. Пример типа дерева
База данных с такой схемой могла бы выглядеть так, как показано на рис. 2.2 (мы показываем один экземпляр дерева).
Рис. 2.2. Пример иерархической базы данных
Все экземпляры данного типа потомка с общим экземпляром типа предка называются близнецами. Для иерархической базы данных определяется полный порядок обхода дерева: сверху-вниз, слева-направо. Заметим, что в терминологии IMS вместо термина запись
использовался термин сегмент, а под записью базы данных понималось все дерево сегментов.
Индексы
Как бы не были организованы индексы в конкретной СУБД, их основное назначение состоит в обеспечении эффективного прямого доступа к кортежу таблицы по ключу. Обычно индекс определяется для одной таблицы, и ключом является значение ее поля (возможно, составного). Если ключом индекса является возможный ключ таблицы, то индекс должен обладать свойством уникальности, т.е. не содержать дубликатов ключа. На практике ситуация выглядит обычно противоположно: при объявлении первичного ключа таблицы автоматически заводится уникальный индекс, а единственным способом объявления возможного ключа, отличного от первичного, является явное создание уникального индекса. Это связано с тем, что для проверки сохранения свойства уникальности возможного ключа, так или иначе, требуется индексная поддержка.
Поскольку при выполнении многих операций уровня SQL требуется сортировка кортежей таблиц в соответствии со значениями некоторых полей, полезным свойством индекса является обеспечение последовательного просмотра кортежей таблицы в заданном диапазоне значений ключа в порядке возрастания или убывания значений ключа.
Наконец, одним из способов оптимизации выполнения эквисоединения таблиц (наиболее распространенная из числа дорогостоящих операций) является организация так называемых мультииндексов для нескольких таблиц, обладающих общими атрибутами. Любой из этих атрибутов (или их набор) может выступать в качестве ключа мультииндекса. Значению ключа сопоставляется набор кортежей всех связанных мультииндексом таблиц, значения выделенных атрибутов которых совпадают со значением ключа.
Общей идеей любой организации индекса, поддерживающего прямой доступ по ключу и последовательный просмотр в порядке возрастания или убывания значений ключа является хранение упорядоченного списка значений ключа с привязкой к каждому значению ключа списка идентификаторов кортежей. Одна организация индекса отличается от другой, главным образом, в способе поиска ключа с заданным значением.
Индексы и кластеризация таблиц
На основе наличия уникальных, обеспечивающих почти прямой доступ к кортежам и не изменяемых во время существования кортежей tid'ов в System R поддерживаются дополнительные управляющие структуры – индексы. Каждый индекс определяется на одном или нескольких полях таблицы, значения которых составляют его ключ, и позволяет производить прямой поиск по ключу кортежей (их tid'ов) и последовательное сканирование таблицы по индексу, начиная с указанного ключа, в порядке возрастания или убывания значений ключа. Некоторые индексы при их создании могут обладать атрибутом уникальности. В таком индексе не допускаются дубликаты ключа. Это единственное средство SQL System R указания системе первичного ключа таблицы (фактически, набора первичного и всех возможных ключей таблицы).
Для организации индексов в System R применяется техника B+-деревьев
(более подробно B+-деревья рассматриваются в подразделе ). Каждый индекс занимает отдельный набор страниц, номер корневой страницы запоминается в описателе индекса. Использование B+-деревьев позволяет достичь эффективности при прямом поиске, поскольку они из-за своей сильной ветвистости обладают небольшой глубиной. Кроме того, B+-деревья сохраняют порядок ключей в листовых блоках иерархии, что позволяет производить последовательное сканирование таблицы в порядке возрастания или убывания значений полей, на которых определен индекс. Фундаментальное свойство B+-деревьев – автоматическая балансировка дерева – допускает произведение лишь локальных модификаций индекса при переполнениях и опустошениях страниц индекса. Насколько известно автору, System R была первой системой, в которой для организации индексов использовались B+-деревья. Эту традицию соблюдает большинство реляционных систем, возникших позднее.
Видимо, наиболее важной особенностью физической организации баз данных в System R является возможность обеспечения кластеризации связанных кортежей одной или нескольких таблиц. Под кластеризацией кортежей понимается физически близкое расположение (в пределах одной страницы данных) логически связанных кортежей.
Обеспечение соответствующей кластеризации позволяет добиться высокой эффективности системы при выполнении некоторого класса запросов. В силу большой важности понятия кластеризации в System R и ее развитиях рассмотрим историю вопроса более подробно.
В окончательном варианте System R существует только одно средство определения условий кластеризации таблицы – объявить до заполнения таблицы один (и только один) индекс, определенный на полях этой таблицы, кластеризованным. Тогда, если заполнение таблицы кортежами производится в порядке возрастания или убывания значений полей кластеризации (в зависимости от атрибутики индекса), система физически располагает кортежи в страницах данных в том же порядке.
Кроме того, в каждой странице данных кластеризованной таблицы оставляется некоторое резервное свободное пространство. При последующих вставках кортежей в такую таблицу система стремится поместить каждый кортеж в одну из страниц данных, в которых уже находятся кортежи этой таблицы с такими же (или близкими) значениями полей кластеризации. Естественно, что поддерживать идеальную кластеризацию таблицы можно только до определенного предела, пока не исчерпается резервная память в страницах. Далее этого предела степень кластеризации таблицы начинает уменьшаться, и для восстановления идеальной кластеризации таблицы требуется физическая реорганизация таблицы (ее можно произвести средствами SQL).
Очевидным преимуществом кластеризации таблицы является то, что при последовательном сканировании кластеризованной таблицы с использованием кластеризованного индекса потребуется ровно столько чтений страниц данных из внешней памяти, сколько страниц занимают кортежи этой таблицы. Следовательно, при правильно выбранных критериях кластеризации запросы, связанные с заданием условий на полях кластеризации можно выполнить почти оптимально.
В ранних версиях System R существовал еще один способ физического доступа к кортежам таблицы и, соответственно, еще один способ указания условия кластеризации с использованием так называемых связей (links).
На уровне физического представления связь – это физическая ссылка (tid) из одного кортежа на другой (не обязательно одной таблицы). В языке SEQUEL (до того момента, когда его стали называть SQL) существовали средства определения связей в иерархической манере: можно было объявить некоторую таблицу родительской по отношению к той же или другой таблице-потомку. При этом указывались поля родительской таблицы и таблицы-потомка, в соответствии со значениями которых образовывалась иерархия. Правила построения были очень простыми – проводились связи от кортежа родительской таблицы ко всем кортежам таблицы-потомка с теми же значениями полей связывания. На самом деле, все кортежи таблицы-потомка с общим значением полей связывания образовывали кольцевой список, на который проводилась одна связь из соответствующего кортежа родительской таблицы.
Следует заметить, что этот способ использования механизма связей поддерживался в ранних версиях SEQUEL. В интерфейсе RSS System R этого периода допускалась возможность произвольной установки связей без учета совпадения значений полей связывания. Тем самым, в системе в целом не использовались все возможности RSS, которые с избытком превосходили потребности организации иерархических бинарных связей по совпадению полей связывания.
Для одной таблицы допускалось создание многих связей: кортеж таблицы мог быть родителем нескольких иерархий и входить в несколько других иерархий в качестве потомка. При этом одна связь могла быть объявлена кластеризованной. Тогда система стремилась поместить в одну страницу данных все кортежи одной иерархии. При этом, естественно, использовалась возможность размещения в одной странице данных кортежей нескольких таблиц. Основной смысл такой кластеризации заключался в возможности оптимизации выполнения некоторых запросов, включающих (экви)соединение двух связанных таблиц в соответствии со значениями полей связывания.
В более поздних публикациях, посвященных System R, упоминания о механизме связей исчезли, из чего можно заключить, что разработчики отказались от его использования.
Думается, что основными причинами отказа от использования связей были следующие. Во-первых, средства построения связей, обеспечиваемые RSS, были очень низкого уровня, гораздо более низкого, чем средства поддержки индексов. Если при занесении, удалении или обновлении кортежа RSS обеспечивала автоматическую коррекцию всех индексов, то для коррекции связей требовалось выполнить ряд дополнительных обращений к RSS, из-за чего время выполнения этих операций, конечно, увеличивалось.
Во-вторых, при реализации этого механизма возникают дополнительные синхронизационные проблемы нижнего уровня (уровня совместного доступа к страницам данных). В частности, наличие прямых ссылок между страницами данных увеличивает вероятность возникновения синхронизационных тупиков.
Наконец, в-третьих, все эти дополнительные накладные расходы не окупались преимуществами, предоставляемыми механизмом связей. Действительно, максимального эффекта от использования связей можно достичь только при выполнении операции соединения двух таблиц, кластеризованных по этой связи, если поле соединения совпадает с полем связывания и условия, накладываемые на родительскую таблицу, выделяют в нем ровно один кортеж. Очевидно, что такие запросы на практике редки.
(Отметим, что приведенные соображения принадлежат автору и не излагались в публикациях по System R, так что на самом деле причины могли быть и другими.)
Кроме таблиц и индексов при работе System R во внешней памяти могут располагаться еще и временные объекты – списки (list). Список – это временная структура данных, создаваемая с целью оптимизации выполнения SQL-запроса, содержащая некоторые кортежи хранимой таблицы базы данных, не имеющая имени и, следовательно, не видимая на уровне интерфейса SQL. Кортежи списка могут быть упорядочены по возрастанию или убыванию полей соответствующей таблицы. Средства работы со списками имеются в интерфейсе RSS, но их, естественно, нет в SQL. Соответственно, эти средства используются только внутри системы при выполнении запросов (в частности, один из наиболее эффективных алгоритмов выполнения соединений основан на использовании отсортированных списков кортежей).Публикации по System R не дают точного представления о структурах данных, используемых при организации списков, но исходя из здравого смысла можно предположить, что они устроены не так, как таблицы (например, для кортежа, входящего в список, не требуется адресация через tid), и что располагаются они во временных файлах (в случае сбоя системы все временные объекты пропадают).
