- •Е.И. Асташева сетевые базы данных
- •Введение
- •1. Введение в базы данных
- •1.1. Что такое база данных
- •1.2. Структура базы данных
- •2. Иерархическая и сетевая модели организации данных
- •3. Реляционная модель базы данных
- •3.1. Домены и отношения
- •3.2. Целостность данных
- •3.3. Реляционная алгебра
- •3.4. Реляционное исчисление
- •4. Проектирование логической структуры базы данных
- •4.1. Концепция функциональной зависимости
- •4.2. Нормализация базы данных
- •4.3. Объектное моделирование
- •5. Функции защиты базы данных
- •5.1. Транзакции и параллелизм
- •5.2. Безопасность и целостность баз данных
- •6. Дополнительные аспекты реляционной технологии
- •6.1. Представления
- •6.2. Повышение производительности с помощью оптимизации
- •6.3. Домены, отношения и типы данных
- •6.4. Неопределенные значения и трехзначная логика
- •6.5. Распределенные базы данных
- •7. Технология физического хранения и доступа к данным
- •7.1. Основные этапы доступа к базе данных
- •7.2. Управление страницами
- •7.3. Процедура индексирования и хеширования
- •7.4. Сжатие данных
- •Заключение
- •Библиографический список
- •Оглавление
- •394026 Воронеж, Московский просп., 14
3.4. Реляционное исчисление
Допустим, что имеется БД, обладающая следующей структурой: отношение СТУДЕНТЫ (СТУД_НОМ, СТУД_ИМЯ, СТУД_СТИП, ГР_НОМ) и отношение ГРУППЫ (ГР_НОМ, ГР_КОЛ, ГР_СТАР). Предположим, что необходимо узнать имена и номера студенческих билетов у студентов, являющихся старостами групп с количеством студентов больше 25.
Если бы для формулировки такого запроса использовалась реляционная алгебра, то мы получили бы алгебраическое выражение, которое читалось бы. например, следующим образом:
- выполнить соединение отношений СТУДЕНТЫ и ГРУППЫ по условию СТУД_НОМ = ГР_СТАР;
- ограничить полученное отношение по условию ГР_КОЛ>25;
- спроецировать результат предыдущей операции на атрибут СТУД_ИМЯ и СТУД_НОМ.
Здесь пошагово сформулирована последовательность выполнения запроса к БД, каждый из которых соответствует одной реляционной операции. Если же сформулировать тот же запрос с использованием реляционного исчисления, то мы получили бы формулу, которую можно было бы прочитать, например, следующим образом: Выдать СТУД_ИМЯ и СТУД_НОМ для таких студентов, чтобы существовала группа с таким же значением ГР_СТАР и значением ГР_КОЛ большим 25.
Во второй формулировке мы указали лишь характеристики результирующего отношения, но ничего не сказали о способе его формирования. В этом случае СУБД должна сама решить, что за операции и в каком порядке нужно выполнить над отношениями СТУДЕНТЫ и ГРУППЫ. Оба рассмотренных в примере способа на самом деле эквивалентны, и существуют не очень сложные правила преобразования одного в другой.
Базисными понятиями реляционного исчисления являются понятие переменной с определенной для нее областью допустимых значений и понятие правильно построенной формулы, опирающейся на переменные и специальные функции.
В зависимости от того, что является областью определения переменной, различаются исчисление кортежей и исчисление доменов. В исчислении кортежей областями определения переменных являются отношения БД, то есть допустимым значением каждой переменной является кортеж некоторого отношения. В исчислении доменов областями определения переменных являются домены, на которых определены атрибуты отношений БД, то есть допустимым значением каждой переменной является значение некоторого домена.
Для определения кортежной переменной используется оператор RANGE. Например, для того, чтобы определить переменную СТУДЕНТ, областью определения которой является отношение СТУДЕНТЫ, нужно употребить конструкцию
RANGE СТУДЕНТ IS СТУДЕНТЫ
Из этого определения следует, что в любой момент времени переменная СТУДЕНТ представляет некоторый кортеж отношения СТУДЕНТЫ. При использовании кортежных переменных в формулах можно ссылаться на значение атрибута переменной. Например, для того, чтобы сослаться на значение атрибута СТУД_ИМЯ переменной СТУДЕНТ, нужно употребить конструкцию СТУДЕНТ.СТУД_ИМЯ.
Правильно построенные формулы служат для выражения условий, накладываемых на кортежные переменные. В основе таких формул лежат простые сравнения, представляющие собой операции сравнения значений атрибутов переменных или литерально заданных констант. Например, конструкция "СТУДЕНТ.СТУД_НОМ=123456" является простым сравнением. Более сложные варианты правильно построенных формул реализуются с помощью логических связок NOT, AND, OR и IF ... THEN. Наконец, допускается построение правильно построенных формул с помощью кванторов. Если F - это правильно построенная формула, в которой участвует переменная var, то конструкции EXISTS var (F) и FORALL var (F) являются правильными. Здесь квантор EXISTS обозначает "существование", a FORALL - "для всех кортежей".
Переменные, входящие в правильно построенные формулы, могут быть свободными или связанными. Все переменные, входящие в их состав, при построении которой не использовались кванторы, являются свободными. Фактически, это означает, что если для какого-то набора значений свободных кортежных переменных при вычислении формул получено значение "истина", то эти значения кортежных переменных могут входить в результирующее отношение. Если же имя переменной использовано сразу после квантора при построении формул вида EXISTS var (F) или FORALL var (F) то здесь, и во всех формулах, где она использована, var - связанная переменная. При вычислении значения такой правильно построенной формулы используется не одно значение связанной переменной, а вся ее область определения.
Пусть СТУД1 и СТУД2 - две кортежные переменные, определенные на отношении СТУДЕНТЫ. Тогда, формула
EXISTS CТУД2(СТУД1.СТУ_СТИП>СТУД2.СТУД_СТИП)
для текущего кортежа переменной СТУД1 принимает значение "истина" только в том случае, если во всем отношении СТУДЕНТЫ найдется такой кортеж, связанный с переменной СТУД2, что значение его атрибута СТУД_СТИП удовлетворяет внутреннему условию сравнения.
Правильно построенная формула
FORALL СТУД2(СТУД1.СТУД_СТИП > СТУД2.СТУД_СТИП)
для текущего кортежа переменной СТУД1 принимает значение "истина" только в том случае, если для всех кортежей отношения СТУДЕНТЫ, связанных с переменной СТУД2, значения атрибута СТУД_СТИП удовлетворяют условию сравнения.
Таким образом, правильно построенные формулы обеспечивают средства выражения условия выборки из отношений БД.
Чтобы можно было использовать реляционное исчисление для реальной работы с БД, требуется еще один компонент, который определяет набор и имена столбцов результирующего отношения. Этот компонент называется целевым списком.
Целевой список строится из целевых элементов, каждый из которых может иметь следующий вид:
- var.attr, где var - имя свободной переменной соответствующей формуле, a attr - имя атрибута отношения, на котором определена переменная var;
- var, что эквивалентно наличию подсписка var.attr1, var.attr2, ... , var.attrn, где attr1, attr2, ... , attrn включает имена всех атрибутов определяющего отношения; newname = var.attr;
- newname - новое имя соответствующего атрибута результирующего отношения.
Последний вариант требуется в тех случаях, когда в формуле используются несколько свободных переменных с одинаковой областью определения. В исчислении доменов областью определения переменных являются не отношения, а домены. Применительно к БД СТУДЕНТЫ можно говорить, например, о доменных переменных ИМЯ (значения домена - допустимые имена) или НОМ_СТУД (значения домена - допустимые номера студентов).
Основным отличием исчисления доменов от исчисления кортежей является наличие дополнительного набора предикатов (см. ниже); позволяющих выражать так называемые условия членства.
Предикатом принято называть некую логическую функцию, которая для некоторого аргумента возвращает значение ИСТИНА или ЛОЖЬ. Отношение может быть рассмотрено как предикат с аргументами, являющимися атрибутами рассматриваемого отношения. Если заданный конкретный набор кортежей присутствует в отношении, то предикат выдаст истинный результат, в противном случае - ложный.
Во всех остальных отношениях формулы и выражения исчисления доменов выглядят похожими на формулы и выражения исчисления кортежей. Реляционное исчисление доменов положено в основу большинства языков запросов, основанных на использовании форм.