Ответы к экзамену по БД, страница 3

Абстракции в моделях данных. Примеры.Иерархическая модель данныхИерархические, или древовидные, структуры данных разработаны и используются достаточно давно.Например, большинство методов индексирования базируются именно на древовидных структурах данных.Иерархическая модель данных близка по своей идее к иерархической структуре данных. Но модель описывает неконкретные методы работы и манипулирования ссылками, а способ логического представления данных, то, какимитерминами оперирует проектировщик структуры базы данных, когда отражает реальные зависимости с помощьюимеющихся в СУБД механизмов.Иерархическая модель позволяет строить иерархию элементов. То есть у каждого элемента может бытьнесколько “наследников” и существует один “родитель”. Для каждого уровня связи вводится интерпретация, зависящаяот предметной области и описывающая взаимоотношение между “родителями” и “наследниками”.

Каждый элементпредставляется с помощью записи. Структура данных, обычно используемая для представления этой записи об элементе,обычно содержит некоторые атрибуты, характеристики каждого элемента.Попробуем представить себе базу данных для описания тематических сборников по некоторой теме. Преждевсего, выделим уровни иерархии.Первый уровень - это издательства. Каждое издательство характеризуется своим названием, юридическимадресом, номером счета в банке.Каждое издательство выпускает несколько сборников. То есть издательство является “родителем” для сборникаи связано со сборником соотношением “издает” (“публикует”, “печатает” и т.д.).

Для каждого сборника появляютсятакие атрибуты, как размер, периодичность, цена, ответственный редактор, корректор и т.д.В каждом сборнике есть несколько статей (хотя бы, одна). То есть сборник и статья связаны соотношением“включает”.

Далее, у каждой статьи есть название, авторы.Авторы представляются отдельным элементом и образуют следующий уровень иерархии. Каждый авторхарактеризуется фамилией, именем, отчеством, гонораром и т.д. Статьи связаны с автором соотношением “написаны”.Графическое представление этого примера приведено на Рис.2.2. Элементы нарисованы прямоугольниками, ихназвания даны обычным шрифтом.

