- •Содержание
- •1. Основные понятия баз данных
- •1.1. Проектирование баз данных
- •1.2. Индексы и ключи в базах данных
- •2. Функциональные зависимости
- •2.1. Понятие функциональной зависимости
- •2.2. Метод синтеза
- •2.3. Аксиомы вывода
- •2.4. Применение аксиом вывода
- •2.5. Замыкание множества атрибутов относительно множества функциональных зависимостей
- •2.6. Эквивалентность двух систем функциональных зависимостей
- •2.7 Метод синтеза
- •2.8. Классы эквивалентности функциональных зависимостей с эквивалентными левыми частями
- •2.9. Составные функциональные зависимости и кольцевые покрытия
- •3. Нормализация баз данных
- •3.1. Декомпозиция таблицы на две таблицы без потери информации и с потерей информации
- •4. Иерархия в базах данных
- •4.1. Использование иерархии в базах данных
- •4.2. Инклюзивная и эксклюзивная иерархии
- •5. Сортировка и поиск записей в базах данных
- •5.1.Многофазная сортировка
- •7. Оптимизация запросов
- •7.1. Основные операции реляционной алгебры и их обозначения
- •8. Статистические данные, используемые для минимизации запросов
- •8.1. Анализ стоимости операций
- •8.2. Оценка размеров промежуточных отношений
- •8.2.1. Оценка размера результата операции объединения
- •8.2.2. Оценка размера результата операции пересечения
- •8.2.3. Оценка размера результата оператора проекции
- •8.2.4. Оценка размера результата оператора выбора
- •8.3. Выборка с условием равенства двух атрибутов
- •8.4. Выборка при условии неравенства двух атрибутов
- •8.5. Естественное соединение отношений с несколькими общими атрибутами
- •8.6. Соединение нескольких отношений
- •8.7. Оценка размеров результатов выполнения других операторов
- •8.7.1. Объединение
- •8.7.2. Пересечение
- •8.7.3. Разность
- •8.7.4. Удаление кортежей-дубликатов
- •8.7.5. Группирование и агрегирование
- •8.8. Свод формул для сравнительного расчета количества записей результата выполнения операций реляционной алгебры
- •8.9. Тождественные преобразования для операций реляционной алгебры
- •8.10. Алгебраические законы и планы запросов
- •8.10.1. Коммутативный и ассоциативный законы
- •8.11. Законы для "множественных" и "мультимножественных" версий операторов
- •8.11.1. Законы выбора
- •8.11.2. Некоторые тривиальные законы
- •8.11.3. Законы проекции
- •8.11.4. Законы соединения и декартова произведения
- •8.11.5. Законы, касающиеся удаления кортежей-дубликатов
- •8.11.6. Законы группирования и агрегирования
- •8.11.7. Закон деления
4. Иерархия в базах данных
4.1. Использование иерархии в базах данных
Пусть нужно составить базу данных, в которой должна содержаться информация о сотрудниках предприятия: инженерах и рабочих. Причем оплата труда у инженеров определяется в зависимости от оклада, а у рабочих по тарифу.
Рассмотрим различные варианты реализации данной предметной области.
1)
Таблица 4.1 – Инженер
TN |
F |
I |
O |
Oklad |
|
|
|
|
|
Таблица 4.2 – Рабочий
TN |
F |
I |
O |
Tarif |
|
|
|
|
|
2)
Таблица 4.3 – Личность
TN |
F |
I |
O |
D |
|
|
|
|
|
Таблица 4.4 – Инженер
TN |
Oklad |
|
|
Таблица 4.5 – Рабочий
TN |
Tarif |
|
|
TN – табельный номер,
F – фамилия,
I – имя,
O – отчество,
D – дискриминатор,
Oklad – оклад,
Tarif – тариф.
Наиболее эффективным является второй вариант, так как доступ к нужной информации об оплате ускоряется. Данная реализация называется иерархией (рисунок 4.1).
Рис. 4.1 - Иерархия в базе данных
Пример.
Рис. 4.2 - Пример иерархии в базе данных
Функциональные зависимости, сохраняющие иерархию:
A,B D1234567
Tip1256A, Tip1256B C, D1256,A,B
Tip26A, Tip26B E, D26, Tip1256A, Tip1256B
Tip7A, Tip7B Tip7, Tip37A, Tip37B
4.2. Инклюзивная и эксклюзивная иерархии
Если объекты, принадлежащие разным сущностям одного уровня иерархии не пересекаются, то такая иерархия называется эксклюзивной. В проти вном случае инклюзивной.
Например, общее – комплектующие, одноуровневые сущности – дисплей и винчестер.
Пример инклюзивной иерархии.
Если один и тот же объект может принадлежать двум различным сущностям одного уровня иерархии, в таком случае используют инклюзивную иерархию.
Рассмотрим пример базы данных «Центр досуга». Существуют 3 секции: каратэ, живопись, танцы. Ученик имеет уникальный номер. Причем ученик может состоять в нескольких секциях одновременно под одним и тем же номером. Возможна следующая реализация данной задачи.
Рис.4.3 - Реализация задачи без использования иерархии
NCHK – номер ученика,
F – фамилия,
I – имя,
O – отчество,
C – класс,
S – секция,
N – номер кабинета,
SP – фамилия преподавателя,
NP – имя преподавателя.
Реализация с помощью инклюзивной иерархии
Рис. 4.4 - Реализация задачи с использованием иерархии
5. Сортировка и поиск записей в базах данных
5.1.Многофазная сортировка
Пусть имеем исходный файл размера Q. Исходный файл частями объемом равным М записывается в оперативную память. Каждая часть в ОП сортируется внутренней быстрой сортировкой и как отсортированный подсписок часть файла записывается на диск. Это первая фаза. Во второй фазе память делится на L буферов, где L>=Q/M.
Объем каждого буфера должен быть не меньше чем объем блока. Начальный блок каждого из отсортированных подсписков записывается в свой буфер. В каждом из буферов выбирается первая запись и среди них находится минимальная с точки зрения сортировки, удаляется из буфера и записывается в единственный выходной буфер.
Процесс циклически повторяется до тех пор, пока один из буферов не опустошится. Если он опустошился, в него записывается следующий блок из того же самого отсортированного подсписка.
Алгоритм заканчивается, когда все блоки опустошаются и ни один блок нельзя подкачать.
Рис. 5.1. Многофазная сортировка
.
Рис. 5.2. Многофазная сортировка
2 - количество обращений к памяти.
5.2. Выполнение основных операций реляционной алгебры при помощи многокомпонентного многофазного слияния
5.2.1.Удаление записей-дубликатов
Схема работы аналогична двухфазной многокомпонентной сортировке за исключением: после того как среди первых записей всех блоков (в ОЗУ) выбрана минимальная по сортировке, она записывается в выходной буфер, а все записи равные ей по содержанию из других буферов удаляются. Если буфер опустошился, то считывается следующий блок, и из него записи тоже удаляются.
5.2.2. Операция группировки
Выполняется по аналогичной схеме, но все совпадающие записи не удаляются, а помещаются в выходной буфер.
5.2.3. Объединение двух отношений
для наборов(в конце первого отношения записывается второе).
для множеств.
R S = Q.
R разбивается на L1 отсортированных подсписков. Отношение S разбивается на L2 отсортированных подсписков. В буферы (L1+L2) считываются буферы из каждого из отсортированных подсписков.
5.3.Операция поиска. Выборка записей по критериям
Для того, чтобы найти требуемую запись по ключу, требуется от трех до шести обращений к диску для поиска по индексному дереву (В+-дерево) и еще одно обращение к диску за блоком, где находится запись.
Если запись не ключевая, то нужно построить индекс по полям, по которым ищется запись.
6. ОСНОВЫ ЯЗЫКА ПРОГРАММИРОВАНИЯ СУБД FOXPRO
6.1. Доступ к таблицам в системе FoxPro
Таблица должна быть размещена в оперативной памяти.
Пример создания таблицы CAST.
IF NOT USED ([CAST])
USE CAST IN ø // открыть в памяти, поместить в свободный буфер
ENDIF
При открытии таблицы в память записываются все ее индексы, число которых не больше 256.
В старых языках символом «;» обозначают продолжение оператора на следующей строке, в новых – окончание оператора.
Пример. Установить порядок по полю табельный номер (TN).
SET ORDER TO TN
С каждой таблицей связан указатель доступной записи в данный момент. При первом открытии таблицы указывает на первую запись в соответствии с порядком, который задает тот индекс, который открыли.
Команды управления указателем активной записи:????
Команды изменения положения указателя в активной таблице:
SKIP – вниз на одну запись;;
SKIP -1 – вверх на одну запись;;
GOTOP – на первую запись;
GO BOTTOM – на последнюю запись.
SALE CAST – выборка активной таблицы.
Пример использования оператора SALE CAST:
IF NOT USED …
USE
SET …
ELSE
SALE CAST
ENDIF
Используется оператор ROF() , если начало таблицы, EOF()- если конец таблицы.
Оператор SALE выбирает таблицы, в которых нужно передвигать указатель.
Переход к следующей записи в активной таблице:
IF NOT EOF()
SKIP
ELSE
ENDIF
Выбор записи в таблице:
GOTOP
DO WHILE NOT EOF()
…
SKIP
ENDDO
SELE CAST
GOTOP
DO WHILE NOT EOF()
…
SELE TAB
GOTOP
DO WHILE NOT EOF()
…
SKIP
ENDDO
SELE CAST
SKIP
ENDDO
Чтобы присвоить значение полю, используют оператор REPLACE. Записывают:
REPLACE <имя поля> WITH <выражение>
Например,
REPLACE CAST.A WITH 10.