- •Серия «Учебники и учебные пособия»
- •Э.П. Голенищев
- •И.В. Клименко
- •Рецензент
- •Предисловие
- •Введение
- •Глава 1. ИФОРМАЦИОННЫЕ СИСТЕМЫ НА БАЗАХ ДАННЫХ
- •1.1. Понятие информационной системы, информационное обеспечение
- •1.2. Понятие базы данных
- •1.3. Понятие системы управления базами данных
- •1.3.1. Обобщенная архитектура СУБД
- •1.3.2. Достоинства и недостатки СУБД
- •1.3.3. Архитектура многопользовательских СУБД
- •Технология «клиент/сервер»
- •Таблица 1.1
- •1.4. Понятие независимости данных
- •1.5. Категории пользователей базой данных
- •1.5.1. Общая классификация пользователей БД
- •1.5.2. Администратор базы данных
- •1.5.3. Разделение функций администрирования
- •Таблица 1.2
- •1.6. Средства администрирования баз данных
- •Таблица 1.3
- •Глава 2. ПРОЕКТИРОВАНИЕ БАЗ ДАННЫХ
- •2.1. Жизненный цикл информационной системы
- •2.1. Подходы и этапы проектирования баз данных
- •2.2.1. Цели и подходы к проектированию баз данных
- •2.2.2. Этапы проектирования баз данных
- •2.3. Инфологическое проектирование базы данных
- •Таблица 2.1
- •Пояснение
- •2.3.1. Модель «сущность-связь»
- •2.3.2. Классификация сущностей, расширение ER-модели
- •Рис. 2.15. Пример ловушки разрыва
- •2.4. Логическое проектирование
- •2.4.1. Выбор СУБД
- •2.4.1.1. Метод ранжировки
- •Таблица 2.2
- •Таблица 2.3
- •2.4.1.2. Метод непосредственных оценок
- •2.4.1.3. Метод последовательных предпочтений
- •Таблица 2.4
- •Таблица 2.5
- •2.4.1.4. Оценка результатов экспертного анализа
- •Таблица 2.6
- •Наименование параметра
- •2.4.2. Даталогические модели данных
- •2.4.2.1. Иерархическая модель
- •2.4.2.2. Сетевая модель
- •2.4.2.3. Реляционная модель
- •2.4.2.4. Достоинства и недостатки даталогических моделей
- •2.4.3. Нормализация
- •2.4.3.1. Понятие функциональной зависимости
- •Таблица 2.7
- •2.4.3.2. Аксиомы вывода функциональных зависимостей
- •2.4.3.3. Первая нормальная форма
- •НОМЕР
- •2.4.3.4. Вторая нормальная форма
- •2.4.3.5. Третья нормальная форма
- •2.4.3.6. Нормализация через декомпозицию
- •2.4.3.7. Недостатки нормализации посредством декомпозиции
- •2.4.3.8. Нормальная форма Бойса–Кодда (НФБК)
- •2.4.3.9. Многозначные зависимости
- •Таблица 2.8
- •Таблица 2.9
- •Таблица 2.10
- •2.4.3.10. Аксиомы вывода многозначных зависимостей
- •2.4.3.11. Четвертая нормальная форма
- •2.4.3.12. Зависимости соединения
- •2.4.3.13. Пятая нормальная форма
- •2.4.3.14. Обобщение этапов нормализации
- •Глава 3. ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ ДАННЫХ В СУБД
- •3.1. Списковые структуры
- •3.1.1. Последовательное распределение памяти
- •3.1.2. Связанное распределение памяти
- •Рис. 3.4. Пример двунаправленного линейного списка
- •3.2. Модель внешней памяти
- •3.3. Методы поиска и индексирования данных
- •3.3.1. Последовательный поиск
- •Рис. 3.7. Пример организации файла при начальной загрузке
- •3.3.2. Бинарный поиск
- •3.3.3. Индекс - «бинарное дерево»
- •3.3.4. Неплотный индекс
- •3.3.5. Плотный индекс
- •3.3.6. Инвертированный файл
- •Глава 4. МАТЕМАТИЧЕСКИЕ ОСНОВЫ МАНИПУЛИРОВАНИЯ РЕЛЯЦИОННЫМИ ДАННЫМИ
- •4.1. Теоретические языки запросов
- •4.1.1. Реляционная алгебра
- •4.1.2. Реляционное исчисление кортежей
- •4.1.3. Реляционное исчисление доменов
- •4.1.4. Сравнение теоретических языков
- •4.2. Определение реляционной полноты
- •Глава 5. РАСПРЕДЕЛЕННЫЕ БАЗЫ ДАННЫХ И СУБД
- •5.1. Основные определения, классификация распределенных систем
- •5.2. Преимущества и недостатки распределенных СУБД
- •Таблица 5.1
- •5.3. Функции распределенных СУБД
- •5.4. Архитектура распределенных СУБД
- •5.5. Разработка распределенных реляционных баз данных
- •5.5.1. Распределение данных
- •Таблица 5.2
- •5.5.2. Фрагментация
- •5.5.3. Репликация
- •5.5.3.1. Виды репликации
- •5.5.3.2. Функции службы репликации
- •5.5.3.3. Схемы владения данными
- •5.5.3.4. Сохранение целостности транзакций
- •5.5.3.5. Моментальные снимки таблиц
- •5.5.3.6. Триггеры базы данных
- •5.5.3.7. Выявление и разрешение конфликтов
- •5.6. Обеспечение прозрачности
- •5.6.1. Прозрачность распределенности
- •5.6.2. Прозрачность транзакций
- •5.6.3. Прозрачность выполнения
- •5.6.4. Прозрачность использования
- •ЗАКЛЮЧЕНИЕ
- •ПРИЛОЖЕНИЯ
- •Приложение 1. Недостатки файловых систем
- •Приложение 2. Краткая история развития субд
- •Приложение 3. Сравнительная характеристика даталогических моделей
- •Сводная характеристика систем баз данных
- •Приложение 4. Пример мифологического проекта базы данных
- •Приложение 5. Обобщенная методика проектирования реляционных баз данных
- •Приложение 6. Принципы организации компьютерных сетей
- •Отличие ЛВС от систем на основе мини-ЭВМ
- •Таблица П.6.1
- •Приложение 7. Правила распределенных СУБД
- •Независимость от операционной системы
- •Приложение 8. Краткий толковый словарь
- •Содержание
Следовательно, подходящие р[ D3 ] отсутствуют.
4.1.2.Реляционное исчисление кортежей
Ввыражениях реляционной алгебры всегда явно задается некий порядок выполнения запроса. В реляционном же исчислении указывается что необходимо извлечь, а не как.
Реляционное исчисление никак не связано с дифференциальным и интегральным исчислениями в математике, а его название произошло от части символьной логики, которая называется логикой предикатов.
Влогике первого порядка или теории исчисления предикатов под предикатом подразумевается истинностная функция с аргументами. При подстановке вместо аргументов значений, функция становится выражением, называемым суждением, которое может быть истинным или ложным. Например, предложения «студент Шепелявцев учится на третьем курсе вуза» и «средний балл успеваемости студента Шепелявцева выше, чем у студента Мамаева» являются суждениями, поскольку можно определить их истинность или ложность. В первом случае функция «учится на третьем курсе вуза» имеет один аргумент («студент Шепелявцев»), а во втором случае функция «средний балл выше» имеет два аргумента («студент Шепелявцев» и «студент Мамаев»).
Если предикат содержит переменную, например в виде «ж учится на третьем курсе вуза», то у этой переменной должна быть область определения. При подстановке вместо переменной х одних значений
из ее области определения данное суждение может оказаться истинным, а при подстановке других – ложным.
Если Р – предикат, то множество всех значений переменной х, при которых суждение Р становится истинным, можно символически записать следующим образом:
Предикаты могут соединяться с помощью логических операторов , , ¬, с образованием составных предикатов.
В реляционном исчислении кортежей задача состоит в нахождении таких кортежей, для которых предикат является истинным.
Выражение реляционного исчисления с переменными-кортежами записывается в виде [17]
где t – свободная переменная-кортеж, обозначающая кортеж фиксированной длины (если необходимо указать арность кортежа, то используют запись t(i); i – арность кортежа t); φ – некоторая формула, построенная по специальным правилам.
88
Например, выражение {tï R1(t)ÚR2(t)}, где в качестве формулы выступает конструкция R1(t)ÚR2(t), означает, что необходимо получить множество всех кортежей t, причем таких кортежей, которые
принадлежат отношениям R1 или R2. Формула (R1(t)ÚR2(t)) имеет смысл только тогда, когда отношения R1 и R2 имеют одинаковую арность, поскольку переменная-кортеж t задана как переменная
фиксированной длины. Выражение {tï R1(t)ÚR2(t)} эквивалентно операции объединения (R1 È RJ реляционной алгебры.
Формулы в реляционном исчислении строятся из атомов и совокупности арифметических и логических операторов.
Атомы формул могут быть трех типов [17]:
1)R(t), где R - имя отношения. Этот атом означает, что t – это кортеж в отношении R;
2)s[i]θu[j], где s и и - переменные-кортежи; θ - арифметический оператор (<, >, =, ≤, ≥, ≠); i, j - номера или имена необходимых компонентов (столбцов) в соответствующих кортежах; s[i] – i- тый компонент в кортеже-переменной s; u[j] – j-тый компонент в кортеже-переменной и. Например, атом (s[3]≥u[5]) означает, что третий компонент переменной s больше или равен пятому компоненту переменной и;
3)s[i]θa или aθs[i], где а – константа. Например, атом (s[4]=70), означает, что четвертая компонента переменной-кортежа s равна 70.
При записи формул используется понятие свободных и связанных переменных-кортежей, что определяется характером использования в формуле кванторов; " – квантор всеобщности (общности),
читается – все, всякий, каков бы ни был и т.п.; $ – квантор существования, читается – некоторые, хотя бы один существует и т.п.
Вхождение переменной t в формулу φ связано, если в φ оно находится в подформуле, начинающейся
квантором " или $, за которым непосредственно следует переменная t и о котором говорят, что он связывает переменную t. В остальных случаях вхождения переменной t в формулу φ свободны. Например, в формуле
все вхождения переменной х связаны, первое и последнее вхождения у свободны, остальные вхождения переменной у связаны, все вхождения переменной z свободны, единственное вхождение переменной r связано.
Кванторы в реляционном исчислении играют ту же роль, что декларации в языке программирования. Понятие свободной переменной аналогично понятию глобальной переменной, описанной вне текущей процедуры. Понятие связанной переменной аналогично понятию локальной переменной, описанной в текущей процедуре.
Аналогично тому, как не все возможные комбинации букв алфавита образуют правильные слова, так и в реляционном исчислении не каждая последовательность формул является допустимой. Допустимыми формулами могут быть только недвусмысленные и небессмысленные последовательности.
Правильно построенные формулы определяются рекурсивно следующим образом [11, 17].
1.Каждый атом – это формула. Все вхождения переменных-кортежей, упомянутые в атоме, являются свободными.
2.Если φ1 и φ2 – формулы, то выражения φ1Ùφ2 (утверждает, что φ1 и φ2 истинны), φ1Úφ2 (утверждает, что φ1 или φ2, или обе истинны), Øφ1 (утверждает, что φ1 не истинна), также являются формулами.
Экземпляры переменных-кортежей – свободные или связанные в формулах (φ1Ùφ2), (φ1Úφ2) и (Øφ1) так же, как и в φ1 и φ2. Таким образом, свободными (связанными) являются те и только те вхождения переменных, которые происходят от свободных (связанных) вхождений переменных φ1 и φ2. Некоторое вхождение переменной может быть связанным в φ1, например, в то время как другое – свободным в φ2 и т.п.
3.Если φ – формула, то ("s)(φ) – также формула. Свободные вхождения переменной s в формуле φ
становятся связанными квантором ("s) в формуле ("s)(φ). Формула ("s)(φ) утверждает, что при подстановке любого кортежа подходящей арности вместо свободных вхождений s формула становится истинной.
4.Если φ – формула, то ($s)(φ) – также формула. Свободные вхождения переменной s в формуле φ
89
также становятся связанными квантором ($s) в формуле ($s)(φ). Формула ($s)(φ) утверждает, что существует значение s, при подстановке которого вместо всех свободных вхождений s в формулу φ эта формула становится истинной.
Например, формула ($s)(R(s)) означает, что отношение не пусто, т.е. существует некоторый кортеж s, принадлежащий R.
5. Формулы могут при необходимости заключаться в скобки. Используется следующий порядок старшинства:
арифметические операторы сравнения;
кванторы " и $;
Ù, Ú, Ø.
6. Ничто иное не является формулой.
В качестве примера можно записать выражение реляционного исчисления на переменных-кортежах, соответствующее операции проекции в реляционной алгебре:
Введем ограничения на конечность реальных отношений в БД, чтобы исключить возможность
формирования выражений типа {tï-R(t)}, не имеющих смысла. Это выражение обозначает все возможные, не принадлежащие R кортежи, арность которых согласуется с t.
С этой целью в реляционном исчислении рассматривают только безопасные выражения {t ïφ(t)}, для которых выполняется условие, что каждый компонент (элемент столбца) любого кортежа t, удовлетворяющего φ(t) является элементом некоторого множества элементов D(φ). Множество D(φ) определяется как функция фактических отношений, которые указываются в φ(t), и констант, присутствующих в формуле φ(t) и элементов кортежей тех отношений, которые указаны в φ(t). Так как все отношения в БД предполагаются конечными, то и множество D(φ) – конечно:
где a1.φ, а2.φ, ..., ап.φ – константы, встретившиеся в формуле φ(t); π1(R1), …, πk(Rn) – проекции кортежей фактических отношений R1, ..., Rn, встретившихся в формуле φ(t) (в данном случае – компоненты
кортежей).
При таком определении множества D(φ) справедливо следующее:
Например, если задано выражение {tïcÚR(t)}, где R – бинарное отношение, то
Реляционное исчисление является безопасным, если выполнятся следующие условия:
1)из истинности φ(t) следует, что каждый компонент кортежа t принадлежит D(φ);
2)для любой подформулы вида ($u)(φ1(u)), входящей в состав ф, из истинности φ1(и) следует, что и принадлежит D(φ1);
3)для любой подформулы вида ("u)(φ1(u)), входящей в состав φ, из истинности φ1(u) следует, что и не
принадлежит D(φ1), или же, что то же самое, из истинности Øφ1(u) следует, что и принадлежит D(φ1 ).
При выполнении этих условий выражение {t|φ(t)} является безопасным. Выражению ("u)(φ1(u))
эквивалентно выражение Ø($u)(Øφ1(u)).
На основании вышеизложенного можно утверждать, что если формула φ(t) такова, что любая ее подформула вида ($u)(φ1(t)) или ("u)(φj(t)) безопасна, то безопасно каждое выражение вида {tïR(t)Ùφ(t )}. Действительно, любой кортеж, удовлетворяющий формуле (R(t)Ùφ(t)), принадлежит в соответствии с
90
этой формулой отношению R, Следовательно, каждый из его компонентов будет принадлежать также и множеству элементов D(R(t)Ùφ(t)). Тогда в силу выполнения условия 1 (выполнение условий 2 и 3 задано как исходная предпосылка) выражение {t|R(t)Ùφ(t)} – безопасное. Если в φ(t) найдется хотя бы одна из подформул вида ($u)(φi(t)) или ("u)(φj(t)), которая окажется не безопасной, то тогда и выражение {t|R(t)Ùφ(t)} не будет безопасным. Если в формуле φ(t) вообще отсутствуют подформулы вида ($u)(φi(t)) или ("u)(φj(t)) – или соответствующие им эквивалентные -Ø("u)(Øφi(t)) или Ø($u)(Øφj(t) ), – то выражение (t|R(t)Ùφ(t)} всегда является безопасным.
Например, если φ(t) = ØR2(t), то получим безопасное выражение {tïR1(t)ÙØR2(t)}, соответствующее операции разности отношений в реляционной алгебре (R1 – R2).
Безопасным является также выражение {t|R(t)}, соответствующее выражению R (точнее – переменной R, обозначающей отношение).
В реляционном исчислении на переменных-кортежах доказана теорема, устанавливающая эквивалентность безопасных выражений в исчислении операциям реляционной алгебры.
Теорема 4.1. Если Е – выражение реляционной алгебры, то существует эквивалентное ему безопасное выражение в реляционном исчислении с переменными-кортежами [17].
Для основных операций реляционной алгебры укажем следующие соответствующие выражения реляционного исчисления на переменных-кортежах.
1.Операции объединения (R1 È R2) соответствует выражение
2.Операции разности (R1 – R2) соответствует выражение
Рассматривается все множество кортежей t, таких, что t принадлежит R1 и не принадлежит R2. 3. Операции декартова произведения (R1 Ä R2) соответствует выражение
Рассматривается все множество кортежей t арности (k+m), таких, что существует кортеж и, принадлежащий R1, и существует кортеж υ, принадлежащий R2, причем k первых компонентов кортежа t образуют компоненты кортежа и, а следующие т компонентов кортежа t образуют компоненты кортежа
υ.
4.Операции проекции соответствует выражение
5.Операции селекции соответствует выражение {tïR(t)ÙF'}, где F' – это выражение F, в котором каждый операнд, обозначающий компонент i, заменен на t[i].
Несмотря на то, что реляционное исчисление является достаточно сложным с точки зрения освоения
ииспользования, тем не менее, его непроцедурная природа считается весьма перспективной и это стимулирует поиск других, более простых в употреблении непроцедурных методов. Подобные исследования привели к появлению двух категорий реальных реляционных языков:
языков на основе преобразований;
графических языков.
Языки на основе преобразований являются классом непроцедурных языков, которые используют отношения для преобразования исходных данных к требуемому виду. Эти языки предоставляют простые в употреблении структуры для получения результата. Примером реального языка на основе преобразований, реализующего реляционное исчисление с переменными-кортежами, является язык запросов SQL.
91