LOGO Основные методы организации БД Дисциплина: «Проектирование баз данных» Специальность: 08080165 «Прикладная информатика (в экономике)» Институт информатики, - презентация

1 LOGO Основные методы организации БД Дисциплина: «Проектирование баз данных» Специальность: «Прикладная информатика (в экономике)» Институт информатики, инноваций и бизнес систем Кафедра информатики, инженерной и компьютерной графики Старший преподаватель Богданова О.Б.

2 Company Logo Основные дидактические единицы Физический доступ к базе данных. Физические средства хранения данных. Организация данных и способы адресации: последовательная организация файлов; индексно- последовательная организация файлов; прямая организация файлов; статические и динамические хэш- функции. Реализация логических отношений: связанные списки; инвертированные списки; В-деревья. Преобразование логической структуры реляционной базы данных в физическую структуру.

3 Company Logo Основные методы организации БД Существует определенная схема управления физическим доступом для организации представления данных на уровне интерфейса.

4 Company Logo Основные методы организации БД

5 Company Logo Интерфейс внешней записи Создан для отвлечения пользователя от изучения структуры файлов, связей между файлами и т.д. Интерфейс хранимых записей Представляет структуру хранения в виде файлов, каждый из кот. состоит из записей одного типа, и связей между файлами. Интерфейс физических записей Структура хранения файлов в соответствии с установленной файловой системой. Основные методы организации БД

6 Company Logo Основные методы организации данных на уровне интерфейса хранимых записей Предположим, что существует файл, упорядоченный по значению первичного ключа. Данный файл на уровне интерфейса физических записей будет представлен в соответствии с файловой структурой ОС. А на уровне интерфейса хранимых записей его организация может быть различной, т.е. СУБД будет видеть записи в базе в зависимости от варианта организации.

7 Company Logo STATUS Вл-к Москва Артем Москва CITY МеталснабS2 Завод ЭВМS4 ПримснабS5 ХимснабS3 ГлавснабS1 SNAMES# 1 вариант: Создание таблицы с первичным ключом. Файл SUPLIER

8 Company Logo Существует единственный хранимый файл, который содержит 5 записей по одной на каждого поставщика. Преимущества: простота и очевидность. Недостатки: 1) медленный поиск (кроме запроса «найти все сведения о поставщике»); 2) нет экономии памяти. 1 вариант: Создание таблицы с первичным ключом.

9 Company Logo 2 вариант: Факторизация (по полю CITY) STATUSCITY МеталснабS2 Завод ЭВМS4 ПримснабS5 ХимснабS3 ГлавснабS1 SNAMES# Вл-к Артем Москва CITY Файл CITY Файл SUPLIER

10 Company Logo В случае факторизации данные размещаются по 2-м файлам, причем с указателями из исходного на дополнительный. Это основной принцип организации справочника. Преимущества: экономия памяти в том случае, если количество записей в исходной файле (SUPLIER) велико, а в факторизованном файле (CITY) мало. Недостатки: с т.з. поиска данная структура не является достаточно оптимальной особенно для запросов «найти все сведения о поставщике» и «найти всех поставщиков в одном городе». 2 вариант: Факторизация (по полю CITY)

11 Company Logo 3 вариант: Индексирование по определенному полю Вл-к Артем Москва CITYSuplier STATUS МеталснабS2 Завод ЭВМS4 ПримснабS5 ХимснабS3 ГлавснабS1 SNAMES# Файл CITY Файл SUPLIER

12 Company Logo В данном случае указатели направлены из индексного файла в основной. Данный метод с точки зрения памяти аналогичен предыдущему, с точки зрения поиска он обеспечивает лучшие характеристики для запроса «найти всех поставщиков в одном городе» и худшее для запроса «все сведения о поставщике», «статус поставщика». Данный индексированный файл (CITY) можно считать плотным вторичным индексом, что означает: индекс таблицы CITY содержит отдельную запись для каждого экземпляра хранимой записи исходного файла (SUPLIER). 3 вариант: Индексирование по определенному полю

13 Company Logo Механизм индексирования Один из механизмов индексирования предполагает, что записи в исходном файле имеют ключи со значениями из натурального ряда и перед выполнением индексирования эти ключи упорядочены по возрастанию. Записи загружаются в файл, плотно заполняя блоки (без пробелов) и после чего система формирует строку в таблице младших индексов, ставя в соответствие блока и мах-ый ключ в этом блоке (такая таблица формируется на определенное кол-во блоков). После заполнения таблицы формируется строка в таблице старшего индекса, где ставится в соответствие таблицы младшего индекса и мах-го ключа.

14 Company Logo Москва S1 Главснаб S4 Завод Владивосток S5 Примснаб Артем S2 Металснаб S3 Химснаб вариант: Сочетание факторизации и индексирования

15 Company Logo 5 вариант: Использование цепочек указателей Владивосток АртемМосква S1 Главснаб S2 Металснаб S3 Химснаб S4 Завод S5 Примснаб

16 Company Logo 6 вариант: Иерархическая организация S1 Главснаб 30 S4 Завод 10 S2 Металлоснаб 20 S3 Химический 20 S4 Приморский 20 Москва Артем Вл-к В1 В2 В3 А С5 С1 С2 С3 С4 Блок 1 Блок 2 А1В1С1С2В2 С3С4В3С5

17 Company Logo 7 вариант: Инвертированная организация S5 S4 S3 S2 S1 Ук-ли Металснаб Завод ЭВМ Примснаб Химснаб Главснаб SNAME Индекс SNAME S1 S2 S3 S5 S4 Ук-ли SNAME Индекс STATUS

18 Company Logo S1 S4 S5 S2 S3 Ук-ли Вл-к Москва Артем SNAME Индекс CITY S2 S4 S5 S3 S1 S# Индекс SUPLIER 7 вариант: Инвертированная организация

19 Company Logo 8 вариант: Хеш - адресация S S S S S Адрес хранения записи = остаток от делания S#/13

20 Company Logo 8 вариант: Хеш - адресация 5 S 200 Металлоснаб 20 Артем 10 S 400 Завод 20 Москва 1 S 300 Химснаб 20 Артем 9 S 100 Приборснаб 20 Вл-к 6 S 500 Главснаб 30 Москва

21 Company Logo Вопросы по теме лекции 1. Что означает термин стратегический селектор? 2. Объясните назначение диспетчера файлов. 3. Сравните последовательную, индексно- последовательную и прямую организацию файлов. 4. Какие характеристики должны быть у хорошего алгоритма хэширования? 5. Для чего применяются указатели?

22 Company Logo Использование материалов презентации Использование данной презентации, может осуществляться только при условии соблюдения требований законов РФ об авторском праве и интеллектуальной собственности, а также с учетом требований настоящего Заявления. Презентация является собственностью авторов. Разрешается распечатывать копию любой части презентации для личного некоммерческого использования, однако не допускается распечатывать какую-либо часть презентации с любой иной целью или по каким-либо причинам вносить изменения в любую часть презентации. Использование любой части презентации в другом произведении, как в печатной, электронной, так и иной форме, а также использование любой части презентации в другой презентации посредством ссылки или иным образом допускается только после получения письменного согласия авторов.

23 LOGO Основные методы организации БД