Примеры запросов с использованием предиката exists
Пример 18.16. Найти номера отделов, среди служащих которых имеются менеджеры проектов. SELECT DEPT.DEPT_NO FROM DEPT WHERE EXISTS (SELECT EMP.EMP_NO FROM EMP WHERE EMP.DEPT_NO = DEPT.DEPT_NO AND EXISTS (SELECT PRO.PRO_MNG FROM PRO WHERE PRO.PRO_MNG = EMP.EMP_NO));
Эту формулировку можно упростить, избавившись от самого вложенного запроса (пример 18.16.1): SELECT DEPT.DEPT_NO FROM DEPT WHERE EXISTS (SELECT EMP.EMP_NO FROM EMP, PRO WHERE EMP.DEPT_NO = DEPT.DEPT_NO AND PRO.PRO_MNG = EMP.EMP_NO);
Далее заметим, что по смыслу предикат предиката EXISTS список выборки во вложенном подзапросе является несущественным, и формулировку запроса можно изменить, например, следующим образом (пример 18.16.2): SELECT DEPT.DEPT_NO FROM DEPT WHERE EXISTS (SELECT * FROM EMP, DEPT WHERE EMP.DEPT_NO = DEPT.DEPT_NO AND PRO.PRO_MNG = EMP.EMP_NO);
Запросы с предикатом EXISTS можно также переформулировать в виде запросов с предикатом сравнения (пример 18.16.3): SELECT DEPT.DEPT_NO FROM DEPT WHERE (SELECT COUNT(*) FROM EMP, DEPT WHERE EMP.DEPT_NO = DEPT.DEPT_NO AND PRO.PRO_MNG = EMP.EMP_NO ) >= 1;
Пример 18.17. Найти номера отделов, размер заработной платы служащих которых не превышает размер заработной платы руководителя отдела. FROM DEPT WHERE NOT EXISTS (SELECT * FROM EMP EMP1, EMP EMP2 WHERE EMP1.EMP_NO = DEPT.DEPT_MNG AND EMP2.DEPT_NO = DEPT.DEPT_NO AND EMP2.EMP_SAL > EMP1.EMP_SAL);
Примеры запросов с использованием предиката in
Пример 18.9. Найти номера, имена и номера отделов служащих, работающих в отделах 15, 17 и 19.
SELECT EMP_NO, EMP_NAME, DEPT_NO FROM EMP WHERE DEPT_NO IN (15, 17, 19);
Конечно, эта формулировка запроса эквивалентна следующей формулировке (пример 18.9.1):
SELECT EMP_NO, EMP_NAME, DEPT_NO FROM EMP WHERE DEPT_NO = 15 OR DEPT_NO = 17 OR DEPT_NO = 19;
Пример 18.10. Найти номера служащих, не являющихся руководителями отделов и получающих заплату, размер которой равен размеру зарплаты какого-либо руководителя отдела.
SELECT EMP_NO FROM EMP WHERE EMP_NO NOT IN (SELECT DEPT_MNG FROM DEPT) AND EMP_SAL IN (SELECT EMP_SAL FROM EMP, DEPT WHERE EMP_NO = DEPT_MNG);
Запросы, содержащие предикат IN с подзапросом, легко переформулировать в запросы с соединениями. Например, запрос из эквивалентен следующему запросу с соединениями (пример 18.10.1): SELECT DISTINCT EMP_NO FROM EMP, EMP EMP1, DEPT WHERE EMP_NO NOT IN (SELECT DEPT_MNG FROM DEPT) AND EMP_SAL = EMP1_SAL AND EMP1.EMP_NO = DEPT.DEPT_MNG;
По поводу этой второй формулировки следует сделать два замечания. Во-первых, как видно, мы изменили только ту часть условия, в которой использовался предикат IN, и не затронули предикат NOT IN. Запросы с предикатами NOT IN запросами с соединениями так просто не заменяются. Во-вторых, в разделе SELECT было добавлено ключевое слово DISTINCT, потому что в результате запроса во второй формулировке для каждого служащего будет содержаться столько строк, сколько существует руководителей отделов, получающих такую же зарплату, что и данный служащий.
Примеры запросов с использованием предиката like
Пример 18.11. Найти номера проектов, в названии которых присутствуют слова 'next' и 'step'. Слова должны следовать именно в такой последовательности, но слово 'next' может быть первым в названии проекта.
SELECT PRO_TITLE FROM PRO WHERE PRO_TITLE LIKE '%next%step%' OR PRO_TITLE LIKE 'Next%step%';
Это очень неудачный запрос, потому что его выполнение, скорее всего, вынудит СУБД просмотреть все строки таблицы PRO и для каждой строки выполнить две проверки столбца PRO_TITLE. Можно немного улучшить формулировку с небольшим риском получить неверный ответ (пример 18.11.1):
SELECT PRO_TITLE FROM PRO WHERE PRO_TITLE LIKE '%ext%step%';
Пример 18.12. Найти номера отделов, служащие которых являются менеджерами проектов, и название каждого из этих проектов начинается с названия отдела.
SELECT DISTINCT DEPT.DEPT_NO FROM EMP, DEPT, PRO WHERE EMP.EMP_NO = PRO.PRO_MNG AND EMP.DEPT_NO = DEPT.DEPT_NO AND PRO.PRO_TITLE LIKE DEPT.DEPT_NAME '%';
Вот как может выглядеть формулировка этого запроса, если использовать вложенные подзапросы (пример 18.12.1):
SELECT DEPT.DEPT_NO FROM DEPT WHERE DEPT.DEPT_NO IN (SELECT EMP.DEPT_NO FROM EMP WHERE EMP.EMP_NO IN (SELECT PRO.PRO_MNG FROM PRO WHERE PRO.PRO_TITLE LIKE DEPT.DEPT_NAME '%'));
Пример 18.13. Найти номера отделов, названия которых не начинаются со слова 'Software'. SELECT DEPT_NO FROM DEPT WHERE DEPT_NAME NOT LIKE 'Software%';
Примеры запросов с использованием предиката match
Все примеры этого пункта основаны на запросе «Найти номера служащих и номера их отделов для служащих, для которых в отделе со «схожим» номером работает служащий со «схожей» датой рождения» c некоторыми уточнениями.
Пример 18.25 SELECT EMP_NO, DEPT_NO FROM EMP WHERE (DEPT_NO, EMP_BDATE) MATCH SIMPLE (SELECT EMP1.DEPT_NO, EMP1.EMP_BDATE FROM EMP EMP1 WHERE EMP1.EMP_NO <> EMP.EMP_NO);
Этот запрос вернет данные о служащих, про которых: либо неизвестны номер отдела или дата рождения (или и то, и другое);либо в отделе данного служащего работает по крайней мере еще один человек с той же датой рождения.
Если использовать предикат MATCH UNIQUE FULL, то мы получим данные о служащих, про которых: либо неизвестны номер отдела или дата рождения (или и то, и другое);либо в отделе данного служащего работает еще один человек с той же датой рождения.
Пример 18.26 SELECT EMP_NO, DEPT_NO FROM EMP WHERE (DEPT_NO, EMP_BDATE) MATCH PARTIAL (SELECT EMP1.DEPT_NO, EMP1.EMP_BDATE FROM EMP EMP1 WHERE EMP1.EMP_NO <> EMP.EMP_NO);
Этот запрос вернет данные о служащих, про которых: либо неизвестны номер отдела и дата рождения;либо неизвестен номер отдела, но имеется по крайней мере еще один человек с той же датой рождения;либо неизвестна дата рождения, но в отделе данного служащего работает по крайней мере еще один человек;либо известны и номер отдела, и дата рождения, и в отделе данного служащего работает по крайней мере еще один человек с той же датой рождения.
Если использовать предикат MATCH UNIQUE PARTIAL, то мы получим данные о служащих, про которых: либо неизвестны номер отдела и дата рождения;либо неизвестен номер отдела, но имеется еще один человек с той же датой рождения;либо неизвестна дата рождения, но в отделе данного служащего работает еще один человек;либо известны и номер отдела, и дата рождения, и в отделе данного служащего работает еще один человек с той же датой рождения.
Пример 18.27 SELECT EMP_NO, DEPT_NO FROM EMP WHERE (DEPT_NO, EMP_BDATE) MATCH UNIQUE FULL (SELECT EMP1.DEPT_NO, EMP1.EMP_BDATE FROM EMP EMP1 WHERE EMP1.EMP_NO <> EMP.EMP_NO);
Этот запрос вернет данные о служащих, о которых: либо неизвестны номер отдела и дата рождения;либо в отделе данного служащего работает по крайней мере еще один человек с той же датой рождения.
Если использовать предикат MATCH UNIQUE SIMPLE, то мы получим данные о служащих, о которых: либо неизвестны номер отдела и дата рождения;либо в отделе данного служащего работает еще один человек с той же датой рождения.
Примеры запросов с использованием предиката null
На самом деле, в нашей формулировке запроса из есть одна неточность. Если у некоторого служащего номер отдела неизвестен (значение столбца EMP.DEPT_NO у соответствующей строки таблицы служащих является неопределенным), то бессмысленно вычислять средний размер зарплаты отдела этого служащего и находить размер зарплаты руководителя отдела. Формулировка из приведет к правильному результату, но это неочевидно. Чтобы сделать формулировку более понятной (и, возможно, помочь системе выполнить запрос более эффективно), нужно воспользоваться предикатом IS NOT NULL и переписать запрос следующим образом:
Пример 18.7.
SELECT EMP_NO, EMP_NAME FROM EMP WHERE DEPT_NO IS NULL;
Пример 18.8. Найти номера и имена служащих, номер отдела которых неизвестен.
SELECT EMP_NO, EMP_NAME, EMP_SAL FROM EMP WHERE DEPT_NO IS NOT NULL AND EMP_SAL BETWEEN (SELECT AVG(EMP1.EMP_SAL) FROM EMP EMP1 WHERE EMP.DEPT_NO = EMP1.DEPT_NO) AND (SELECT EMP1.EMP_SAL FROM EMP EMP1 WHERE EMP1.EMP_NO = ( SELECT DEPT.DEPT_MNG FROM DEPT WHERE DEPT.DEPT_NO = EMP.DEPT_NO ) );
Мы не обсуждаем в этом курсе предикаты, основанные на использовании выражений типа мультимножества, которые были введены в стандарте SQL:2003.
Здесь снова идет речь о семантике выполнения оператора SELECT. В стандарте, естественно, не требуется, чтобы в реализации языка запросы с корреляционными подзапросами выполнялись в точности так, как описывается ниже. Суть в том, что какой бы реальный алгоритм выполнения такого запроса не использовался, результат выполнения должен быть точно таким же, как если бы запрос выполнялся по описываемой схеме.
Кстати, в этом случае можно было бы обойтись введением одного псевдонима, оставив в качестве неявного второго псевдонима имя таблицы – EMP.
Покажем это в развернутой форме. Пусть s – текущая строка таблицы EMP, просматриваемой в цикле внешнего запроса, и пусть s.DEPT_NO содержит неопределенное значение. Тогда для строки s условие первого подзапроса будет иметь вид NULL = EMP1.DEPT_NO, и значением этого условия будет unknown для любой строки таблицы EMP(EMP1), просматриваемой в цикле этого подзапроса. Поскольку unknown не является разрешающим условием, результирующая таблица подзапроса будет пуста, и агрегатная функция AVG выдаст значение NULL. По этому поводу значением условия внешнего запроса будет unknown, и строка s не войдет в результирующую таблицу.
Примеры запросов с использованием предиката similar
Пример 18.14. Найти номера и названия отделов, название которых начинается со слов 'Hardware' или 'Software', а за ними (не обязательно непосредственно) следует последовательность десятичных цифр, предваряемых символом подчеркивания. SELECT DEPT_NAME, DEPT_NO FROM DEPT WHERE DEPT_NAME SIMILAR TO '(HARD|SOFT)WARE%\_[:DIGIT:]+' ESCAPE '\';
Пример 18.15. Найти номера и названия проектов, название которых не начинается с последовательности цифр. SELECT DEPT_NAME, DEPT_NO FROM DEPT WHERE DEPT_NAME SIMILAR TO '[^1-9]+%';
Примеры запросов с использованием предиката unique
Пример 18.18. Найти номера отделов, служащих которых можно различить по имени и дате рождения. SELECT DEPT_NO FROM DEPT WHERE UNIQUE (SELECT EMP_NAME, EMP_BDATE FROM EMP WHERE EMP.DEPT_NO = DEPT.DEPT_NO);
Возможна альтернативная, но более сложная формулировка этого запроса с использованием предиката NOT EXISTS (пример 18.18.1): SELECT DEPT_NO FROM DEPT WHERE NOT ESISTS (SELECT * FROM EMP, EMP EMP1 WHERE EMP1.EMP_NO <> EMP.EMP_NO AND EMP.DEPT_NO = DEPT.DEPT_NO AND EMP1.DEPT_NO = DEPT.DEPT_NO AND EMP1.EMP_NAME = EMP.EMP_NAME AND(EMP1.EMP_BDATE = EMP.EMP_BDATE OR (EMP.EMP_BDATE IS NULL AND EMP1.EMP_BDATE IS NULL)));
Если же ограничиться требованием уникальности имен служащих, то возможна следующая формулировка (пример 18.18.2): SELECT DEPT_NO FROM DEPT WHERE (SELECT COUNT (EMP_NAME) FROM EMP WHERE EMP.DEPT_NO = DEPT.DEPT_NO) = (SELECT COUNT (DISTINCT EMP_NAME) FROM EMP WHERE EMP.DEPT_NO = DEPT.DEPT_NO);
Примеры запросов с использованием соединенных таблиц
Мы приведем всего пару примеров, чтобы проиллюстрировать формулировки запросов, в разделе FROM которых используются ссылки на соединенные таблицы, т. е. выражения соединений.
Пример 19.17. Для каждого отдела найти его номер, имя руководителя, число служащих, минимальный, максимальный и средний размеры зарплаты служащих (еще одна формулировка запроса из ).
SELECT DEPT.DEPT_NO, EMP1.EMP_NAME, COUNT(*), MIN(EMP2.EMP_SAL), MAX(EMP2.EMP_SAL), AVG(EMP2.EMP_SAL) FROM (DEPT NATURAL INNER JOIN EMP AS EMP2) INNER JOIN EMP AS EMP1 ON DEPT.DEPT_MNG = EMP1.EMP_NO GROUP BY DEPT.DEPT_NO, EMP1.EMP_NAME;
Пример 19.18. Найти номера служащих и имена их начальников отделов для служащих, размер зарплаты которых больше 30000 руб.
SELECT EMP1.EMP_NO, EMP2.EMP_NAME FROM (EMP AS EMP1 NATURAL INNER JOIN DEPT) INNER JOIN EMP AS EMP2 ON DEPT.DEPT_MNG = EMP2.EMP_NO WHERE EMP1.EMP_SAL > 30000.00;
Можно обойтись вообще без раздела WHERE, если пожертвовать «естественностью» первого соединения (пример 19.18.1):
SELECT EMP1.EMP_NO, EMP2.EMP_NAME FROM (EMP AS EMP1 INNER JOIN DEPT ON EMP1.DEPT_NO = DEPT.DEPT_NO AND EMP1.EMP_SAL > 30000.00) INNER JOIN EMP AS EMP2 ON DEPT.MNG = EMP2.EMP_NO;
Возможности соединенных таблиц открывают широкий простор для воображения, но не будем увлекаться и ограничимся приведенными простыми примерами.
Привилегии и представления
При определении представлений действуют специальные правила определения привилегий над этими представлениями. Если при создании обычных объектов базы данных, таких, как таблица или домен, текущий authID автоматически получает все возможные привилегии доступа к соответствующему объекту, включая привилегию на передачу привилегий, то для представлений ситуация иная. Поскольку создаваемое представление всегда основывается на одной или нескольких базовых таблицах (или представлениях), привилегии, которые получает создатель представления, должны основываться на привилегиях, которыми располагает текущий authID по отношению к этим базовым таблицам или представлениям.
Например, чтобы операция создания представления была выполнена успешно, текущий authID должен обладать привилегией SELECT по отношению ко всем базовым таблицам и представлениям, на которых основывается новое представление. Тогда текущий authID автоматически получит привилегию SELECT для нового представления. Но текущий authID сможет передавать эту привилегию другим authID только тогда, когда обладает соответствующей привилегией для всех базовых таблиц и представлений, на которых основывается новое представление. Аналогичным образом на представление распространяются привилегии DELETE, INSERT, UPDATE и REFERENCES. Поскольку триггеры над представлениями создавать не разрешается, привилегия TRIGGER представлениям не передается.
Наконец, посмотрим, что происходит при смене привилегий владельца представления по отношению к таблицам, на которых основано это представление. Для простоты предположим, что представление V основано на базовой таблице T. Если во время создания V текущий authID (будущий владелец представления) обладал по отношению к T привилегиями SELECT и INSERT, то он будет обладать этими привилегиями и по отношению к V. Если впоследствии владелец представления получит по отношению к T дополнительные привилегии, то он (и все authID, которым передавались все привилегии – ALL PRIVILEGES для V) получит те же привилегии для V. Должно быть понятно, каким образом обобщается этот подход на случай, когда представление определяется над несколькими таблицами или представлениями.
Проблема фантомов
К более тонким проблемам изолированности транзакций относится так называемая проблема кортежей-«фантомов», приводящая к ситуациям, которые также противоречат изолированности пользователей. Рассмотрим сценарий, показанный на рис. 13.4.
Рис. 13.4. Проблема фантомов
В момент времени t1
транзакция T1
выполняет оператор выборки кортежей таблицы Tab
с условием выборки S
(т.е. выбирается часть кортежей таблицы Tab, удовлетворяющих условию S). До завершения транзакции T1
в момент времени t2
>
t1
транзакция T2
вставляет в таблицу Tab
новый кортеж r, удовлетворяющий условию S, и успешно завершается. В момент времени t3
>
t2
транзакция T1
повторно выполняет тот же оператор выборки, и в результате появляется кортеж, который отсутствовал при первом выполнении оператора.
Конечно, такая ситуация противоречит идее изолированности транзакций и может возникнуть даже на третьем уровне изолированности транзакций. Чтобы избежать появления кортежей-фантомов, требуется более высокий «логический» уровень изоляции транзакций. Идеи требуемого механизма (предикатные синхронизационные блокировки) появились также еще во время выполнения проекта System R, но в большинстве систем не реализованы.
Простые условия
Основой WFF являются простые условия, представляющие собой операции сравнения скалярных значений (значений атрибутов переменных или литерально заданных констант). Например, конструкции
СЛУЖАЩИЙ.СЛУ_НОМ = 2934 и
СЛУЖАЩИЙ.СЛУ_НОМ = ПРОЕКТ.ПРОЕКТ_РУК
являются простыми условиями. Первое условие принимает значение true в том и только в том случае, когда значение атрибута СЛУ_НОМ кортежной переменной СЛУЖАЩИЙ равно 2934. Второе условие принимает значение true в том и только в том случае, когда значения атрибутов СЛУ_НОМ и ПРОЕКТ_РУК переменных СЛУЖАЩИЙ и ПРОЕКТ совпадают.
По определению, простое сравнение является WFF, а WFF, заключенная в круглые скобки, представляет собой простое сравнение.
Более сложные варианты WFF строятся с помощью логических связок NOT, AND, OR и IF ... THEN с учетом обычных приоритетов операций (NOT > AND > OR) и возможности расстановки скобок. Так, если form – WFF, а comp – простое сравнение, то NOT form, comp AND form, comp OR form и IF comp THEN form являются WFF.
Для примеров воспользуемся отношениями СЛУЖАЩИЕ, ПРОЕКТЫ и НОМЕРА_ПРОЕКТОВ из предыдущей лекции (см. ).
Рис. 6.1. Примерные значения отношений СЛУЖАЩИЕ, ПРОЕКТЫ и НОМЕРА_ПРОЕКТОВ
Правильно построенной является следующая формула:
IF СЛУЖАЩИЙ.СЛУ_ИМЯ = 'Иванов' THEN (СЛУЖАЩИЙ.СЛУ_ЗАРП >= 22400.00 AND СЛУЖАЩИЙ.ПРО_НОМ = 1)
Эта формула будет принимать значение true для следующих значений кортежной переменной СЛУЖАЩИЙ:
| 2934 | Иванов | 22400.00 | 1 |
| 2935 | Петров | 29600.00 | 1 |
| 2936 | Сидоров | 18000.00 | 1 |
| 2937 | Федоров | 20000.00 | 1 |
| 2938 | Иванова | 22000.00 | 1 |
| 2935 | Петров | 29600.00 | 2 |
| 2939 | Сидоренко | 18000.00 | 2 |
| 2940 | Федоренко | 20000.00 | 2 |
| 2941 | Иваненко | 22000.00 | 2 |
Конечно, нужно представлять себе какой-нибудь способ реализации системы, которая сможет по заданной WFF при существующем состоянии базы данных произвести такой результат. И таким очевидным способом является следующий: в некотором порядке просмотреть область определения переменной и к каждому очередному кортежу применить условие.
Результатом будет то множество кортежей, для которых при вычислении условия производится значение true. Очевидно, что результат эквивалентен выполнению алгебраической операции СЛУЖАЩИЕ WHERE (NOT (СЛУЖАЩИЙ.СЛУ_ИМЯ = 'Иванов') OR (СЛУЖАЩИЙ.СЛУ_ЗАРП >= 22400.00 AND СЛУЖАЩИЙ.ПРО_НОМ = 1) над отношением, тело которого представляет собой область определения кортежной переменной.
Пусть имеется следующее определение кортежной переменной ПРОЕКТ:
RANGE ПРОЕКТ IS ПРОЕКТЫ
Вот еще пример правильно построенной формулы:
СЛУЖАЩИЙ.СЛУ_ИМЯ = ПРОЕКТ.ПРОЕКТ_РУК
Эта формула будет принимать значение true для следующих пар значений кортежных переменных СЛУЖАЩИЙ и ПРОЕКТ:
| 2934 | Иванов | 22400.00 | 1 | 1 | Иванов |
| 2941 | Иваненко | 22000.00 | 2 | 2 | Иваненко |
| 2934 | Иванов | 22400.00 | 2 | 1 | Иванов |
Здесь нужно сделать несколько замечаний. Во-первых, если бы в данном случае формула была тождественно истинной (например, имела вид
(СЛУЖАЩИЙ.СЛУ_ИМЯ = СЛУЖАЩИЙ.СЛУ_ИМЯ) AND (ПРОЕКТ.ПРОЕКТ_РУК = ПРОЕКТ.ПРОЕКТ_РУК))
то областью истинности этой формулы являлось бы декартово произведение (в строгом математическом смысле) тел отношений СЛУЖАЩИЙ и ПРОЕКТ. В реляционном исчислении кортежей, как и в реляционной алгебре, принято иметь дело с операцией расширенного декартова произведения, и поэтому считается, что в подобных случаях областью истинности WFF является отношение, заголовок которого представляет собой объединение заголовков отношений, на телах которых определены кортежные переменные, а кортежи являются объединением соответствующих кортежей из областей определения переменных.
При этом имя атрибута результирующего отношения уточняется именем соответствующей переменной. Поэтому правильнее было бы изображать область истинности формулы
СЛУЖАЩИЙ.СЛУ_ИМЯ = ПРОЕКТ.ПРОЕКТ_РУК
следующим образом:
| 2934 | Иванов | 22400.00 | 1 | 1 | Иванов |
| 2941 | Иваненко | 22000.00 | 2 | 2 | Иваненко |
| 2934 | Иванов | 22400.00 | 2 | 1 | Иванов |
Протокол упреждающей записи в журнал и его связь с буферизацией
Реальная ситуация является более сложной. Имеются два вида буферов – буфера журнала и буферный пул страниц основной памяти, – которые содержат связанную информацию. И те, и другие буфера могут выталкиваться во внешнюю память. Основной причиной выталкивания буфера журнала является его полное заполнение журнальными записями. Страницы буферного пула базы данных чаще всего выталкиваются во внешнюю память, когда требуется переместить в основную память некоторый блок базы данных, а свободных страниц в буферном пуле нет. Тогда срабатывает алгоритм замещения страниц, выбирается страница, содержимое которой, вероятно, дольше всего не потребуется, и эта страница (если ее содержимое изменялось) выталкивается в соответствующий блок внешней памяти базы данных. Проблема состоит в выработке некоторой общей политики выталкивания, которая обеспечивала бы возможность восстановления состояния базы данных после сбоев.
Заметим, что эта проблема не возникает при индивидуальных откатах транзакций, поскольку в этих случаях содержимое основной памяти не утрачено, и при восстановлении можно пользоваться содержимым как буфера журнала, так и буферных страниц базы данных. Но если произошел мягкий сбой, и содержимое буферов утрачено, то для проведения восстановления базы данных необходимо иметь некоторое согласованное состояние журнала и базы данных во внешней памяти.
Основным принципом согласованной политики выталкивания буфера журнала и буферных страниц базы данных является то, что запись об изменении объекта базы данных должна оказаться во внешней памяти журнала раньше, чем измененный объект окажется во внешней памяти базы данных. Соответствующий протокол журнализации (и управления буферизацией) называется WAL (Write Ahead Log, «пиши сначала в журнал») и состоит в том, что если требуется вытолкнуть во внешнюю память буферную страницу, содержащую измененный объект базы данных, то перед этим нужно гарантировать выталкивание во внешнюю память журнала буферной страницы журнала, содержащей запись об изменении этого объекта.
При следовании протоколу WAL, если во внешней памяти базы данных находится некоторый объект базы данных, по отношению к которому выполнена операция модификации, то во внешней памяти журнала обязательно находится запись, соответствующая этой операции. Обратное неверно, т.е. если во внешней памяти журнала содержится запись о некоторой операции изменения объекта базы данных, то сам измененный объект может отсутствовать во внешней памяти базы данных.
Дополнительное условие на выталкивание буферов накладывается тем требованием, что каждая успешно завершенная транзакция должна быть реально зафиксирована во внешней памяти. Какой бы сбой не произошел, система должна быть в состоянии восстановить состояние базы данных, содержащее результаты всех транзакций, зафиксированных до момента сбоя.
Самым простым решением было бы выталкивание буфера журнала, за которым следует массовое выталкивание буферов страниц базы данных, изменявшихся данной транзакцией. Довольно часто так и делают, но это вызывает существенные накладные расходы при выполнении операции фиксации транзакции.
Оказывается, что минимальным требованием, гарантирующим возможность восстановления последнего согласованного состояния базы данных, является выталкивание при фиксации транзакции во внешнюю память журнала всех записей об изменении базы данных этой транзакцией. При этом последней записью в журнал, производимой от имени данной транзакции, является специальная запись о конце транзакции.
Рассмотрим теперь, как можно выполнять операции восстановления базы данных в различных ситуациях, если в системе поддерживается общий для всех транзакций журнал с общей буферизацией записей, поддерживаемый в соответствии с протоколом WAL.
Проверочное табличное ограничение
Определение табличного ограничения вида CHECK (conditional_expression) приводит к тому, что указанное условное выражение будет вычисляться при каждой попытке обновления соответствующей таблицы (вставке новой строки, удалении или модификации существующей строки). Считается, что попытка обновления таблицы нарушает проверочное ограничение целостности, если после выполнения операции обновления вычисление условного выражения дает результат false. Другими словами, таблица находится в соответствии с данным проверочным табличным ограничением, если для всех строк таблицы результатом вычисления соответствующего условного выражения не является false.
Мы отложим обсуждение допустимых разновидностей условных выражений до следующей лекции, где оно будет более уместно в контексте рассмотрения оператора SELECT языка SQL.
Ранние модели данных
Начнем с рассмотрения общих подходов к организации трех типов ранних систем, а именно, систем, основанных на инвертированных списках, иерархических и сетевых систем управления базами данных. В целом ранние системы можно охарактеризовать следующим образом:
Эти системы активно использовались в течение многих лет, задолго до появления работоспособных реляционных СУБД. На самом деле некоторые из ранних систем используются даже в наше время, накоплены громадные базы данных, и одной из актуальных проблем информационных систем является использование этих систем совместно с современными. Все ранние системы не основывались на каких-либо абстрактных моделях. Как мы упоминали, понятие модели данных фактически вошло в обиход специалистов в области БД только вместе с реляционным подходом. Абстрактные представления ранних систем появились позже на основе анализа и выявления общих признаков у различных конкретных систем. В ранних системах доступ к БД производился на уровне записей. Пользователи этих систем осуществляли явную навигацию в БД, используя языки программирования, расширенные функциями СУБД. Интерактивный доступ к БД поддерживался только путем создания соответствующих прикладных программ с собственным интерфейсом.
Можно считать, что уровень средств ранних СУБД соотносится с уровнем файловых систем примерно так же, как уровень языка Cobol соотносится с уровнем языков ассемблера. Заметим, что при таком взгляде уровень реляционных систем соответствует уровню языков Ада или APL. Навигационная природа ранних систем и доступ к данным на уровне записей заставляли пользователей самих производить всю оптимизацию доступа к БД, без какой-либо поддержки системы. После появления реляционных систем большинство ранних систем было оснащено «реляционными» интерфейсами. Однако в большинстве случаев это не сделало их по-настоящему реляционными системами, поскольку оставалась возможность манипулировать данными в естественном для них режиме.
Раздел CYRCLE
Наконец, обсудим, для чего нужен раздел CYRCLE. Дело в том, что иногда сами данные, хранимые в таблицах базы данных, могут иметь циклическую природу. Представим себе, например, компанию, в которой существует совет директоров, являющийся высшим органом управления компанией. Обычным случаем является тот, когда по крайней мере один из членов совета директоров является простым служащим этой же компании (например, он может входить в совет директоров как представитель профсоюза). Назовем данного члена совета директоров EMP_DIR. Как член совета директоров, EMP_DIR «управляет» деятельностью президента компании. С другой стороны, как служащий компании, EMP_DIR находится в прямом или косвенном подчинении у президента компании. Такое положение может привести к зацикливанию выполнения рекурсивных запросов. Раздел CYRCLE обеспечивает некоторую возможность распознавать подобные ситуации. Если у пользователя имеется полная уверенность в отсутствии циклов в данных, к которым адресуется рекурсивный запрос, то использование раздела CYRCLE не требуется.
Подход к распознаванию зацикленных запросов, принятый в SQL, состоит в том, что распознаются данные, которые уже участвовали ранее в формировании результата рекурсивного запроса. При наличии раздела CYRCLE при добавлении к результату строк, удовлетворяющих условию запроса, такие строки помечаются указанным значением, которое означает, что эти строки уже вошли в результат. При попытке добавления к результату каждой новой строки проверяется, не находится ли она уже в результате, т. е. не помечена ли она этим указанным в разделе CYRCLE значением. Если это действительно так, то считается, что имеет место цикл, и дальнейшее выполнение рекурсивного запроса прекращается.
Обсудим все это более формально. Для удобства воспроизведем еще раз синтаксис раздела CYRCLE.
cycle_clause ::= CYCLE cycle_column_name_comma_list SET cycle_mark_column_name TO value_expression_1 DEFAULT value_expression_2 USING path_column_name
В списке cycle_column_name_comma_list указываются имена одного или нескольких столбцов, которые используются для идентификации новых строк результата на основе строк, уже входящих в результат.
Например, в примерах и столбец CONTAINED_PART связывает конструктивный элемент автомобиля с входящими в его состав подэлементами (через значения их столбцов CONTAINING_PART). Раздел SET приводит к образованию нового столбца результирующей таблицы. Для строк, которые попадают в результат первый раз, в столбец cycle_mark_column_name заносится значение выражения value_expression_2. В повторно заносимых строках значение столбца – value_expression_1. Типом данных этого столбца является тип символьных строк длины один, так что в качестве value_expression_1 и value_expression_2 разумно использовать константы '0' и '1' или 'Y' и 'N'.
Раздел USING приводит к образованию еще одного дополнительного столбца результата с именем path_column_name. Типом данных столбца является ARRAY, причем кардинальность этого типа предполагается достаточно большой, чтобы сохранить информацию обо всех строках, попавших в результат. Элементы массива имеют «строчный тип» (row type), содержащий столько столбцов, сколько их указано в списке раздела CYRCLE. Каждый элемент массива соответствует строке результата, и в его столбцах содержится копия значений соответствующих столбцов этой строки. Вот пример запроса, содержащего раздел CYRCLE (пример 20.5):
WITH RECURSIVE PARTS (PART_NUMBER, NUMBER_OF_PARTS, COST) AS (SELECT CONTAINED_PART, 1, 0.00 FROM CAR WHERE CONTAINING_PART = '' UNION ALL SELECT CAR.CONTAINED_PART, CAR.NUMBER_OF_PARTS, CAR.NUMBER_OF_PARTS * CAR.PART_COST FROM CAR, PARTS WHERE PARTS.PART_NUMBER = CAR.CONTAINING_PART) CYRCLE CONTAINED_PART SET CYCLEMARK TO 'Y' DEFAULT 'N' USING CYRCLEPATH SELECT PART_NUMBER, SUM(NUMBER_OF PARTS), SUM(COST) FROM PARTS ORDER BY PART_NUMBER;
Имена столбцов CYCLEMARK и CYRCLEPATH выбраны произвольным образом – требуется только, чтобы имена этих столбцов отличались от имен столбцов рекурсивного запроса. При выполнении запроса строки, удовлетворяющие его условию, накапливаются в результирующей таблице. Но, кроме того, эти строки «кэшируются» в столбце CYRCLEPATH.При попытке добавления к результату новой строки на основе текущего содержимого столбца CYRCLEPATH проверяется, не содержится ли она уже в результате. Если не содержится, то данные об этой строке добавляются к столбцу CYRCLEPATH (к массиву добавляется новый элемент), в столбец CYCLEMARK этой строки заносится значение 'N', и строка добавляется к результату. Иначе в столбец CYCLEMARK соответствующей строки результата заносится значение 'Y', означающее, что от этой строки начинается цикл.
Раздел GROUP BY CUBE
Наконец, заметим, что, в отличие от запросов с традиционной группировкой, результат запроса, содержащего раздел GROUP BY ROLLUP, зависит от порядка столбцов в списке группировки. При выполнении запроса происходит движение по этому списку слева направо с повышением уровня детальности результирующих данных. Существует еще одна разновидность запроса с группировкой, основанная на использовании раздела GROUP BY CUBE.
Пусть раздел группировки запроса имеет вид GROUP BY CUBE (cname1, cname2, ... , cnamen), где cnamei (i = 1, 2, ... , n) – имя столбца таблицы-результата раздела FROM запроса. Обозначим через SGBC множество {cname1, cname2, ... , cnamen}. Пусть Si является произвольным подмножеством SGBC, т.е. Si представляет собой пустое множество или имеет вид {cnamei1, cnamei2, ... , cnameim}, где m
Пример 20.2. Найти максимальный размер зарплаты во всем предприятии, максимальный размер зарплаты в каждом отделе, максимальный размер зарплаты служащих в каждой возрастной категории и максимальный размер зарплаты служащих каждой возрастной категории каждого отдела.
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 CUBE (DEPT_NO, EMP_BDATE);
Результирующая таблица для этого запроса будет иметь следующий вид:
Рис. 20.4. Результат запроса с разделом GROUP BY CUBE и вызовами агрегатной функции GROUPING к таблице с неопределенными значениями столбцов группировки
Как видно, результат запроса из совсем немного отличается от результата запроса из . Добавились две последние строки, показывающие максимальные значения зарплаты всех служащих предприятия, родившихся в 1950-м и 1960-м гг. соответственно.
Наш пример может навести на мысль, что и в общем случае запросы, содержащие раздел GROUP BY CUBE, не слишком отличаются от запросов с GROUP BY ROLLUP, и выполнение этих запросов тоже не слишком различается. Однако это совсем не так. Запрос, содержащий раздел GROUP BY CUBE, действительно вырождается в объединение результатов 2n запросов с обычным разделом GROUP BY. Соответственно, сложность выполнения такого запроса несравненно выше сложности выполнения похожего запроса с GROUP BY ROLLUP. В нашем примере все получилось так просто только по той причине, что в запросе имеются всего два столбца группировки.
Конечно, мы показали строки результирующей таблицы, расположенные в удобном для нас порядке только для упрощения объяснений. В действительности, строки результирующей таблицы (как обычно) будут расположены в порядке, определяемом системой. Чтобы добиться в точности такого порядка расположения строк, как это показано на , к формулировке запроса из нужно добавить раздел ORDER BY DEPT_NO
, EMP_BDATE
.
Мы опять искусственным образом упорядочили результат запроса для удобства пояснений.
Раздел GROUP BY ROLLUP
Эти же результаты можно получить при выполнении единственного запроса, если в его формулировке использовать специальный вид группировки ROLLUP (пример 20.1):
SELECT DEPT_NO, EMP_BDATE, MAX (EMP_SAL) AS MAX_SAL FROM EMP GROUP BY ROLLUP (DEPT_NO, EMP_BDATE);
Сначала покажем, как будет выглядеть результирующая таблица этого запроса, а потом приведем развернутое пояснение действия новой конструкции. В результате выполнения запроса будет получена таблица, показанная на .
Как видно, в столбце MAX_SAL первой строки результирующей таблицы находится максимальное значение зарплаты служащих на всем предприятии. Столбцы DEPT_NO и EMP_BDATE в этой строке содержат неопределенное значение, поскольку значение MAX_SAL не привязано к каким-либо отделу и возрастной категории. В столбце MAX_SAL следующих трех строк находятся максимальные значения зарплаты служащих отделов с номерами 1, 2 и 3 соответственно, что показывают значения столбца DEPT_NO. Столбец EMP_BDATE в этих строках содержит неопределенное значение, поскольку значение MAX_SAL не привязано к какой-либо возрастной категории. Наконец, в столбце MAX_SAL в последних шести строках содержатся максимальные значения зарплаты служащих каждой возрастной категории каждого отдела, что показывают значения столбцов DEPT_NO и EMP_BDATE, которые теперь содержат соответствующий номер отдела и год рождения служащих.
Рис. 20.1. Результат запроса с разделом GROUP BY ROLLUP
В общем случае пусть раздел группирn), где cnamei (i = 1, 2, ... , n) – имя столбца таблицы-результата раздела FROM запроса. Пусть в списке выборки используются вызовы агрегатных функций AGG1, AGG2, ... , AGGm над значениями столбцов, не входящих в список группировки, а также имена столбцов cname1, cname2, ... , cnamen. Тогда запрос выполняется следующим образом. Первая строка результата (первый набор строк результирующей таблицы) производится таким образом, как если бы в запросе вообще отсутствовал раздел GROUP BY, т.е. агрегатные функции AGG1, AGG2, ... , AGGm вычисляются над значениями всех строк таблицы.
Значением столбцов cname1, cname2, ... , cnamen в этой строке является NULL. (i+1)-й набор строк результата формируется так, как если бы раздел группировки запроса имел вид GROUP BY (cname1, cname2, ... , cnamei) (1
Может показаться, что запросы, содержащие раздел GROUP BY ROLLUP, настолько сложны, что их выполнение будет занимать чрезмерно большое время. Это ощущение является ложным. В действительности, при выполнении запросов с обычной группировкой вида GROUP BY cname1, cname2, ... , cnamen, как правило, последовательно выполняется сортировка строк таблицы-результата раздела FROM в соответствии со значениями столбца cname1, затем – в соответствии со значениями столбца cname2 и т. д., и в заключение – сортировка в соответствии со значениями столбца cnamen. Во время выполнения каждой сортировки можно заодно вычислять значения агрегатных функций. Так что стоимость выполнения запроса, содержащего раздел GROUP BY ROLLUP, лишь незначительно отличается от стоимости выполнения запроса с обычной группировкой.
Раздел объявления сигнатур методов
В разделе method_specification_commalist объявляются сигнатуры методов, ассоциируемых с определяемым структурным типом. Раздел определяется следующими синтаксическими правилами:
method_specification ::= original_method_specification | overriding_method_specification | static_field_method_specification original_method_specification ::= partial_method_specification [ SELF AS RESULT ] [ SELF AS LOCATOR ] [ method_characteristic_list ] overriding_method_specification ::= OVERRIDING partial_method_specification partial_method_specification :== [ INSTANCE | STATIC | CONSTRUCTOR ] METHOD method_name SQL_parameter_declaration_list return_clause [ SPECIFIC specific_method_name ] method_characteristic ::= language_clause | parameter_style_clause | deterministic_clause | SQL_data_access_indication | null_call_clause specific_method_name ::= [ schema_name . ] qualified_identifier static_field_method_specification ::= STATIC METHOD method_name ( ) RETURNS data_type [ SPECIFIC specific_method_name ] external variable name character_string_literal
Как показывает синтаксис, имеются возможности определять первичные методы (original_method_specification), неприменимые к любому супертипу определяемого структурного типа. Если определяемый тип является подтипом некоторого другого типа, то можно также определить подменяющие методы (overriding_method_specification). Подменяющий метод имеет то же имя и тот же список аргументов, что и метод, определенный в некотором супертипе определяемого типа.
Исходный метод может быть определен как метод экземпляра (INSTANCE), статический метод (STATIC) или метод-конструктор (CONSTRUCTOR). Методы экземпляра действуют над экземплярами определяемого типа. Статические методы не используют экземпляры типа и не влияют на них; такие методы действуют над самим типом. Наконец, методы-конструкторы используются для инициализации экземпляров типа. Поскольку у неинстанциируемого типа не может быть экземпляров, для него могут быть определены только статические методы.
Если при определении первичного метода его разновидность не указывается, этот метод считается методом экземпляра.
В сигнатуре метода указывается имя, по которому этот метод будет вызываться (вызывное имя – invocable name). Кроме того, можно указать точное имя метода (specific name), которое может использоваться для уникальной идентификации метода, если его вызывное имя перегружено. Если у метода имеются какие-либо параметры, отличные от неявного параметра SELF, то в определении должен присутствовать заключенный в скобки список пар <имя_параметра, тип_параметра>, разделяемых запятыми. Поскольку методы являются функциями, требуется указать тип возвращаемого значения. Методы могут возвращать значения любого допустимого в SQL типа, даже структурного типа, ассоциированного с методом.
Наконец, у каждого метода имеется набор характеристик метода (method_characteristic). Методы могут быть написаны на языке SQL (более точно, на SQL/PSM) или на любом из языков программирования, поддержка которых предусмотрена в стандарте SQL (Ada, C/C++, COBOL, Fortran, MUMPS, Pascal, PL/1). Язык Java поддерживается в стандарте в несколько иной манере, чем другие языки. Список параметров метода может быть определен в стиле, более соответствующем стилю SQL-подпрограмм (каждый параметр может принимать неопределенное значение, и не требуется параметр кода возврата). Для этого в качестве характеристики метода нужно указать PARAMETER STYLE SQL. Можно определить список параметров в стиле, более близком стилю различных языков программирования (к параметру, который может принимать неопределенное значение, должен быть добавлен дополнительный параметр-индикатор, и должен быть явно определен выходной параметр кода ответа). В этом случае метод должен иметь характеристику PARAMETER STYLE GENERAL. Наконец, для методов, тела которых будут написаны на языке Java, нужно указать характеристику PARAMETER STYLE JAVA.
Любой метод может быть детерминированным (DETERMINISTIC) или недетерминированным (NOT DETERMINISTIC).
Детерминированный метод всегда возвращает один и тот же результат, если вызывается с одним и тем же набором аргументов при одном и том же состоянии базы данных. По умолчанию методы считаются недетерминированными.
У каждого метода имеется характеристика, указывающая связь этого метода с SQL. Можно указать следующие варианты: метод не содержит операторов SQL (NO SQL);метод содержит операторы SQL, но не обращается к базе данных (CONTAINS SQL);метод может производить выборку из базы данных, но не обновляет базу данных (READS SQL DATA);в методе допускаются обновления базы данных (MODIFIES SQL DATA).
По умолчанию принимается характеристика CONTAINS SQL. Наконец, для каждого метода можно определить его реакцию на аргументы, являющиеся неопределенными значениями. Если указывается RETURN NULL ON NULL INPUT, то метод всегда возвращает неопределенное значение, если значение любого из его аргументов является неопределенным (независимо от того, что написано в теле функции, реализующей метод). Если же указывается CALLED ON NULL INPUT (или если характеристика явно не задана), то метод всегда явно выполняется (т. е. происходит вызов соответствующей функции) при вызове с любым набором аргументов.
Кстати, не очень понятно, по каким причинам в стандарте SQL не поддерживается наследование для индивидуальных типов. Конечно, этот механизм существенно более полезен для структурных типов, но его вполне можно было бы реализовать и для индивидуальных типов.
Как уже отмечалось ранее, раздел подтипизации может присутствовать только при определении структурного UDT.
А в стандарте SQL:2003 и MULTISET.
Последнее ограничение является непонятным. Его можно обойти, например, следующим образом. Пусть структурный тип T' определяется как подтип типа T, и мы хотим включить в представление типа T' атрибут a типа T. Тогда предварительно определим тип T'' как подтип типа T в точности с тем же представлением. Тогда ничто не помешает определить в представлении типа T' атрибут a типа T''.
Мы вынуждены следовать терминологии стандарта SQL, которая иногда бывает довольно нечеткой.
В частности, по отношению к структурным типам используются термины значение (value) во вполне стандартном смысле; местоположение (site) как расширенное понятие переменной (нечто, содержащее значение структурного типа); экземпляр (instance). Последний термин в объектной терминологии обычно используется в том же смысле, что объект класса. В случае SQL это строка типизированной таблицы (см. следующий раздел).
Мы снова используем обороты, принятые в стандарте SQL. Заметим, что, хотя смысл неинстанциируемого типа должен быть интуитивно понятен, приведенное определение является очень нечетким. Классическое (не вполне строгое) понятие типа данных основывается на паре <множество_значений, набор_операций>. Поэтому нельзя создать значение типа, можно только выбрать его из соответствующего множества значений. Поэтому, строго говоря, в типе данных не может присутствовать «метод-конструктор», а может иметься (или не иметься) операция выборки значения. У неинстациируемых типов такая операция отсутствует.
Теперь этот язык называется M. Вокруг этого языка и его реализаций имеется, в частности, целое семейство СУБД, основанных на так называемой M-технологии. Судя по всему, наиболее успешной представительницей этого семейства является СУБД Cache известной компании InterSystems.
Этот абзац, в частности, показывает, как много нужно знать технических (и не только технических) подробностей, чтобы реально освоить технику определения UDT в среде SQL.
Раздел SEARCH
В приведенном выше примере не определялся порядок, в котором строки добавляются к частичному результату рекурсивного запроса. Однако иногда требуется, чтобы иерархия обходилась в глубину или в ширину. Соответствующая возможность обеспечивается конструкцией SEARCH. При указании требования обхода в глубину гарантируется, что каждый элемент-предок появится в результате раньше своих потомков и своих братьев справа. Если указывается требование обхода иерархии в ширину, в результате все братья одного уровня появляются раньше, чем какой-либо их потомок. Ниже показан вариант запроса, в котором содержится раздел SEARCH с требованием обхода иерархии элементов автомобиля в ширину (пример 20.4).
WITH RECURSIVE PARTS (ASSEMBLY, PART_NUMBER, NUMBER_OF_PARTS, COST) AS (SELECT CONTAINING_PART, CONTAINED_PART, 1, 0.00 FROM CAR WHERE CONTAINING_PART = '' UNION ALL SELECT CAR.CONTAINING_PART, CAR.CONTAINED_PART, CAR.NUMBER_OF_PARTS, CAR.NUMBER_OF_PARTS * CAR.PART_COST FROM CAR, PARTS WHERE PARTS.PART_NUMBER = CAR.CONTAINING_PART) SEARCH BREADTH FIRST BY CONTAINING_PART, CONTAINED_PART SET ORDER_COLUMN SELECT PART_NUMBER, NUMBER_OF PARTS, COST FROM PARTS ORDER BY ORDER_COLUMN;
В списке столбцов сортировки раздела SEARCH должны указываться имена столбцов виртуальной таблицы, определенной в разделе WITH. Поскольку в данном случае мы хотим, чтобы в результате сначала появлялись все конструктивные элементы одного уровня (CONTAINING_PART), а затем все их подэлементы (CONTAINED_PART), в список выборки рекурсивного запроса PARTS добавлен столбец CONTAINING_PART, который не используется нигде, кроме раздела SEARCH. В разделе SET к результирующей таблице рекурсивного запроса добавлен столбец, который мы назвали ORDER_COLUMN. Название соответствует природе столбца, потому что при выполнении рекурсивного запроса в этот столбец автоматически заносятся значения, характеризующие порядок генерируемых строк в соответствии с выбранным способом обхода иерархии. Чтобы строки результата основного запроса появлялись в должном порядке, в этом запросе требуется наличие раздела ORDER BY с указанием столбца, определенного в разделе SET.
Раздел спецификации ссылочного типа
Хотя типизированные таблицы обсуждаются в следующем разделе, мы вынуждены немного забежать вперед, чтобы ввести синтаксис и пояснить смысл раздела reference_type_specification определения структурного типа. Строки типизированных таблиц обладают всеми характеристиками объектов в объектно-ориентированных системах, включая уникальные идентификаторы, которые могут использоваться для ссылок из других компонентов среды. В SQL:1999 поддерживаются три различных механизма присваивания уникальных идентификаторов экземплярам структурных типов, ассоциированных с такими таблицами (для всех строк таблицы, ассоциированной с данным структурным типом, используется один и тот же механизм). Уникальные идентификаторы экземпляров структурного типа могут представлять собой следующее: значения, генерируемые системой автоматически (system_generated_representation);значения некоторого встроенного типа SQL, которые должны генерироваться приложением при сохранении экземпляра структурного типа как строки типизированной таблицы (user_generated_representation);значения, порождаемые из одного или нескольких атрибутов структурного типа (derived_representation).
Соответственно, синтаксис раздела reference_type_specification определяется следующими правилами:
reference_type_specification ::= system_generated_representation | user_defined_representation | derived_representation system_generated_representation :== REF IS SYSTEM GENERATED user_defined_representation :== REF USING predefined_type derived_representation ::= REF USING (commalist_of_attributes)
Раздел reference_type_specification может присутствовать только в определении максимального структурного супертипа, т. е. соответствующая спецификация наследуется всеми подтипами этого супертипа. При отсутствии в определении супертипа явного раздела reference_type_specification по умолчанию предполагается наличие раздела REF IS SYSTEM GENERATED.
Раздел WHEN
Включение в определение триггера раздела WHEN с соответствующим условным выражением позволяет более точно специфицировать условие применимости триггера. Вычисление условного выражения производится над строками предметной таблицы, и триггер срабатывает только в том случае, когда значением условного выражения является true. Понятно, что виды и интерпретация логических выражений, допускаемых в разделе WHEN, различаются у триггеров с FOR EACH ROW и у триггеров с FOR EACH STATEMENT. В первом случае условное выражение вычисляется для одной строки, которая должна быть обновлена инициирующим SQL-оператором. Во втором – условное выражение вычисляется для всей предметной таблицы целиком и, по всей видимости, должно базироваться на «кванторных» предикатах. Следует также понимать, что вычисление условия раздела WHEN данного триггера производится только в том случае, если произошло событие срабатывания триггера.
Раздел WITH CHECK OPTION определения представления
Пусть в базе данных имеется упрощенная таблица EMP, содержащая следующее множество строк (как в примере с GROUP BY ROLLUP разделе лекции 20):
| 2440 | 1 | 1950 | 15000.00 |
| 2441 | 1 | 1950 | 16000.00 |
| 2442 | 1 | 1960 | 14000.00 |
| 2443 | 1 | 1960 | 19000.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 |
Предположим, что в базе данных имеется представление RICH_EMP, определенное следующим образом: CREATE VIEW RICH_EMP AS SELECT * FROM EMP WHERE EMP_SAL > 18000.00;
Понятно, что в соответствии с правилами SQL (и здравым смыслом) над этим представлением можно выполнять операции обновления. Как видно, в таблице EMP содержится строка, которая соответствует служащему с номером 2447, получающему зарплату в размере 20000 руб. Естественно, эта строка будет присутствовать в виртуальной таблице RICH_EMP. Поэтому можно было бы выполнить, например, операцию UPDATE RICH_EMP SET EMP_SAL = EMP_SAL – 3000 WHERE EMP_NO = 4452;
Но если выполнение такой операции действительно допускается, то в результате строка, соответствующая служащему с номером 2447, исчезнет из виртуальной таблицы RICH_EMP! Аналогичный эффект возникнет при выполнении операции вставки
INSERT INTO RICH_EMP (EMP_NO) 2452;
В базовой таблице EMP появится строка, в которой значением столбца EMP_NO будет 2452, а значения остальных столбцов будут установлены по умолчанию. В частности, значением столбца EMP_SAL будет 10000.00. Тем самым, если подобная операция вставки действительно допустима, то мы вставили в виртуальную таблицу RICH_EMP строку, которую в этой виртуальной таблице увидеть невозможно.
Чтобы избежать такого противоречивого поведения представляемых таблиц, нужно включать в определение представления раздел WITH CHECK OPTION. При наличии этого раздела до реального выполнения операций модификации или вставки строк через представление для каждой строки будет проверяться, что она соответствует условиям представления. Если данное условие не выполняется хотя бы для одной модифицируемой или вставляемой строки, то операция полностью отвергается. В некотором смысле (при наличии раздела WITH CHECK OPTION) условие выборки, содержащееся в выражении запросов представления, можно считать ограничением целостности этого представления.
Раздел WITH выражения запросов
Как видно из синтаксиса выражения запросов, в этом выражении может присутствовать раздел WITH. Он задается в следующем синтаксисе:
with_clause ::= WITH [ RECURSIVE ] with_element_comma_list with_element ::= query_name [ (column_name_list) ] AS (query_expression) [ search_or_cycle_clause ]
Общую форму раздела WITH мы обсудим в лекции 20, когда будем рассматривать средства формулировки рекурсивных запросов. Пока ограничимся случаем, когда в разделе WITH отсутствуют спецификация RECURSIVE и search_or_cycle_clause. Тогда конструкция
WITH query_name (c1, c2, … cn) AS (query_exp_1) query_exp_2
означает, что в любом месте выражения запросов query_exp_2, где допускается появление ссылки на таблицу, можно использовать имя query_name. Можно считать, что перед выполнением query_exp_2 происходит выполнение query_exp_1, и результирующая таблица с именами столбцов c1, c2, … cn сохраняется под именем query_name. Как мы увидим позже, в этом случае раздел WITH фактически служит для локального определения представляемой таблицы (VIEW).
Разделы спецификации функций явного преобразования типов
Если в определении структурного типа присутствует раздел reference_type_specification и он имеет вид user_generated_representation, то в определении структурного типа должен присутствовать и раздел ref_cast_option (тем самым, раздел ref_cast_option может присутствовать только в определении максимального структурного супертипа). Спецификации этого раздела используются для преобразования предоставленных приложением значений встроенного типа в значения типа REFERENCE (REF) , необходимые для реального выполнения ссылок на строки типизированной таблицы, и обратного преобразования. Синтаксис раздела определяется следующими правилами (подробнее см. в следующем разделе):
ref_cast_option ::= cast_to_ref | cast_to_type cast_to_ref ::= CAST (SOURCE AS REF) WITH identifier cast_to_type ::= CAST (REF AS SOURCE) WITH identifier
Раздел cast_option может присутствовать только в определении индивидуального типа. Спецификации раздела обеспечивают возможности преобразования значений индивидуального типа в значения базового встроенного типа, и наоборот. Раздел имеет следующий синтаксис:
cast_option ::= cast_to_distinct | cast_to_source cast_to_distinct ::= CAST (SOURCE_TO_DISTINCT) WITH identifier cast_to_source ::= CAST (DISTINCT_TO_SOURCE) WITH identifier
Разновидности способов сопоставления значений внешнего и возможного ключей
Пусть определяемая таблица имеет имя S. Обсудим смысл необязательного раздела определения внешнего ключа MATCH { SIMPLE | FULL | PARTIAL }. Если этот раздел отсутствует или если присутствует и имеет вид MATCH SIMPLE, то ограничение внешнего ключа (ссылочное ограничение) удовлетворяется в том и только в том случае, когда для каждой строки таблицы S выполняется одно из следующих условий: (a) какой-либо столбец, входящий в состав внешнего ключа, содержит NULL;(b) таблица T содержит в точности одну строку, такую, что значение внешнего ключа в данной строке таблицы S совпадает со значением соответствующего возможного ключа в этой строке таблицы T.
Если раздел MATCH присутствует в определении внешнего ключа и имеет вид MATCH PARTIAL, то ограничение внешнего ключа удовлетворяется в том и только в том случае, когда для каждой строки таблицы S выполняется одно из следующих условий: (a) каждый столбец, входящий в состав внешнего ключа, содержит NULL;(b) таблица T содержит по крайней мере одну такую строку, что для каждого столбца данной строки таблицы S, значение которого отлично от NULL, его значение совпадает со значением соответствующего столбца возможного ключа в этой строке таблицы T.
Если раздел MATCH имеет вид MATCH FULL, то ограничение внешнего ключа удовлетворяется в том и только в том случае, когда для каждой строки таблицы S выполняется одно из следующих условий: (a) каждый столбец, входящий в состав внешнего ключа, содержит NULL;(b) ни один столбец, входящий в состав внешнего ключа, не содержит NULL, и таблица T содержит в точности одну строку, такую, что значение внешнего ключа в данной строке таблицы S совпадает со значением соответствующего возможного ключа в этой строке таблицы T.
Очевидно, что только при наличии спецификации MATCH FULL ссылочное ограничение соответствует требованиям реляционной модели. Тем не менее, в определении ограничения внешнего ключа базовых таблиц в SQL по умолчанию предполагается наличие спецификации MATCH SIMPLE.
Разрушение тупиков
Нужно каким-то образом обеспечить возможность продолжения работы хотя бы для части транзакций, попавших в тупик. Разрушение тупика начинается с выбора в цикле транзакций так называемой транзакции-жертвы, т.е. транзакции, которой решено пожертвовать, чтобы обеспечить возможность продолжения работы других транзакций.
Выбрать «жертву» не так уж легко, поскольку для этого могут использоваться различные, зачастую противоречивые критерии. С одной стороны, было бы разумно жертвовать наиболее «богатой» транзакцией, т.е. той транзакцией, которая удерживает наиболее число блокировок объектов. В этом случае после принудительно завершения такой транзакции освободилось бы наибольшее число объектов, что с большой вероятностью привело бы к исчезновению тупиковой ситуации. Но, с другой стороны, «богатая» транзакция, скорее всего, выполнялась дольше других транзакций. На ее выполнение уже затрачено большое количество системных ресурсов и, вероятно, она скоро завершится самостоятельно. Поэтому этот выбор может оказаться в системном отношении не самым удачным.
Можно пожертвовать самой «молодой» транзакцией, которая существует в системе в течение наименьшего времени. Такую транзакцию менее всего жалко, поскольку она еще не успела израсходовать много системных ресурсов. Но, с другой стороны, такая транзакция не могла и накопить много блокировок, и поэтому ее насильственное завершение вряд ли поможет устранить тупиковую ситуацию. Так стоит ли ею жертвовать?
Можно выбрать транзакцию-жертву случайным образом из всех транзакций, попавших в тупик. Возможно, что в среднем этот подход привел бы к хорошим результатам. Но, к сожалению, в нем не учитывается возможная приоритетность транзакций. Было бы не слишком хорошо, например, жертвовать транзакцией, запущенной от имени руководителя организации.
Поэтому обычно при выборе транзакции-жертвы используется многофакторная оценка ее стоимости, в которую с разными весами входят время выполнения, число накопленных блокировок, приоритет и т.д. В качестве «жертвы» выбирает транзакция, для которой эта оценка выдает наиболее подходящий результат.
После выбора транзакции-жертвы выполняется откат этой транзакции, который может носить полный или частичный (до некоторой точки сохранения) характер. При этом, естественно, освобождаются блокировки, и может быть продолжено выполнение других транзакций.
Естественно, такое насильственное устранение тупиковых ситуаций является нарушением принципа изолированности пользователей, которого невозможно избежать.
Заметим, что в централизованных системах стоимость построения графа ожидания сравнительно невелика, но она становится слишком большой в распределенных СУБД, в которых транзакции могут выполняться в разных узлах сети. Поэтому в таких системах обычно используются другие методы сериализации транзакций.
Рекурсивные представления
Рекурсивным называется представление, в определяющем выражении запроса которого используется имя этого же представления. В представлениях может использоваться и прямая, и взаимная рекурсия. Синтаксис оператора определения рекурсивного запроса выглядит следующим образом:
CREATE RECURSIVE VIEW table_name [ column_name_comma_list ] AS query_expression
Хотя для того, чтобы представление было рекурсивным, требуется рекурсивность определяющего выражения запроса (т.е. в нем должна присутствовать спецификация RECURSIVE); наличие избыточного ключевого RECURSIVE в определении рекурсивного представления является обязательным. Как говорят авторы стандарта, это сделано для того, чтобы избежать случайного появления непредусмотренных рекурсивных представлений. Наконец, обратите внимание на то, что еще не обсуждавшийся нами необязательный раздел WITH CHECK OPTION не может присутствовать в определении рекурсивного представления (по той причине, что разработчики стандарта не смогли найти разумной интерпретации для комбинации RECURSIVE и WITH CHECK OPTION).
В заключение этого раздела могу сказать, что лично мне механизм рекурсии, предлагаемый в стандарте SQL, представляется громоздким и ограниченным. Кроме того, насколько мне известно, компании, поставляющие SQL-ориентированные СУБД, не спешат внедрять в свои продукты средства рекурсии в соответствии со стандартом SQL:1999 (или, по крайней мере, не слишком их афишируют).
Рекурсивные запросы
Начнем этот раздел с нескольких определений, касающихся понятий, которые связаны с рекурсией. Эти понятия имеют общий характер, но в приведенных ниже определениях и комментариях к ним (там, где это уместно) подчеркивается контекст SQL.
Рекурсивные запросы с разделом WITH
В предыдущих лекциях мы уже говорили о разновидности спецификации ссылки на таблицу с использованием раздела WITH. Однако мы умышленно отложили обсуждение рекурсивных возможностей. Полный синтаксис раздела WITH выглядит следующим образом:
with_clause ::= WITH [ RECURSIVE ] with_element_comma_list with_element ::= query_name [ (column_name_list) ] AS ( query_expression ) [ search_or_cycle_clause ] search_or_cycle_clause ::= search_clause | cycle_clause | search_clause cycle_clause search_clause ::= SEARCH recursive_search_order SET sequence_column_name recursive_search_order ::= DEPTH FIRST BY order_item_commalist | BREADTH FIRST BY order_item_commalist cycle_clause ::= CYCLE cycle_column_name_comma_list SET cycle_mark_column_name TO value_expression DEFAULT value_expression USING path_column_name
Для иллюстрации возможностей рекурсивных запросов с разделом WITH и пояснения смысла конструкций SEARCH и CYCLE воспользуемся классическим примером «разборки деталей» (в данном случае мы будем разбирать автомобиль). Предположим, что данные о конструктивных элементах автомобиля хранятся в таблице CAR, определенной следующим образом:
CREATE TABLE CAR (CONTAINING_PART VARCHAR (10), CONTAINED_PART VARCHAR (10), NUMBER_OF_PARTS INTEGER, PART_COST DECIMAL (6,2));
У автомобиля имеется один конструктивный элемент верхнего уровня – полностью собранный автомобиль. Этот элемент не является составной частью какого-либо другого элемента, и для его строки значением столбца CONTAINING_PART является текстовая строка длины 0. В любой другой строке таблицы CAR, соответствующей некоторому неатомарному конструктивному элементу e, столбец CONTAINING_PART содержит идентификационный номер элемента e1, в который входит элемент e, столбец NUMBER_OF_PARTS – число экземпляров элемента e, входящих в e1, а столбец CONTAINED_PART – идентификационный номер самого элемента e. В любой строке таблицы CAR, соответствующей некоторому атомарному конструктивному элементу, значением столбца CONTAINED_PART является строка длины 0, а в столбце PART_COST сохраняется цена атомарного конструктивного элемента (для неатомарных элементов значение этого столбца равно нулю).
Предположим, что нам требуется разобрать автомобиль, начиная с элемента самого верхнего уровня, и для каждого конструктивного элемента получить его номер, общее число используемых экземпляров этого элемента, а также, если элемент является атомарным, общую стоимость используемых экземпляров. Вот возможная формулировка запроса (пример 20.3):
WITH RECURSIVE PARTS (PART_NUMBER, NUMBER_OF_PARTS, COST) AS (SELECT CONTAINED_PART, 1, 0.00 (a) FROM CAR WHERE CONTAINING_PART = '' UNION ALL SELECT CAR.CONTAINED_PART, CAR.NUMBER_OF_PARTS, CAR.NUMBER_OF_PARTS * CAR.PART_COST FROM CAR, PARTS WHERE PARTS.PART_NUMBER = CAR.CONTAINING_PART) SELECT PART_NUMBER, SUM(NUMBER_OF PARTS), SUM(COST) (b) FROM PARTS GROUP BY PART_NUMBER;
Этот запрос будет выполняться следующим образом. При вычислении раздела FROM основного запроса (b) начнется выполнение рекурсивного выражения запросов (a), определенного в разделе WITH. На первом шаге рекурсии будет выполнена часть данного выражения, предшествующая операции UNION ALL и образующая начальный источник рекурсии. В результате будет произведено исходное состояние виртуальной таблицы PARTS, в котором, в нашем случае, появится единственная строка, соответствующая автомобилю целиком. На следующем шаге к таблице PARTS будут добавлены строки, соответствующие конструктивным элементам второго уровня (для автомобиля это, по-видимому, двигатель, колеса, шасси и т.д.). Этот процесс будет продолжаться до тех пор, пока мы не дойдем до атомарных конструктивных элементов и не достигнем, тем самым, фиксированной точки. Поскольку в рекурсивном запросе содержится операция UNION ALL, в результирующей таблице могут появляться строки-дубликаты. Наличие строки-дубликата вида <part_no, number, cost> означает, что элемент с номером part_no входит в одном и том же числе экземпляров в несколько конструктивных элементов более высокого уровня.
Реляционная модель данных
Когда в предыдущих разделах мы говорили об основных понятиях реляционных баз данных, мы не опирались на какую-либо конкретную реализацию. Эти рассуждения в равной степени относятся к любой системе, при построении которой использовался реляционный подход.
Другими словами, мы использовали понятия так называемой реляционной модели данных. Модель данных (в контексте области баз данных) описывает некий набор родовых понятий и признаков, которыми должны обладать все конкретные СУБД и управляемые ими базы данных, если они основываются на этой модели. Наличие модели данных позволяет сравнивать конкретные реализации, используя один общий язык.
Хотя понятие модели данных является общим (см. Лекцию 2), и можно говорить об иерархической, сетевой, семантической и других моделях данных, нужно отметить, что в области баз данных это понятие было введено Эдгаром Коддом применительно к реляционным системам и наиболее эффективно используется именно в данном контексте.
Реляционное деление
Пусть имеются отношения r1{A, B} и r2{B}. Утверждается, что результат r1 DIVIDE BY r2 совпадает с результатом выражения (r1 PROJECT A) MINUS (((r2 TIMES (r1 PROJECT A)) MINUS r1) PROJECT A) в терминах операций реляционной алгебры Кодда или (r1 <REMOVE> B) <AND> <NOT> (((r2 <AND> (r1 <REMOVE> B)) <AND> <NOT> r1) <REMOVE> B) в терминах операций Алгебры A.
Действительно, результатом выполнения операции r1 PROJECT A является унарное отношение со схемой {A}, кортежи тела которого содержат все значения атрибута A из тела отношения r1. Результат выражения r2 TIMES (r1 PROJECT A) – это бинарное отношение со схемой {A, B}, в тело которого входят все возможные комбинации значений атрибута B в теле отношения r2 и атрибута A в теле отношения r1. В теле результата вычисления выражения (r2 TIMES (r1 PROJECT A)) MINUS r1 останутся только те кортежи, которые не входят во второй операнд, т. е. кортежи с таким значением атрибута A, что значение атрибута B, принадлежащее телу r2, не является значением атрибута B ни в одном кортеже тела отношения r1. Следовательно, если мы возьмем проекцию результата выражения (r2 TIMES (r1 PROJECT A)) MINUS r1 на атрибут A, то в результирующем унарном отношении останутся только те значения A, которые не должны попасть в результат операции r1 DIVIDE BY r2. После выполнения завершающей операции MINUS мы получим желаемый результат.
Для иллюстрации воспользуемся отношениями СЛУЖАЩИЕ и НОМЕРА_ПРОЕКТОВ, которые мы уже применяли в предыдущих примерах. Для удобства мы воспроизводим их на . На этом же рисунке показаны промежуточные и окончательный результаты вычисления выражения (СЛУЖАЩИЕ PROJECT {СЛУ_НОМЕР, СЛУ_ИМЯ, СЛУ_ЗАРП}) MINUS ((((СЛУЖАЩИЕ PROJECT {СЛУ_НОМЕР, СЛУ_ИМЯ, СЛУ_ЗАРП}) TIMES НОМЕРА_ПРОЕКТОВ) MINUS СЛУЖАЩИЕ) PROJECT {СЛУ_НОМЕР, СЛУ_ИМЯ, СЛУ_ЗАРП}).
Рис. 5.14. Выражение операции DIVIDE BY через другие операции Алгебры A
Тем самым, мы показали, что пяти операций Алгебры A достаточно для выражения всех операций алгебры Кодда из лекции 4. Но на самом деле число операций можно еще более сократить, что мы и продемонстрируем в следующем разделе.
Реляционные аналоги штриха Шеффера и стрелки Пирса
Более того, в алгебре логики существуют две операции, через каждую из которых выражаются все три «базовые» операции: «штрих Шеффера» – sh (A, B)
Легко видеть, что sh (A, A)
Аналогично, pi (A, A)
Снова нетрудно проверить, что аналогичные тождества справедливы для реляционных вариантов штриха Шеффера (<sh> (r1, r2)
Поэтому можно свести набор операций Алгебры A к трем операциям: <sh> (или <pi>), <RENAME> и <REMOVE>.
Реляционные структуры данных
Основная идея Кодда состояла в том, чтобы выбрать в качестве родовой логической структуры хранения данных структуру, которая, с одной стороны, была бы достаточно удобной для большинства приложений и, с другой стороны, допускала бы возможность выполнения над базой данных ненавигационных операций. Иерархические и, в особенности, сетевые структуры данных являются навигационными по своей природе. Ненавигационному использованию таблиц мешает упорядоченность их столбцов и, в особенности, строк.
По сути, Кодд предложил использовать в качестве родовой структуры БД «таблицы», в которых и столбцы, и строки не являются упорядоченными. Легко видеть, что такая «таблица» со множеством столбцов {A1, A2, …, An}, в которой каждый столбец Ai
может содержать значения из множества Ti
= {vi1,
vi2, …, vim}
(все множества конечны), в математическом смысле представляет собой отношение над множествами {T1, T2, …, Tn}. Напомню, что в математике отношением над множествами {T1, T2, …, Tn}
называется подмножество декартова произведения этих множеств, т.е. некоторое множество кортежей {{v1,
v2, …, vn}}, где vi
Ti. Поэтому для обозначения родовой структуры Кодд стал использовать термин отношение (relation), а для обозначения элементов отношения – термин кортеж. Соответственно, модель данных получила название реляционной модели.
Схема БД в реляционной модели данных – это набор именованных заголовков отношений
вида Hi
= {<Ai1, Ti1>, < Ai2, Ti2>, …, <
Aini, Tini>}. Ti
называется доменом атрибута Ai. По Кодду, каждый домен Ti
является подмножеством значений некоторого базового типа данных Ti+, а значит, к его элементам применимы все операции этого базового типа (в конце 1960-х гг. базовыми типами данных считались типы данных распространенных тогда языков программирования; в IBM наиболее популярными языками были PL1 и COBOL).
Реляционная база данных в каждый момент времени представляет собой набор именованных отношений, каждое из которых обладает заголовком, таким как он определен в схеме БД, и телом. Имя отношения Ri
совпадает с именем заголовка этого отношения HRi.
Тело отношения BRi
– это множество кортежей вида {<Ai1, Ti1, vi1>, < Ai2, Ti2, vi2>, …, <
Aini, Tini, vini>}, где tij
Tij. Во время жизни БД тела отношений могут изменяться, но все содержащиеся в них кортежи должны соответствовать заголовкам соответствующих отношений.
Режимы проверки CASCADED и LOCAL
Вспомним теперь, что в полном виде синтаксис раздела WITH CHECK OPTION может включать ключевые слова CASCADED или LOCAL (см. подраздел лекции 17). Обсудим их смысл. Предположим, что представление V2 определяется над представлением V1 следующим образом: CREATE VIEW V2 AS SELECT ... FROM V1 WHERE ... [ WITH [ CASCADED | LOCAL ] CHECK OPTION ]
Пусть над V2 выполняется некоторая операция O обновления базы данных. Тогда: если представление V2 определялось без раздела WITH CHECK OPTION, то при выполнении операции O будут проверяться все условия, определяющие ограничения целостности V1 (если в определении V1 присутствовал раздел WITH CHECK OPTION), но никаким образом не будут учитываться условия выборки, содержащееся в выражении запросов представления V2;если в определении представления V2 содержался раздел WITH LOCAL CHECK OPTION, то при выполнении операции O будут проверяться все условия, определяющие ограничения целостности V1, и все условия, содержащееся в выражении запросов представления V2;наконец, если в определении представления V2 содержался раздел WITH CASCADED CHECK OPTION, то при выполнении операции O будут проверяться все условия, определяющие ограничения целостности V1 (так, как если бы в определении V1 присутствовал раздел WITH CASCADED CHECK OPTION). Тем самым, будут проверяться все ограничения целостности, установленные для всех базовых таблиц, на которых основывается определение V1; все условия всех представлений, определенных над этими базовыми таблицами; и, конечно, все условия, содержащиеся в выражении запросов представления V2.
Результаты запросов и агрегатные функции
Об использовании агрегатных функций в разделах HAVING и SELECT оператора выборки упоминалось в подразделе лекции 17. В данном подразделе уместно повторить и уточнить этот материал.
Агрегатные функции можно разумным образом использовать в списке выборки (при построении выражений, являющихся элементами выборки) и в логическом выражении раздела HAVING (вернее, в выражениях, входящих в простые условия). Рассмотрим разные случаи применения агрегатных функций в списке выборки в зависимости от вида табличного выражения.
Если результат табличного выражения R не является сгруппированной таблицей (т. е. в табличном выражении отсутствуют разделы GROUP BY и HAVING), то появление в списке выборки хотя бы одного вызова агрегатной функции от (мульти) множества строк R приводит к тому, что R неявно рассматривается как сгруппированная таблица, состоящая из одной (или нуля, если R пусто) групп с отсутствующими столбцами группирования. Поэтому в данном случае в выражениях списка выборки не допускается прямое использование имен столбцов R: все они должны находиться внутри спецификаций вызова агрегатных функций. Результатом запроса является таблица, состоящая не более чем из одной строки, значения столбцов которой получены путем применения агрегатных функций к R.
Аналогично обстоит дело в том случае, когда R представляет собой сгруппированную таблицу, но табличное выражение не содержит раздела GROUP BY (и, следовательно, содержит раздел HAVING). В этом случае считается, что результат табличного выражения явно объявлен сгруппированной таблицей, состоящей из одной группы, и результат запроса можно формировать только путем применения агрегатных функций к данной группе строк. Опять результатом запроса является таблица, состоящая не более чем из одной строки, значения столбцов которой получены путем применения агрегатных функций к R.
Наконец, рассмотрим случай, когда R представляет собой «настоящую» сгруппированную таблицу, т. е. табличное выражение содержит раздел GROUP BY, и, следовательно, определен по крайней мере один столбец группирования (т.
е. имеется хотя бы один такой столбец, что для любой группы его значения одинаковы во всех строках группы). В этом случае правила формирования списка выборки полностью соответствуют правилам формирования условия выборки раздела HAVING. Другими словами, в выражениях, являющихся элементами списка выборки, допускается прямое использование имен столбцов группирования, а спецификации остальных столбцов R могут появляться только внутри спецификаций агрегатных функций. Результатом запроса является таблица, число строк в которой равно числу групп в R. Значения столбцов каждой строки формируются на основе значений столбцов группирования и вызовов агрегатных функций для соответствующей группы.
Оба термина являются приемлемыми. Речь идет об агрегатных функциях, поскольку аргументом функции является агрегатное (составное) значение. Речь идет о функциях над множествами, поскольку аргументом функции является множество (в общем случае, мультимножество) значений. Но более правильно было бы говорить о групповых функциях, поскольку в большинстве случаев такие функции работают на значениях столбцов групп строк.
Поскольку, как отмечалось в Лекции 15, в SQL к булевскому значению uknown принято относиться точно так же, как и к неопределенному значению, в списке значений для вычисления этих функций не останутся значения uknown.
Обратите внимание на то, что это еще один вид различения строк в SQL и еще одна скрытая интерпретация неопределенного значения. COUNT(*) работает так, как если бы выполнялось соотношение (NULL=NULL)
Семантическая модель Entity-Relationship (Сущность-Связь)
В этой лекции мы кратко рассмотрим некоторые черты одной из наиболее популярных семантических моделей данных – модели «Сущность-Связь» (часто ее называют кратко ER-моделью от Entity-Relationship).
Здесь следует сделать два замечания, касающиеся, главным образом, терминологии. Оба термина relation и relationship могут быть переведены на русский язык как отношение. Поэтому в русскоязычной литературе ER-модель иногда называют моделью сущность-отношение, а иногда и реляционной семантической моделью. Наверное, в этом нет ничего страшного, если говорить о ER-модели в отрыве от тематики проектирования реляционных баз данных.
Но если требуется одновременно использовать термины ER-модели и реляционной модели данных, то, безусловно, требуется применять для терминов relation и relationship разные русские эквиваленты. За этими терминами стоят весьма различные понятия. В реляционной модели отношение (relation) – это единственная родовая структура данных. С помощью этого же механизма представляются «связанные» сущности (вспомните, например, про внешние ключи). Как мы увидим немного позже, в ER-модели для представления схемы базы данных используются два равноправных понятия – сущность и связь. Связи в ER-модели играют роль, отличную от той, какую играют отношения в реляционной модели данных.
Кроме того, в русскоязычную терминологию вошла и чистая транслитерация термина relation именно в смысле отношение. Мы говорим, например, про реляционную модель данных, реляционную алгебру и т. д., понимая модель данных, основанную на отношениях, алгебру отношений и т. п. По этому поводу, по крайней мере, в контексте баз данных, разумно окончательно зарезервировать термины relation и отношение для обозначения понятий реляционной модели данных, а для термина relationship использовать другой допустимый русскоязычный эквивалент – связь.
На использовании разных вариантов ER-модели основано большинство современных подходов к проектированию баз данных (главным образом, реляционных). Модель была предложена Питером Ченом (Peter Chen) в 1976 г. Моделирование предметной области базируется на использовании графических диаграмм, включающих небольшое число разнородных компонентов. Простота и наглядность представления концептуальных схем баз данных в ER-модели привели к ее широкому распространению в CASE-системах, поддерживающих автоматизированное проектирование реляционных баз данных. Среди множества разновидностей ER-моделей одна из наиболее популярных и развитых применялась в системе CASE компании Oracle. Мы обсудим некоторый упрощенный вариант этой модели. Если говорить более точно, сосредоточимся на ее структурной и целостной частях.
Семантические модели данных
Потребность проектировщиков баз данных в более удобных и мощных средствах моделирования предметной области вызвала к жизни направление семантических моделей данных. Хотя любая развитая семантическая модель данных, как и реляционная модель, включает структурную, манипуляционную и целостную части, главным назначением семантических моделей является обеспечение возможности выражения семантики данных.
Прежде чем мы коротко рассмотрим особенности двух распространенных семантических моделей, остановимся на возможных областях их применения. Чаще всего на практике семантическое моделирование используется на первой стадии проектирования базы данных. При этом в терминах семантической модели производится концептуальная схема базы данных, которая затем вручную преобразуется к реляционной (или какой-либо другой) схеме. Этот процесс выполняется под управлением методик, в которых достаточно четко оговорены все этапы такого преобразования. Основным достоинством данного подхода является отсутствие потребности в дополнительных программных средствах, поддерживающих семантическое моделирование. Требуется только знание основ выбранной семантической модели и правил преобразования концептуальной схемы в реляционную схему.
Следует заметить, что многие начинающие проектировщики баз данных недооценивают важность семантического моделирования вручную. Зачастую это воспринимается как дополнительная и излишняя работа. Эта точка зрения абсолютно неверна. Во-первых, построение мощной и наглядной концептуальной схемы БД позволяет более полно оценить специфику моделируемой предметной области и избежать возможных ошибок на стадии проектирования схемы реляционной БД. Во-вторых, на этапе семантического моделирования производится важная документация (хотя бы в виде вручную нарисованных диаграмм и комментариев к ним), которая может оказаться очень полезной не только при проектировании схемы реляционной БД, но и при эксплуатации, сопровождении и развитии уже заполненной БД.
Неоднократно приходилось и приходится наблюдать ситуации, в которых отсутствие такого рода документации существенно затрудняет внесение даже небольших изменений в схему существующей реляционной БД.
Конечно, это относится к случаям, когда проектируемая БД содержит не слишком малое число таблиц. Скорее всего, без семантического моделирования можно обойтись, если число таблиц не превышает десяти, но оно совершенно необходимо, если БД включает более сотни таблиц. Для справедливости заметим, что процедура создания концептуальной схемы вручную с ее последующим преобразованием в реляционную схему БД затруднительна в случае больших БД (содержащих несколько сотен таблиц). Причины, по всей видимости, не требуют пояснений.
История систем автоматизации проектирования баз данных (CASE-средств) началась с автоматизации процесса рисования диаграмм, проверки их формальной корректности, обеспечения средств долговременного хранения диаграмм и другой проектной документации. Конечно, компьютерная поддержка работы с диаграммами для проектировщика БД очень полезна. Наличие электронного архива проектной документации помогает при эксплуатации, администрировании и сопровождении базы данных. Но система, которая ограничивается поддержкой рисования диаграмм, проверкой их корректности и хранением, напоминает текстовый редактор, поддерживающий ввод, редактирование и проверку синтаксической корректности конструкций некоторого языка программирования, но существующий отдельно от компилятора. Кажется естественным желание расширить такой редактор функциями компилятора, и это действительно возможно, поскольку известна техника компиляции конструкций языка программирования в коды целевого компьютера. Но коль скоро имеется четкая методика преобразования концептуальной схемы БД в реляционную схему, то почему бы не выполнить программную реализацию соответствующего «компилятора» и не включить ее в состав системы проектирования баз данных?
Эта идея, естественно, показалась разумной производителям CASE-средств проектирования БД. Подавляющее большинство подобных систем, представленных на рынке, обеспечивает автоматизированное преобразование диаграммных концептуальных схем баз данных, представленных в той или иной семантической модели данных, в реляционные схемы, специфицированные чаще всего на языке SQL.
У читателя может возникнуть вопрос, почему в предыдущем предложении говорится про «автоматизированное», а не про «автоматическое» преобразование? Все дело в том, что в типичной схеме SQL-ориентированной БД могут содержаться определения многих объектов (ограничений целостности общего вида, триггеров и хранимых процедур и т. д.), которые невозможно сгенерировать автоматически на основе концептуальной схемы. Поэтому на завершающем этапе проектирования реляционной схемы снова требуется ручная работа проектировщика.
Еще раз обратите внимание на то, какой ход рассуждений привел нас к выводу о возможности автоматизации процесса преобразования концептуальной схемы БД в реляционную схему. Если создатели семантической модели данных предоставляют методику преобразования концептуальных схем в реляционные, то почему бы не реализовать программу, которая производит те же преобразования, следуя той же методике? Зададимся теперь другим, но, по существу, схожим вопросом. Если создатели семантической модели данных предоставляют язык (например, диаграммный), используя который проектировщики БД на основе исходной информации о предметной области могут сформировать концептуальную схему БД, то почему бы не реализовать программу, которая сама генерирует концептуальную схему БД в соответствующей семантической модели, используя исходную информацию о предметной области? Хотя нам не известны коммерческие CASE-средства проектирования БД, поддерживающие такой подход, экспериментальные системы успешно существовали. Они представляли собой интегрированные системы проектирования с автоматизированным созданием концептуальной схемы на основе интервью с экспертами предметной области и последующим преобразованием концептуальной схемы в реляционную.
Как правило, CASE-средства, автоматизирующие преобразование концептуальной схемы БД в реляционную, производят реляционную схему базы данных в третьей нормальной форме. Нормализация более высокого уровня усложняет программную реализацию и редко требуется на практике.
Наконец, третья возможность, которую следует упомянуть, хотя она еще не вышла (или только выходит, а может быть, так никогда и не выйдет) за пределы исследовательских и экспериментальных проектов, – это работа с базой данных в семантической модели, т. е. СУБД, основанные на семантических моделях данных. При этом снова рассматриваются два варианта: обеспечение пользовательского интерфейса на основе семантической модели данных с автоматическим отображением конструкций этого интерфейса в реляционную модель данных (это задача примерно того же уровня сложности, что и автоматическая компиляция концептуальной схемы базы данных в реляционную схему) и прямая реализация СУБД, основанная на какой-либо семантической модели данных. Многие авторитетные специалисты полагают, что ближе всего ко второму подходу объектно-ориентированные СУБД, чьи модели данных по многим параметрам близки к семантическим моделям (хотя в некоторых аспектах они более мощны, а в некоторых – более слабы).
Начиная с этой лекции, мы переходим к использованию терминов таблица, строка и столбец вместо строгих реляционных терминов отношение, атрибут и таблица, поскольку здесь под «реляционными» базами данных понимаются, главным образом, SQL-ориентированные базы данных, для которых эта упрощенная терминология более естественна.
Многие сторонники реляционного подхода считают отсутствие раздельного представления сущностей и связей преимуществом реляционной модели данных, мотивируя это тем, что зачастую то, что вчера считалось сущностью, сегодня разумнее принять за связь, и наоборот. Это, безусловно, верно с точки зрения поддержки и модификации существующих реляционных баз данных, но отнюдь не так с точки зрения проектирования базы данных.
Позволю себе одно терминологическое замечание, которое может показаться несколько наивным для специалистов в области инженерии программного обеспечения (software engineering), к числу которых я не принадлежу. Издавна существует отдельный класс программных систем, предназначенных для автоматизации проектирования новых продуктов в разных областях промышленности – автомобилестроении, аэрокосмической промыш- ленности, электронной промышленности и т.д.
Очевидно, что процесс проектирования автомобиля принципиально отличается от процесса проектирования микропроцессора, но, тем не менее, для обозначения любой Системы Автоматизации ПРоектирования используется собирательный термин САПР (CAD – Computer Aided Design). Это оправдывается тем, что разные подклассы САПР имеют гораздо больше общих черт, чем различий. Так вот, по моему мнению, система автоматизации проектирования БД по своему назначению и строению в большей степени является системой класса САПР, чем системой класса CASE (Computer Aided Software Engineering). По всей видимости, средства автоматизированной поддержки проектирования баз данных стали в свое время называть CASE-средствами, поскольку они обычно включали не только инструменты для поддержки проектирования, но и инструменты, поддерживающие проектирование и разработку приложений баз данных. В последние годы такие инструменты все реже производятся в виде одного пакета, и сам термин «CASE-средство» почти вышел из употребления. Тем не менее, поскольку не появилось какое-либо другое собирательное название средств поддержки проектирвания баз данных, мы будем продолжать использовать именно этот термин.
Семантика агрегатных функций
Агрегатные функции (в стандарте SQL они называются функциями над множествами) определяются следующими синтаксическими правилами:
<set_function_specification> ::= COUNT(*) | set_function_type ([DISTINCT | ALL ] value_expression) | GROUPING (column_reference) <set_function_type> ::= { AVG | MAX | MIN | SUM | EVERY | ANY | SOME | COUNT }
Как видно из этих правил, в стандарте SQL:1999 определены пять стандартных агрегатных функций: COUNT – число строк или значений, MAX – максимальное значение, MIN – минимальное значение, SUM – суммарное значение и AVG – среднее значение, а также две «кванторные» функции EVERY и SOME (ANY). В последних двух случаях выражение должно иметь булевский тип. Обсуждение функции GROUPING мы отложим до следующей лекции.
Агрегатные функции предназначены для того, чтобы вычислять некоторое значение для заданного мультимножества строк. Таким мультимножеством строк может быть группа строк, если агрегатная функция применяется к сгруппированной таблице, или (в вырожденных случаях) вся таблица. Для всех агрегатных функций, кроме COUNT(*), фактический (т. е. требуемый семантикой) порядок вычислений состоит в следующем. На основании параметров агрегатной функции из заданного мультимножества строк производится список значений. Затем по этому списку значений производится вычисление функции. Если список оказался пустым, то значением функции COUNT для него является 0, значением функции SOME – false, значением функции ALL – true, а значением всех остальных функций – NULL.
Пусть T обозначает тип значений из этого списка (вернее, «наименьший общий» тип, см. раздел лекции 17). Типы значений агрегатных функций определяются следующими правилами. Результат вычисления функции COUNT – это точное число с точностью и шкалой, которые определяются в реализации.Тип результата значений функций MAX и MIN совпадает с T. При вычислении функций SUM и AVG тип T не должен быть типом символьных строк. Если T представляет собой тип точных чисел, то и типом результата функции является тип точных чисел с определяемыми в реализации точностью и шкалой.Если T представляет собой тип приблизительных чисел, то и типом результата функции является тип приблизительных чисел с определяемой в реализации точностью.Для функций EVERY и SOME T является булевским типом. Первая функция принимает значение true в том и только в том случае, когда вычисление выражения-аргумента дает значение true для каждой строки из заданного набора строк, и false, когда значение выражения-аргумента есть false хотя бы для одной строки из заданного набора строк.Функция SOME принимает значение false в том и только в том случае, когда значение выражения-аргумента есть false для каждой строки из заданного набора строк, и true, когда значение выражения-аргумента есть true хотя бы для одной строки из заданного набора строк.
Вычисление функции COUNT(*) производится путем подсчета числа строк в заданном мультимножестве. Все строки считаются различными, даже если они состоят из одного столбца со значением null во всех строках.
Если «арифметическая» (AVG, MAX, MIN, SUM, COUNT) агрегатная функция специфицирована с ключевым словом DISTINCT, то множество значений, на котором она вычисляется, строится из значений указанного выражения, вычисляемого для каждой строки заданной группы строк. Затем из этого мультимножества удаляются неопределенные значения, и в нем устраняются значения-дубликаты (т. е. образуется множество). После этого вычисляется указанная функция.
Если агрегатная функция специфицирована без ключевого слова DISTINCT (или с ключевым словом ALL), то мультимножество значений формируется из значений выражения, вычисляемого для каждой строки заданной группы строк. Затем из этого мультимножества удаляются неопределенные значения, и производится вычисление агрегатной функции.
Семантика оператора выборки
Для начала опишем общую схему выполнения оператора SELECT в соответствии с предписаниями стандарта. Выполнение запроса состоит из нескольких шагов, соответствующих разделам оператора выборки. На первом шаге выполняется раздел FROM. Если список ссылок на таблицы (table_reference_commalist) этого раздела соответствует таблицам A, B, … C, то в результате выполнения раздела FROM образуется таблица (назовем ее T), являющаяся расширенным декартовым произведением таблиц A, B, …, C. Если в разделе FROM указана только одна таблица, то она же и является результатом выполнения этого раздела. Как говорилось в лекции 4, в реляционной алгебре для корректного выполнения операции взятия расширенного декартова произведения отношений в общем случае требуется применение операции переименования атрибутов. Соответствующие возможности переименования столбцов таблиц, указанных в списке раздела FROM, поддерживаются и в SQL. Альтернативный способ именования столбцов результирующей таблицы T основывается на использовании квалифицированных имен столбцов. Идея этого подхода (более раннего в истории SQL) заключается в том, что с любой таблицей, ссылка на которую содержится в списке раздела FROM, можно связать некоторое имя-псевдоним (в стандарте оно называется correlation name). Тогда если с такой таблицей A связан псевдоним Z, то в пределах оператора выборки можно ссылаться на любой столбец a таблицы A по квалифицированному имени Z.a. Мы обсудим это подробнее в следующем подразделе. Пока же будем считать, что имена всех столбцов таблицы T определены и различны.
На втором шаге выполняется раздел WHERE. Условное выражение (conditional_expression) этого раздела применяется к каждой строке таблицы T, и результатом является таблица T1, содержащая те и только те строки таблицы T, для которых результатом вычисления условного выражения является true. (Заголовки таблиц T и T1 совпадают.) Если раздел WHERE в операторе выборки отсутствует, то это трактуется как наличие раздела WHERE true, т. е. T1 содержит те и только те строки, которые содержатся в таблице T.
Обратите внимание на разницу в трактовке логических выражений в операторах выборки и в табличных ограничениях целостности. Логическое выражение раздела WHERE (и раздела HAVING) оператора выборки разрешает выборку строки в том и только в том случае, когда результатом вычисления логического выражения на данной строке является true (значения false и uknown не являются разрешающими). Логическое выражение табличного ограничения целостности запрещает наличие строки в таблице в том и только в том случае, когда результатом вычисления логического выражения на данной строке является false (значения true и uknown не являются запрещающими).
Если в операторе выборки присутствует раздел GROUP BY, то он выполняется на третьем шаге. Каждый элемент списка имен столбцов (column_name_commalist), указываемого в этом разделе, должен быть одним из имен столбцов таблицы T1. В результате выполнения раздела GROUP BY образуется сгруппированная таблица T2, в которой строки таблицы T1 расставлены в минимальное число групп, таких, что во всех строках одной группы значения столбцов, указанных в списке имен столбцов раздела GROUP BY (столбцов группировки), одинаковы. Заметим, что сгруппированные таблицы не могут являться окончательным результатом оператора выборки. Они существуют только на концептуальном уровне на стадии выполнения запроса, содержащего раздел GROUP BY.
Если в операторе выборки присутствует раздел HAVING, то он выполняется на следующем шаге. Условное выражение этого раздела применяется к каждой группе строк таблицы T2, и результатом является сгруппированная таблица T3, содержащая те и только те группы строк таблицы T2, для которых результатом вычисления условного выражения является true. Условное выражение раздела HAVING строится по синтаксическим правилам, общим для всех условных выражений, но обладает той спецификой, что применяется к группам строк, а не к отдельным строкам. Поэтому предикаты, из которых строится это условное выражение, должны быть предикатами на группу в целом.
В них могут использоваться имена столбцов группировки (инварианты группы) и так называемые агрегатные функции (COUNT, SUM, MIN, MAX, AVG) от других столбцов. Мы обсудим агрегатные функции более подробно в лекции 19.
При наличии в запросе раздела HAVING, которому не предшествует раздел GROUP BY, таблица T1 рассматривается как сгруппированная таблица, состоящая из одной группы строк, без столбцов группирования. В этом случае логическое выражение раздела HAVING может состоять только из предикатов с агрегатными функциями, а результат вычисления этого раздела T3 либо совпадает с таблицей T1, либо является пустым.
Если в операторе выборки присутствует раздел GROUP BY, но отсутствует раздел HAVING, то это трактуется как наличие раздела HAVING true, т. е. T3 содержит те и только те группы строк, которые содержатся в таблице T2.
После выполнения раздела WHERE (если в запросе отсутствуют разделы GROUP BY и HAVING, случай (a)) или явно или неявно заданного раздела HAVING (случай (b)) выполняется раздел SELECT. При выполнении этого раздела на основе таблицы T1 в случае (a) или на основе сгруппированной таблицы T3 в случае (b) строится таблица T4, содержащая столько строк, сколько строк или групп строк содержится в таблицах T1 или T3 соответственно. Число столбцов в таблице T4 зависит от числа элементов в списке элементов выборки (select_item_commalist) и от вида элементов.
Рассмотрим, каким образом формируются значения столбцов в таблице T4. Элемент списка выборки может задаваться одним из двух способов:
select_item ::= value_expression [ [ AS ] column_name ] | [ correlation_name . ] *
Сначала обсудим первый вариант. В этом случае каждый элемент списка элементов выборки соответствует столбцу таблицы T4. Столбцу может быть явным образом приписано имя (когда и зачем могут использоваться имена таблицы T4, мы обсудим позже). Порядок формирования значения этого столбца для выделенных выше случаев (a) и (b) различается, и мы рассмотрим подобные случаи по отдельности.
В случае (a) выражение, содержащееся в элементе выборки, может содержать литеральные константы и вызовы функций со значениями соответствующих типов (в том числе ниладические).
Кроме того, в выражении могут использоваться имена столбцов таблицы T1. Выражение вычисляется для каждой строки таблицы T1, и именам столбцов соответствуют значения этих столбцов в данной строке таблицы T1.
В случае (b), как и в случае (a), выражение, содержащееся в элементе выборки, может содержать литеральные константы и вызовы функций. Но, в отличие от случая (a), в выражение могут входить непосредственно имена только тех столбцов таблицы T3, которые входили в список столбцов группировки раздела GROUP BY оператора выборки. (Если сгруппированная таблица T3 была образована за счет наличия раздела HAVING без присутствия раздела GROUP BY, то в выражении элемента выборки вообще нельзя непосредственно использовать имена столбцов таблицы T3). Имена других столбцов таблицы T3 могут использоваться только в конструкциях вызова агрегатных функций COUNT, SUM, MIN, MAX, AVG. Выражение вычисляется для каждой группы строк таблицы T3. Именам столбцов, входящих в выражение непосредственно, сопоставляются значения этих столбцов, которые соответствуют данной группе зстрок таблицы T3.
Во втором варианте спецификация элемента списка выборки вида [ Z. ]* является сокращенной формой записи списка Z.a1, Z.a2, …, Z.an, где a1, a2, …, an представляет собой полный список имен столбцов таблицы, псевдоним которой Z. Следует сделать три замечания. Во-первых, для именованной таблицы, входящей в список раздела FROM только один раз, можно использовать имя таблицы вместо псевдонима. Во-вторых, во втором варианте спецификации элемента списка выборки можно опустить псевдоним только в том случае, если в разделе FROM указана только одна таблица. В-третьих, в случае (b) второй вариант спецификации элемента выборки допустим только тогда, когда все столбцы таблицы с псевдонимом Z входят в список столбцов группировки раздела GROUP BY.
Итак, мы получили таблицу T4. Если в спецификации раздела SELECT отсутствует ключевое слово DISTINCT, или присутствует ключевое слово ALL, либо отсутствуют и ALL, и DISTINCT, то T4 является результатом выполнения раздела SELECT.
В противном случае на завершающей стадии выполнения раздела SELECT в таблице T4 удаляются строки-дубликаты.
Если в операторе выборки не содержится раздел ORDER BY, то таблица T4 является результирующей таблицей запроса. Иначе на завершающей стадии выполнения запроса производится сортировка строк таблицы T4 в соответствии со списком элементов сортировки (order_item_commalist) раздела ORDER BY. В стандарте SQL:1999 элемент списка элементов сортировки имеет следующую синтаксическую форму:
order_item ::= value_expression [ collate_clause ] [ { ASC | DESC } ]
Выполнение раздела ORDER BY производится следующим образом. Выбирается первый элемент списка сортировки, и строки таблицы T4 расставляются в порядке возрастания (если в элементе присутствует спецификация ASC; при отсутствии спецификации ASC/DESC предполагается наличие ASC) или в порядке убывания (при наличии спецификации DESC) в соответствии со значениями выражения, содержащегося в данном элементе, которые вычисляются для каждой строки таблицы T4. Далее выбирается второй элемент списка сортировки, и в соответствии со значениями заданного в нем выражения и порядка сортировки расставляются строки, которые после первого шага сортировки образовали группы с одинаковым значением выражения первого элемента списка сортировки. Операция продолжается до исчерпания списка элементов сортировки. Результирующий отсортированный список строк является окончательным результатом запроса.
В общем случае выражение, входящее в элемент списка сортировки, основывается на именах столбцов таблицы T4 и именах столбцов таблицы, над которой вычислялся раздел SELECT (T1 или T3). Идея состоит в том, что если некоторое выражение могло бы быть использовано в элементе списка выборки, то его можно использовать в элементе списка сортировки. В стандарте SQL:1999 присутствует ряд чисто технических ограничений на вид выражений, допустимых в элементах списка сортировки, если в запросе присутствуют разделы GROUP BY и/или HAVING и если в разделе SELECT присутствует спецификация DISTINCT.
Но в любом случае это выражение может иметь вид a, где a – имя столбца таблицы T4.
Заметим, что в предыдущих версиях стандарта языка SQL, включая SQL/92, элемент списка сортировки определялся следующим синтаксическим правилом:
order_item ::= { column_name | unsigned_integer } [ { ASC | DESC } ]
В качестве имени столбца (column_name) можно было использовать любое имя, вводимое для столбца таблицы T4 в элементе списка выборки. Вместо имени столбца можно было использовать его порядковый номер (unsigned_integer) в списке элементов выборки раздела SELECT. Как мы видели, в новом стандарте вторая возможность исключена. Доводом является не тот факт, что использование номеров столбцов противоречит реляционной модели. Использование номеров столбцов запрещено, поскольку не давало возможности применять в элементах списка сортировки выражения. Тем не менее, по нашему мнению, возможность использования номеров столбцов в течение долгого времени будет продолжать поддерживаться в коммерческих реализациях SQL, поскольку она применяется во многих существующих приложениях.
Сериализация транзакций
Чтобы добиться изолированности транзакций, в СУБД должны использоваться какие-либо методы регулирования совместного выполнения транзакций.
Пусть в системе одновременно выполняется некоторое множество транзакций S = {T1, T2, …, Tn}. План (способ) выполнения набора транзакций S
(в котором, вообще говоря, чередуются или реально параллельно выполняются операции разных транзакций) называется сериальным, если результат совместного выполнения транзакций эквивалентен результату некоторого последовательного выполнения этих же транзакций (Ti1, Ti2, …, Tin).
Сериализация транзакций – это механизм их выполнения по некоторому сериальному плану. Обеспечение такого механизма является основной функцией компонента СУБД, ответственного за управление транзакциями. Система, в которой поддерживается сериализация транзакций, обеспечивает реальную изолированность пользователей.
Основная реализационная проблема состоит в выборе метода сериализации набора транзакций, который не слишком ограничивал бы чередование их операций или реальную параллельность. Приходящим на ум тривиальным решением является действительно последовательное выполнение транзакций. Но существуют ситуации, в которых можно выполнять операторы разных транзакций в любом порядке с сохранением свойства сериальности. Примерами могут служить только читающие транзакции, а также транзакции, не конфликтующие по объектам базы данных.
Между транзакциями T1
и T2
могут существовать следующие виды конфликтов:
W/W – транзакция T2
пытается изменять объект, измененный не закончившейся транзакцией T1
(наличие такого конфликта может привести к возникновению ситуации потерянных изменений);
R/W – транзакция T2
пытается изменять объект, прочитанный не закончившейся транзакцией T1
(наличие такого конфликта может привести к возникновению ситуации неповторяющихся чтений);
W/R – транзакция T2
пытается читать объект, измененный не закончившейся транзакцией T1
(наличие такого конфликта может привести к возникновению ситуации «грязного» чтения).
Практические методы сериализации транзакций основываются на учете этих конфликтов.
Сетевая модель данных
Типичным представителем систем, основанных на сетевой модели данных, является СУБД IDMS (Integrated Database Management System), разработанная компанией Cullinet Software, Inc. и изначально ориентированная на использования на мейнфреймах компании IBM. Архитектура системы основана на предложениях Data Base Task Group (DBTG) организации CODASYL (COnference on DAta SYstems Languages), которая отвечала за определение языка программирования COBOL. Отчет DBTG был опубликован в 1971 г., и вскоре после этого появилось несколько систем, поддерживающих архитектуру CODASYL, среди которых присутствовала и СУБД IDMS. В настоящее время IDMS принадлежит компании Computer Associates.
Сетевые структуры данных
Сетевой подход к организации данных является расширением иерархического подхода. В иерархических структурах запись-потомок должна иметь в точности одного предка; в сетевой структуре данных у потомка может иметься любое число предков.
Сетевая БД состоит из набора записей и набора связей между этими записями, а если говорить более точно, из набора экземпляров каждого типа из заданного в схеме БД набора типов записи и набора экземпляров каждого типа из заданного набора типов связи.
Тип связи определяется для двух типов записи: предка и потомка. Экземпляр типа связи состоит из одного экземпляра типа записи предка и упорядоченного набора экземпляров типа записи потомка. Для данного типа связи L
с типом записи предка P
и типом записи потомка C
должны выполняться следующие два условия:
каждый экземпляр типа записи P
является предком только в одном экземпляре типа связи L;
каждый экземпляр типа записи C
является потомком не более чем в одном экземпляре типа связи L.
На формирование типов связи не накладываются особые ограничения; возможны, например, следующие ситуации:
тип записи потомка в одном типе связи L1
может быть типом записи предка в другом типе связи L2
(как в иерархии); данный тип записи P
может быть типом записи предка в любом числе типов связи; данный тип записи P
может быть типом записи потомка в любом числе типов связи; может существовать любое число типов связи с одним и тем же типом записи предка и одним и тем же типом записи потомка; и если L1
и L2
- два типа связи с одним и тем же типом записи предка P
и одним и тем же типом записи потомка C, то правила, по которым образуется родство, в разных связях могут различаться;
типы записи X
и Y
могут быть предком и потомком в одной связи и потомком и предком – в другой;
предок и потомок могут быть одного типа записи.
На рис. 2.3 показан простой пример схемы сетевой БД. На этом рисунке показаны три типа записи: Отдел, Служащие
и Руководитель и три типа связи: Состоит из служащих, Имеет руководителя и Является служащим. В типе связи Состоит из служащих типом записи-предком является Отдел, а типом записи-потомком – Служащие
(экземпляр этого типа связи связывает экземпляр типа записи Отдел
со многими экземплярами типа записи Служащие, соответствующими всем служащим данного отдела). В типе связи Имеет руководителя типом записи-предком является Отдел, а типом записи-потомком – Руководитель
(экземпляр этого типа связи связывает экземпляр типа записи Отдел
с одним экземпляром типа записи Руководитель, соответствующим руководителю данного отдела). Наконец, в типе связи Является служащим типом записи-предком является Руководитель, а типом записи-потомком – Служащие
(экземпляр этого типа связи связывает экземпляр типа записи Руководитель с одним экземпляром типа записи Служащие, соответствующим тому служащему, которым является данный руководитель).
Рис. 2.3. Пример схемы сетевой базы данных
Схема восстановления от точки физической согласованности
Будем считать, что в журнале отмечаются точки физической согласованности базы данных – моменты времени, в которые во внешней памяти содержатся согласованные результаты операций, завершившихся до соответствующего момента времени, и отсутствуют результаты операций, которые не завершились, а буфер журнала вытолкнут во внешнюю память. Немного позже мы обсудим, как можно достичь физической согласованности. Назовем такие точки ppc (point of physical consistency).
Все возможные состояния транзакций к моменту мягкого сбоя показаны на рис. 14.1.
Рис. 14.1. Возможные состояния транзакций к моменту мягкого сбоя
Предположим, что каким-то образом удалось восстановить внешнюю память базы данных к состоянию на момент времени tppc (как это можно сделать, обсудим в следующем подразделе). Тогда восстановление последнего по времени логически целостного состояния базы данных производится следующим образом.
Для транзакции T1
никаких действий производить не требуется. Она закончилась до момента tppc, и все ее результаты гарантированно отражены во внешней памяти базы данных.
Для транзакции T2
нужно повторно выполнить (redo) последовательность операций, которые выполнялись после установки точки физически согласованного состояния в момент tppc. Действительно, во внешней памяти полностью отсутствуют следы операций, которые выполнялись в транзакции T2
после момента tppc. Следовательно, повторное прямое (по смыслу и хронологии) выполнение операций транзакции T2
корректно и приведет к логически согласованному состоянию базы данных. (Поскольку транзакция T2
успешно завершилась до момента мягкого сбоя tfs, в журнале содержатся записи обо всех изменениях базы данных, произведенных этой транзакцией.)
Для транзакции T3
нужно выполнить в обратном направлении (undo) ту часть операций, которую она успела выполнить до момента tppc. Действительно, во внешней памяти базы данных полностью отсутствуют результаты операций T3, которые были выполнены после момента tppc. С другой стороны, во внешней памяти гарантированно присутствуют результаты операций T3, которые были выполнены до момента tppc.
Следовательно, обратное выполнение (по смыслу и хронологии) операций T3
корректно и приведет к согласованному состоянию базы данных. (Поскольку транзакция T3
не завершилась к моменту мягкого сбоя tfs, при восстановлении необходимо устранить все последствия ее выполнения.)
Для транзакции T4, которая успела начаться после момента tppc
и закончиться до момента мягкого сбоя tfs, нужно произвести полное повторное выполнение операций в прямом направлении. (Поскольку транзакция T4
успешно завершилась до момента мягкого сбоя tfs, в журнале содержатся записи обо всех изменениях базы данных, произведенных этой транзакцией).
Наконец, для транзакции T5, начавшейся после момента tppc
и не успевшей завершиться к моменту мягкого сбоя tfs, никаких действий предпринимать не требуется. Результаты операций этой транзакции полностью отсутствуют во внешней памяти базы данных.
Синхронизация многопользовательского доступа
Последнее, на чем мы остановимся в связи с файлами, – это способы применения файлов в многопользовательской среде. Если операционная система поддерживает многопользовательский режим, может возникнуть ситуация, когда два или более пользователей одновременно пытаются работать с одним и тем же файлом. Если все эти пользователи собираются только читать файл, ничего страшного не произойдет. Но если хотя бы один из них будет изменять файл, для корректной работы этой группы требуется взаимная синхронизация.
В файловых системах обычно применялся следующий подход. В операции открытия файла (первой и обязательной операции, с которой должен начинаться сеанс работы с файлом) помимо прочих параметров указывался режим работы (чтение или изменение). Если к моменту выполнения этой операции от имени некоторого процесса A файл уже был открыт некоторым другим процессом B, причем существующий режим открытия был несовместим с требуемым режимом (совместимы только режимы чтения), то в зависимости от особенностей системы либо процессу A сообщалось о невозможности открытия файла в нужном режиме, либо процесс A блокировался до тех пор, пока процесс B не выполнит операцию закрытия файла.
Синхронизационные блокировки
Наиболее распространенным в централизованных СУБД (включающих системы, основанные на архитектуре «клиент-сервер») является подход, основанный на соблюдении двухфазного протокола синхронизационных захватов объектов баз данных (Two-Phase Locking Protocol, 2PL). В общих чертах подход состоит в том, что перед выполнением любой операции в транзакции T
над объектом базы данных o
от имени транзакции T запрашивается синхронизационная блокировка объекта o
в соответствующем режиме (в зависимости от вида операции).
Основными режимами синхронизационных блокировок являются следующие:
совместный режим – S (Shared), означающий совместную (по чтению) блокировку объекта и требуемый для выполнения операции чтения объекта;
монопольный режим – X (eXclusive), означающий монопольную (по записи) блокировку объекта и требуемый для выполнения операций вставки, удаления и модификации объекта.
Блокировки одних и тех же объектов по чтению несколькими транзакциями совместимы, т.е. нескольким транзакциям допускается одновременно читать один и тот же объект. Блокировка объекта одной транзакцией по чтению не совместима с блокировкой другой транзакцией того же объекта по записи, т.е. никакой транзакции нельзя изменять объект, читаемый некоторой транзакцией (кроме самой этой транзакции), и никакой транзакции нельзя читать объект, изменяемый некоторой транзакцией (кроме самой этой транзакции). Блокировки одного и того же объекта по записи разными транзакциями не совместимы, т.е. никакой транзакции нельзя изменять объект, изменяемый некоторой транзакцией (кроме самой этой транзакции). Правила совместимости захватов одного объекта разными транзакциями приведены в таблице 10.1.
В первом столбце приведены возможные состояния объекта с точки зрения синхронизационных захватов. При этом "-" соответствует состоянию объекта, для которого не установлен никакой захват. Транзакция, запросившая синхронизационный захват объекта БД, уже захваченный другой транзакцией в несовместимом режиме, блокируется до тех пор, пока захват с этого объекта не будет снят.
Таблица 9.1. Совместимость блокировок S и X
| X | S | |
| - | да | да |
| X | нет | нет |
| S | нет | да |
Для обеспечения сериализации транзакций (третьего уровня изолированности) синхронизационные блокировки объектов, произведенные по инициативе транзакции, можно снимать только при ее завершении (см. примеры сценариев, обсуждавшихся в разделе ). Это требование порождает двухфазный протокол синхронизационных захватов – 2PL. В соответствии с этим протоколом выполнение транзакции разбивается на две фазы:
первая фаза транзакции (выполнение операций над базой данных) – накопление блокировок;
вторая фаза (фиксация или откат) – снятие блокировок.
Достаточно легко убедиться, что при соблюдении двухфазного протокола синхронизационных блокировок действительно обеспечивается сериализация транзакций на третьем уровне изолированности. Также легко видеть, что для обеспечения отсутствия потерянных данных достаточно блокировать в режиме X изменяемые объекты базы данных и удерживать эти блокировки до конца транзакции, а для обеспечения отсутствия чтения «грязных» данных достаточно блокировать в режиме X изменяемые объекты до конца транзакции и блокировать в режиме S читаемые объекты на время выполнения операции чтения.
Основная проблема состоит в том, что следует считать объектом для синхронизационного захвата? В контексте реляционных баз данных возможны следующие альтернативы:
файл (сегмент в терминах System R) – физический (с точки зрения базы данных) объект, область хранения нескольких таблиц и, возможно, индексов;
таблица – логический объект, соответствующий множеству кортежей данной таблицы;
страница данных – физический объект, хранящий кортежи одной или нескольких таблиц, индексную или служебную информацию;
кортеж – элементарный физический объект базы данных.
На самом деле, любая операция над объектом базы данных фактически воздействует и на объемлющие его объекты. Например, операция над кортежем является и операцией над страницей, в которой этот кортеж хранится, и над соответствующей таблицей, и над файлом, содержащим таблицу. Поэтому действительно имеется выбор уровня объекта блокировки.
Понятно, что для поддержки блокировок требуются системные ресурсы, и что чем крупнее объект синхронизационного захвата (неважно, какой природы этот объект – логический или физический), тем меньше синхронизационных блокировок будет поддерживаться в системе, и на это, соответственно, будут тратиться меньшие накладные расходы. Более того, если устанавливать блокировки на уровне файлов или таблиц, то будет решена даже проблема фантомов (если это не ясно сразу, посмотрите еще раз описание проблемы фантомов и определение двухфазного протокола захватов).
Но вся беда в том, что при использовании для блокировок крупных объектов возрастает вероятность конфликтов транзакций и, тем самым, уменьшается допускаемая степень чередования их операций или реального параллельного выполнения. Фактически, при укрупнении объекта синхронизационной блокировки мы умышленно огрубляем ситуацию и видим конфликты в тех ситуациях, в которых на самом деле конфликтов нет.
Разработчики многих систем начинали с использования страничных блокировок, полагая это некоторым компромиссом между стремлениями сократить накладные расходы и сохранить достаточно высокий уровень параллельности транзакций. Но это не очень хороший выбор. Не будем останавливаться на деталях, но заметим, что использование страничных блокировок в двухфазном протоколе иногда вызывает очень неприятные синхронизационные проблемы, усложняющие организацию СУБД (коротко говоря, эти проблемы связаны с тем, что страницы приходится блокировать на двух разных уровнях – уровне управления буферами страниц в основной памяти и уровне выполнения логических операций).В большинстве современных систем используются покортежные синхронизационные блокировки.
Но при этом возникает очередной вопрос. Если единицей блокировки является кортеж, то какие синхронизационные блокировки потребуются при выполнении таких операций как уничтожение заполненной таблицы? Было бы довольно нелепо перед выполнением такой операции потребовать блокировки всех существующих кортежей таблицы. Кроме того, это не предотвратило бы возможности параллельной вставки нового кортежа в уничтожаемое отношение в некоторой другой транзакции.
Синхронизационные тупики, их распознавание и разрушение
Одним из наиболее чувствительных недостатков метода сериализации транзакций на основе синхронизационных блокировок является возможность возникновение тупиков (deadlocks) между транзакциями. Синхронизационные тупики возможны при применении любого из рассмотренных выше вариантов механизмов блокировок.
На рис. 13.6 показан простой сценарий возникновения синхронизационного тупика между транзакциями T1
и T2:
Рис. 13.6. Ситуация синхронизационного тупика между транзакциями T1 и T2
транзакции T1
и T2
устанавливают монопольные блокировки объектов o1
и o2
соответственно;
после этого T1
требуется совместная блокировка объекта o2, а T2
– совместная блокировка объекта o1;
ни одно из этих требований блокировки не может быть удовлетворено, следовательно, ни одна из транзакций не может продолжаться; поэтому монопольные блокировки объектов никогда не будут сняты, а требования совместных блокировок не будут удовлетворены.
Поскольку тупики возможны, и никакого естественного выхода из тупиковой ситуации не существует, то эти ситуации необходимо обнаруживать и искусственно устранять.
Синтаксис определения триггеров и типы триггеров
Для более подробного обсуждения механизма триггеров в SQL:1999 необходимо ввести набор синтаксических правил:
trigger_definition ::= CREATE TRIGGER trigger_name { BEFORE | AFTER } { INSERT | DELETE | UPDATE [ OF column_commalist ] } ON table_name [ REFERENCING old_or_new_values_alias_list ] triggered_action triggered_action ::= [ FOR EACH { ROW | STATEMENT } ] [ WHEN left_paren conditional_expression right_paren ] triggered_SQL_statement triggered_SQL_statement ::= SQL_procedure_statement | BEGIN ATOMIC SQL_procedure_statement_semicolonlist END old_or_new_values_alias ::= OLD [ ROW ] [ AS ] correlation_name | NEW [ ROW ] [ AS ] correlation_name | OLD TABLE [ AS ] identifier | NEW TABLE [ AS ] identifier
Естественно, в языке имеется и конструкция, отменяющая определение триггера:
DROP TRIGGER trigger_name.
(Конструкция ALTER TRIGGER в языке SQL не поддерживается.)
Как мы видим, синтаксические правила допускают несколько разновидностей определения триггера. Кратко обсудим эти разновидности.
Скалярные выражения
Скалярное выражение – это выражение, вырабатывающее результат некоторого типа, специфицированного в стандарте. Скалярные выражения являются основой языка SQL, поскольку, хотя это реляционный язык, все условия, элементы списков выборки и т. д. базируются именно на скалярных выражениях. В SQL:1999 имеется несколько разновидностей скалярных выражений. К числу наиболее важных разновидностей относятся численные выражения; выражения со значениями-строками символов; выражения со значениями даты-времени; выражения со значениями-временными интервалами; булевские выражения. Мы не будем слишком глубоко вникать в тонкости, но тем не менее приведем некоторые базовые спецификации и пояснения.
Прежде чем перейти к конкретным видам скалярных выражений, рассмотрим некоторые наиболее общие языковые конструкции, на которых эти выражения базируются.
Случаи, в которых без порождаемых таблиц обойтись невозможно
На самом деле, демонстрирует лишь возможность альтернативных формулировок запросов с использованием ссылок на порождаемые таблицы в разделе FROM. Но в некоторых случаях без подобных конструкций просто невозможно обойтись. Вот простой пример.
Пример 19.15. Найти общее число служащих и максимальный размер зарплаты в отделах с одинаковым максимальным размером зарплаты.
SELECT SUM (TOTAL_EMP), MAX_SAL FROM (SELECT MAX (EMP_SAL), COUNT (*) FROM EMP WHERE DEPT_NO IS NOT NULL GROUP BY DEPT_NO ) AS DEPT_MAX_SAL (MAX_SAL, TOTAL_EMP) GROUP BY MAX_SAL;
И в этом случае выражение запросов, содержащееся в разделе FROM, можно перенести в раздел WITH (пример 19.15.1):
WITH DEPT_MAX_SAL (MAX_SAL, TOTAL_EMP) AS (SELECT MAX (EMP_SAL), COUNT (*) FROM EMP WHERE DEPT_NO IS NOT NULL GROUP BY DEPT_NO) SELECT SUM (TOTAL_EMP), MAX_SAL FROM DEPT_MAX_SAL GROUP BY MAX_SAL;
Здесь мы не можем обойтись «одноуровневой» конструкцией запроса, поскольку требуется двойная группировка, причем вторая группировка должна быть получена в соответствии с результатами первой. Еще один пример.
Пример 19.16. Найти число проектов, дату их завершения и средний размер зарплаты служащих, участвующих в проекте, для проектов с одной и той же датой завершения и одним и тем же средним размером зарплаты служащих, участвующих в проекте.
SELECT COUNT (*), PRO_EDATE, AVG_SAL FROM (SELECT PRO_EDATE, AVG (EMP_SAL) FROM (SELECT PRO_SDATE + PRO_DURAT, PRO_NO FROM PRO) AS PRO1 (PRO_EDATE, PRO_NO), EMP WHERE PRO1.PRO_NO = EMP.PRO_NO GROUP BY PRO1.PRO_NO ) AS PRO_AVG_SAL (PRO_EDATE, AVG_SAL) GROUP BY PRO_EDATE, AVG_SAL;
Заметим, что выражение запросов на третьей и четвертой строках примера необходимо только по той причине, что нам требуется группировка по дате окончания проектов, соответствующий столбец в таблице PRO отсутствует, а в списке группировки можно использовать только имена столбцов. Для упрощения вида формулировки это выражение разумно вынести в раздел WITH (пример 19.16.1):
WITH PRO1 (PRO_EDATE, PRO_NO) AS (SELECT PRO_SDATE + PRO_DURAT, PRO_NO FROM PRO) SELECT COUNT (*), PRO_EDATE, AVG_SAL FROM (SELECT PRO_EDATE, AVG (EMP_SAL) FROM PRO1, EMP WHERE PRO1.PRO_NO = EMP.PRO_NO GROUP BY PRO1.PRO_NO) AS PRO_AVG_SAL (PRO_EDATE, AVG_SAL) GROUP BY PRO_EDATE, AVG_SAL;
Служебная информация
Для корректной работы подсистемы управления данными во внешней памяти необходимо поддерживать информацию, которая используется только этой подсистемой и не видна подсистеме языкового уровня. Набор структур служебной информации зависит от общей организации системы, но обычно требуется поддержание следующих служебных данных:
Внутренние каталоги, описывающие физические свойства объектов базы данных, например, число атрибутов таблицы, их размер и, возможно, типы данных; описание индексов, определенных для данной таблицы и т.д.
Описатели свободной и занятой памяти в страницах данных. Такая информация требуется для нахождения свободного места при занесении кортежа. Отдельно приходится решать задачу поиска свободного места в случаях некластеризованных и кластеризованных таблиц (в последнем случае приходится дополнительно использовать кластеризованный индекс). Как уже отмечалось, нетривиальной является проблема освобождения страницы в условиях мультидоступа.
Связывание страниц одной таблицы. Если в одном файле внешней памяти могут располагаться страницы нескольких таблиц (обычно к этому стремятся), то нужно каким-то образом связать страницы одной таблицы. Тривиальный способ использования прямых ссылок между страницами часто приводит к затруднениями при синхронизации транзакций (например, особенно трудно освобождать и заводить новые страницы таблицы). Поэтому стараются использовать косвенное связывание страниц с использованием служебных индексов. В частности, известен общий механизм для описания свободной памяти и связывания страниц на основе B-деревьев.
Соединения общего вида
При наличии того факта, что операция взятия расширенного декартова произведения TIMES является частным случаем операции <AND>, после того как мы научились с помощью Алгебры A выполнять ограничения, становится очевидно, что через операции Алгебры A выражаются и соединения общего вида. В общем случае, чтобы получить результат соединения общего вида произвольных отношений A и B, нужно: выполнить над одним из отношений одну или несколько операций <RENAME>, чтобы избавиться от общих имен атрибутов;выполнить над полученными отношениями операцию <AND>, производящую расширенное декартово произведение;и для полученного отношения выполнить одну или несколько операций <AND> с отношениями-константами, чтобы должным образом ограничить его.
