18.Базы данных., 12/11/2007
Структуры данных, рассмотренные в предыдущих лекциях, широко использу-ются в различных информационных системах. В самом широком смысле информаци-онная система представляет собой программный комплекс, функции которого состоят в поддержке надежного хранения информации в памяти компьютера, выполнении специфических для данного приложения преобразований информации и/или вычис-лений, предоставлении пользователям удобного и легко осваиваемого интерфейса. Обычно объемы информации, с которыми приходится иметь дело таким системам, достаточно велики, а сама информация имеет достаточно сложную структуру. Клас-сическими примерами информационных систем являются банковские системы, системы резервирования авиационных или железнодорожных билетов, мест в гостиницах и т.д. Такие информационные системы, которые в едином комплексе осуществляют хранение, выбор и модификацию постоянно существующей информации называют базами данных (БД). Комплекс, состоящий из технических средств и специальных программных компонентов и обеспечивающий создание, использование и обслуживание БД, называется системой управления базами данных (СУБД). В структуре СУБД можно выделить четыре важнейших уровня - уровни физической модели данных, логической модели, внешних моделей и прикладной уровень.
Физическая модель данных располагается на самом нижнем уровне в структу-ре СУБД. Эта модель описывается в виде внутренней, или машинной, схемы базы данных и содержит сведения о характеристиках устройств внешней памяти, форматах используемых физических записей, индексах, каталогах и т.п. Собственно база дан-ных располагается на устройствах внешней памяти и непосредственно связана с физической моделью данных.
Логическая модель данных - абстрактное представление БД в терминах логи-ческих характеристик данных и отношений между элементами данных (например, в терминах логических записей, полей логических записей, отношений между логиче-скими записями и полями логических записей). Другое название логической модели - концептуальная модель данных. Логическая модель выражается с помощью концеп-туальной схемы. Наиболее известны иерархическая, сетевая и реляционная схемы баз данных.
Внешняя модель данных характеризует собой ту часть логической модели, ко-торая «видима» определенному пользователю. Иными словами, внешняя модель пред-ставляет собой описание тех элементов базы данных и отношений между этими эле-ментами, которые необходимы для определенных прикладных программ. Приклад-ной уровень СУБД охватывает прикладные программы, предназначенные для выпол-нения в среде СУБД. Прикладные программы создаются пользователями на специ-альном языке базы данных. В современных СУБД обычно поддерживается единый интегрированный язык, содержащий все необходимые средства для работы с БД, на-чиная от ее создания, и обеспечивающий базовый пользовательский интерфейс с ба-зами данных. Стандартным языком наиболее распространенных в настоящее время реляционных СУБД является язык SQL (Structured Query Language).
17.2 Иерархическая и сетевая модели баз данных.
В зависимости от используемой логической модели данных принято различать следующие три основных класса СУБД: иерархические СУБД, сетевые СУБД, реля-ционные СУБД.
Иерархическая БД состоит из упорядоченного набора деревьев; более точно, из упорядоченного набора нескольких экземпляров одного типа дерева.
Тип дерева состоит из одного "корневого" типа записи и упорядоченного набо-ра из нуля или более типов поддеревьев (каждое из которых является некоторым ти-пом дерева). Тип дерева в целом представляет собой иерархически организованный набор типов записи.
Здесь Отдел является предком для Начальник и Сотрудники, а Начальник и Со-трудники - потомки Отдел. Между типами записи поддерживаются связи.
Для БД определен полный порядок обхода - сверху- вниз, слева- направо.
Примерами типичных операторов манипулирования иерархически организо-ванными данными могут быть следующие:
Найти указанное дерево БД (например, отдел 310);
Перейти от одного дерева к другому;
Перейти от одной записи к другой внутри дерева (например, от отдела - к пер-вому сотруднику);
Перейти от одной записи к другой в порядке обхода иерархии;
Вставить новую запись в указанную позицию;
Удалить текущую запись.
Сетевой подход к организации данных является расширением иерархического. В иерархических структурах запись-потомок должна иметь в точности одного предка; в сетевой структуре данных потомок может иметь любое число предков.
Сетевая БД состоит из набора записей и набора связей между этими записями, а если говорить более точно, из набора экземпляров каждого типа из заданного в схеме БД набора типов записи и набора экземпляров каждого типа из заданного набора ти-пов связи. Тип связи определяется для двух типов записи: предка и потомка. Экземп-ляр типа связи состоит из одного экземпляра типа записи предка и упорядоченного набора экземпляров типа записи потомка. Для данного типа связи L с типом записи предка P и типом записи потомка C должны выполняться следующие два условия:
Каждый экземпляр типа P является предком только в одном экземпляре L;
Каждый экземпляр C является потомком не более, чем в одном экземпляре L.
На формирование типов связи не накладываются особые ограничения; возмож-ны, например, следующие ситуации:
a.Тип записи потомка в одном типе связи L1 может быть типом записи предка в другом типе связи L2 (как в иерархии).
b.Данный тип записи P может быть типом записи предка или потомка в любом числе типов связи.
c.Может существовать любое число типов связи с одним и тем же типом запи-си предка и одним и тем же типом записи потомка; и если L1 и L2 - два типа связи с одним и тем же типом записи предка P и одним и тем же типом запи-си потомка C, то правила, по которым образуется родство, в разных связях могут различаться.
d.Типы записи X и Y могут быть предком и потомком в одной связи и потом-ком и предком - в другой.
Примерный набор операций может быть следующим:
Найти конкретную запись в наборе однотипных записей (инженера Сидорова);
Перейти к следующему потомку в некоторой связи (от Сидорова к Иванову);
Перейти от потомка к предку по некоторой связи (найти отдел Сидорова);
Создать новую запись, уничтожить запись, модифицировать запись; Достоинства ранних СУБД:
Развитые средства управления данными во внешней памяти на низком уровне;
Возможность построения вручную эффективных прикладных систем;
Возможность экономии памяти за счет разделения подобъектов (в сетевых системах). Недостатки:
Слишком сложно пользоваться;
Фактически необходимы знания о физической организации;
Прикладные системы зависят от этой организации;
Их логика перегружена деталями организации доступа к БД.
17.3 Реляционные базы данных.
Реляционный подход к организации баз данных является наиболее распростра-ненным в настоящее время и обладает рядом следующих достоинств:
наличие небольшого набора абстракций, которые позволяют сравнительно просто моделировать большую часть распространенных предметных областей и до-пускают точные формальные определения, оставаясь интуитивно понятными;
наличие простого и в то же время мощного математического аппарата, опи-рающегося главным образом на теорию множеств и математическую логику и обеспе-чивающего теоретический базис реляционного подхода к организации баз данных;
возможность манипулирования данными без необходимости знания конкретной физической организации баз данных во внешней памяти. Реляционные системы далеко не сразу получили широкое распространение. В то время, как основные теоретические результаты в этой области были получены еще в 70-х, и тогда же появились первые прототипы реляционных СУБД, долгое время считалось невозможным добиться эффективной реализации таких систем. Однако от-меченные выше преимущества и постепенное накопление методов и алгоритмов орга-низации реляционных баз данных и управления ими привели к тому, что уже в сере-дине 80-х годов реляционные системы практически вытеснили с мирового рынка ранние СУБД.
В основе реляционной модели базы данных лежит математическое понятие от-ношения (от англ. relation), откуда и происходит название этого типа модели БД. Ос-новными понятиями реляционных баз данных являются тип данных, домен, атрибут, кортеж, первичный ключ и отношение. Для начала покажем смысл этих понятий на примере отношения СОТРУДНИКИ:
Понятие тип данных в реляционной модели данных полностью адекватно поня-тию типа данных в языках программирования. Обычно в современных реляционных БД допускается хранение символьных, числовых данных, битовых строк, специализи-рованных числовых данных (таких как "деньги"), а также специальных данных (дата, время, временной интервал). Достаточно активно развивается подход к расширению возможностей реляционных систем абстрактными типами данных.
Понятие домена более специфично для баз данных, хотя и имеет некоторые аналогии с подтипами в некоторых языках программирования. В самом общем виде домен определяется заданием некоторого базового типа данных, к которому относятся элементы домена, и произвольного логического выражения, применяемого к элементу типа данных. Если вычисление этого логического выражения дает результат "истина", то элемент данных является элементом домена. Наиболее правильной интуитивной трактовкой понятия домена является понимание домена как допустимого потенциаль-ного множества значений данного типа. Например, домен "Имена" в нашем примере определен на базовом типе строк символов, но в число его значений могут входить только те строки, которые могут изображать имя (в частности, такие строки не могут начинаться с мягкого знака).
Схема отношения - это именованное множество пар {имя атрибута, имя домена (или типа, если понятие домена не поддерживается)}. Отношение - это множество кортежей, соответствующих одной схеме отношения. Обычным житейским представ-лением отношения является таблица, заголовком которой является схема отношения, а строками - кортежи отношения-экземпляра; в этом случае имена атрибутов именуют столбцы этой таблицы. Поэтому иногда говорят "столбец таблицы", имея в виду "ат-рибут отношения". Как правило, один или несколько атрибутов в каждом отношении используются в качестве ключа. Ключ - это такой атрибут (или совокупность несколь-ких атрибутов), значение которого идентифицирует каждый кортеж, или запись, в таблице, представляющей данное отношение. Ключ данного отношения называется первичным ключом.
17.4 Внутренняя организация реляционных СУБД
Реляционные СУБД обладают рядом особенностей, влияющих на организацию внешней памяти :
наличие двух уровней системы: уровня непосредственного управления данны-ми во внешней памяти (а также обычно управления буферами оперативной памяти, управления транзакциями и журнализацией изменений БД) и языкового уровня (на-пример, уровня, реализующего язык SQL). При такой организации подсистема нижне-го уровня должна поддерживать во внешней памяти набор базовых структур, кон-кретная интерпретация которых входит в число функций подсистемы верхнего уров-ня.
Поддержание отношений-каталогов. Информация, связанная с именованием объектов базы данных и их конкретными свойствами (например, структура ключа ин-декса), поддерживается подсистемой языкового уровня. С точки зрения структур внешней памяти отношение-каталог ничем не отличается от обычного отношения ба-зы данных.
Регулярность структур данных. Поскольку основным объектом реляционной модели данных является плоская таблица, главный набор объектов внешней памяти может иметь очень простую регулярную структуру.
При этом необходимо обеспечить возможность эффективного выполнения операторов языкового уровня как над одним отношением (простые селекция и проек-ция), так и над несколькими отношениями (наиболее распространено и трудоемко со-единение нескольких отношений). Для этого во внешней памяти должны поддержи-ваться дополнительные "управляющие" структуры - индексы.
Наконец, для выполнения требования надежного хранения баз данных необ-ходимо поддерживать избыточность хранения данных, что обычно реализуется в виде журнала изменений базы данных. Соответственно возникают следующие разновидности объектов во внешней памяти базы данных:
строки отношений - основная часть базы данных, большей частью непосредст-венно видимая пользователям;
управляющие структуры - индексы, создаваемые по инициативе пользователя (администратора) или верхнего уровня системы из соображений повышения эффек-тивности выполнения запросов и обычно автоматически поддерживаемые нижним уровнем системы;
журнальная информация, поддерживаемая для удовлетворения потребности в надежном хранении данных;
служебная информация, поддерживаемая для удовлетворения внутренних по-требностей нижнего уровня системы (например, информация о свободной памяти).
Общей идеей любой организации индекса, поддерживающего прямой доступ по ключу и последовательный просмотр в порядке возрастания или убывания значений ключа является хранение упорядоченного списка значений ключа с привязкой к каж-дому значению ключа списка идентификаторов кортежей. Наиболее популярным под-ходом к организации индексов в базах данных является использование техники B-деревьев. С точки зрения внешнего логического представления B-дерево - это сбалан-сированное сильно ветвистое дерево во внешней памяти. Сбалансированность означа-ет, что длина пути от корня дерева к любому его листу одна и та же. Ветвистость де-рева - это свойство каждого узла дерева ссылаться но большое число узлов-потомков. С точки зрения физической организации B-дерево представляется как мультисписоч-ная структура страниц внешней памяти, т.е. каждому узлу дерева соответствует блок внешней памяти (страница). Внутренние и листовые страницы обычно имеют разную структуру.
При этом выдерживаются следующие свойства:
ключ(1) <= ключ(2) <= ... <= ключ(n);
в странице дерева Nm находятся ключи k со значениями ключ(m) <= k <= ключ(m+1). Листовая страница обладает следующими свойствами:
ключ(1) < ключ(2) < ... < ключ(t);
сп(r) - упорядоченный список идентификаторов кортежей (tid), включающих значение ключ(r);
листовые страницы связаны одно- или двунаправленным списком.
Поиск в B-дереве - это прохождение от корня к листу в соответствии с задан-ным значением ключа. Заметим, что поскольку деревья сильно ветвистые и сбаланси-рованные, то для выполнения поиска по любому значению ключа потребуется одно и то же (и обычно небольшое) число обменов с внешней памятью.
Альтернативным и все более популярным подходом к организации индексов является использование техники хэширования. Общей идеей методов хэширования является применение к значению ключа некоторой функции свертки (хэш-функции), вырабатывающей значение меньшего размера. Свертка значения ключа затем исполь-зуется для доступа к записи. В самом простом, классическом случае, свертка ключа используется как адрес в таблице, содержащей ключи и записи. Основным требовани-ем к хэш-функции является равномерное распределение значение свертки. При воз-никновении коллизий (одна и та же свертка для нескольких значений ключа) образу-ются цепочки переполнения. Главным ограничением этого метода является фиксиро-ванный размер таблицы. Если таблица заполнена слишком сильно или переполнена, но возникнет слишком много цепочек переполнения, и главное преимущество хэши-рования - доступ к записи почти всегда за одно обращение к таблице - будет утрачено. Расширение таблицы требует ее полной переделки на основе новой хэш-функции (со значением свертки большего размера). В случае баз данных такие действия являются абсолютно неприемлемыми. Поэтому обычно вводят промежуточные таблицы- спра-вочники, содержащие значения ключей и адреса записей, а сами записи хранятся от-дельно. Тогда при переполнении справочника требуется только его переделка, что вы-зывает меньше накладных расходов. Чтобы избежать потребности в полной передел-ки справочников, при их организации часто используют технику B-деревьев с расще-плениями и слияниями. Хэш-функция при этом меняется динамически, в зависимости от глубины B-дерева. Путем дополнительных технических ухищрений удается до-биться сохранения порядка записей в соответствии со значениями ключа. В целом ме-тоды B-деревьев и хэширования все более сближаются.
Автор: it-library, количество прочтений: 6839 Наверх
Ал...
Да...