Связи нарисованы стрелками и их названия даны курсивом, атрибуты для каждогоэлемента на этой схеме не показаны - они являются частью элемента данных.ИздательствовыпускаетСборниксодерж итСтатьянаписанаАвторданных)Рис.2.2. Графическое представление иерархической модели данных (справа пример какой-то конкретной базыДостоинства иерархических СУБД: возможность реализовать быстрый поиск нужных значений, когда условиязапроса соответствуют иерархии в схеме базе данных.Недостатки иерархических СУБД: например, если запрос не соответствует имеющейся иерархии, то и егопрограммирование, и его исполнение, потребуют значительных усилий. Например, попытки реализовать запрос типа “вскольких сборниках статей опубликовал свои статьи какой-либо автор” может оказаться весьма трудной задачей (мыможем искать в направлении от статьи к автору, но не наоборот). Другим недостатком иерархической модели являетсясложность внесения в нее изменений.

Если, по каким-то причинам изменились условия задачи, и модель предметнойобласти перестала быть иерархической (например, в нашем примере, мы хотим иметь не только зависимость авторов отстатьи, но и статей от автора), то приведение схемы базы данных в соответствие предметной области становитсянетривиальной задачей.Недостатки иерархической модели проистекают оттого, что данная модель слишком жесткая. Иерархическаямодель очень хорошо подходит для устоявшихся предметных областей с четкими зависимостями “родитель-потомок”, тоесть к моделям, где есть четкая субординация между понятиями.Сетевая модель данныхСетевая модель данных является развитием иерархической модели. В сетевой модели, так же как и виерархической модели, есть понятие элемента данных и связи, которая может быть именована.

Главное отличие сетевоймодели от иерархической заключается в том, что к каждому элементу может идти связь не от одного элемента(“родителя”), а от нескольких.Например, генеалогическое дерево, построенное только по мужской линии (или, только по материнской),является древовидной, иерархической структурой - у каждого человека (элемента), есть только один родитель. Если жевключать в генеалогическое дерево всех родителей, то такое дерево с точки зрения структур данных будет уже недеревом, а сетью:мужПетров И.В.Петрова О.Ф.ж енаребенокребенокмат ьот ецПетров С.И.Рис.2.3. Представление фрагмента генеалогического дерева на основе сетевой модели данныхНа данном рисунке представлены элементы только одно класса - описание людей, и на этом множестве длянекоторых конкретных пар людей существуют связи, именуемые “муж”, “жена”, “отец”, “мать”, “ребенок”.

Поэтому сточки зрения графического представления схемы этой базы данных (а не конкретных данных о семье Петровых), можноиспользовать следующий рисунок:мат ьмужот ецЧеловекж енаребенокРис.2.4. Представление схемы базы данных генеалогического дерева на основе сетевой модели данныхСетевая модель данных основывается на понятии элемента данных и связей, задающих логикувзаимоотношениями между данными. Связи от каждого элемента могут быть направлены на произвольное количестводругих элементов. На каждый элемент могут быть направлены связи от произвольного числа других элементов. Каждыйэлемент данных описывает некоторое понятие из предметной области и характеризуется некоторыми атрибутами.

Длякаждого элемента данных (элемент - это часть схемы) в реальной базе данных может существовать несколькоэкземпляров этого элемента. С каждым конкретным экземпляром по конкретной связи может быть связано разное числоэкземпляров другого элемента (например, у каждого человека разное число детей), но число видов связи одинаково длявсех экземпляров одного элемента.Если мы вернемся к нашему примеру про издательства тематических сборников (этот пример рассматривался вразделе про иерархические СУБД) и попытаемся расширить его, для того чтобы он более полно соответствовал реальнымвзаимоотношениям, то схема базы данных будет выглядеть следующим образом:Издательствовыпускаетсот рудничает сСборникопубликована всодерж итСтатьянаписалнаписанаАвторРис.2.5. Представление расширенной схемы базы данных для описания издательств на основе сетевой моделиК достоинствам сетевой модели относится очень высокая скорость поиска и возможность адекватнопредставлять многие задачи в самых разных предметных областях.

Высокая скорость поиска основывается наклассическом способе физической реализации сетевой модели - на основе списков.Главным недостатком сетевой модели, как, впрочем, и иерархической, является ее жесткость. Поиск данных,доступ к ним, возможен только по тем связям, которые реально существуют в данной конкретной модели. При поискеданных сетевая СУБД требует перемещаться только по существующим, заранее предусмотренным связям.Реляционная структура данныхВ конце 60-х годов появились работы, в которых обсуждались возможности применения различных табличныхдаталогических моделей данных, т.е.

возможности использования привычных и естественных способов представленияданных. Наиболее значительной из них была статья сотрудника фирмы IBM д-ра Э. Кодда (Codd E.F., A Relational Modelof Data for Large Shared Data Banks. CACM 13: 6, June 1970), где, вероятно, впервые был применен термин "реляционнаямодель данных".Будучи математиком по образованию, Э.

Кодд предложил использовать для обработки данных аппарат теории множеств(объединение, пересечение, разность, декартово произведение). Он показал, что любое представление данных сводится ксовокупности двумерных таблиц особого вида, известного в математике как отношение – relation (англ.).Наименьшая единица данных реляционной модели – это отдельное атомарное (неразложимое) для данной моделизначение данных. Так, в одной предметной области фамилия, имя и отчество могут рассматриваться как единое значение,а в другой – как три различных значения.Доменом называется множество атомарных значений одного и того же типа.

Отношение на доменах D1, D2, ..., Dn (необязательно, чтобы все они были р азличны) со стоит из заголовка и тела. На р ис. 2 .6 пр иведен пр имер о тношения длярасписания движения самолетов.Заголовок (интерпретация) состоит из такого фиксированного множества атрибутов A1, A2, ..., An, что существуетвзаимно однозначное соответствие между этими атрибутами Ai и определяющими их доменами Di (i=1,2,...,n).Рис. 2.6.

Отношение с математической точки зрения (Ai - атрибуты, Vi - значения атрибутов)Тело состоит из меняющегося во времени множества кортежей, где каждый кор теж со стоит в свою очер едь измножества пар атрибут-значение (Ai:Vi), (i=1,2,...,n), по одной такой паре для каждого атрибута Ai в заголовке. Длялюбой заданной пары атрибут-значение (Ai:Vi) Vi является значением из единственного домена Di, который связан сатрибутом Ai.Степень отношения – это число его атрибутов. Отношение степени один называют унарным, степени два – бинарным,степени три – тернарным, ..., а степени n – n-арным.Кардинальное число или мощность отношения – это число его кортежей.