Лекция (1) (1121827), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Сетевой подход к организации данных является расширением иерархического подхода. В иерархических структурах запись-потомок должна иметь в точности одного предка; в сетевой структуре данных у потомка может иметься любое число предков.

Сетевая БД состоит из набора записей и набора связей между этими записями, а если говорить более точно, из набора экземпляров каждого типа из заданного в схеме БД набора типов записи и набора экземпляров каждого типа из заданного набора типов связи.

Тип связи определяется для двух типов записи: предка и потомка. Экземпляр типа связи состоит из одного экземпляра типа записи предка и упорядоченного набора экземпляров типа записи потомка. Для данного типа связи L с типом записи предка P и типом записи потомка C должны выполняться следующие два условия:

• каждый экземпляр типа записи P является предком только в одном экземпляре типа связи L;

• каждый экземпляр типа записи C является потомком не более чем в одном экземпляре типа связи L.

На формирование типов связи не накладываются особые ограничения; возможны, например, следующие ситуации:

• тип записи потомка в одном типе связи L1 может быть типом записи предка в другом типе связи L2 (как в иерархии);

• данный тип записи P может быть типом записи предка в любом числе типов связи;

• данный тип записи P может быть типом записи потомка в любом числе типов связи;

• может существовать любое число типов связи с одним и тем же типом записи предка и одним и тем же типом записи потомка; и если L1 и L2 - два типа связи с одним и тем же типом записи предка P и одним и тем же типом записи потомка C, то правила, по которым образуется родство, в разных связях могут различаться;

• типы записи X и Y могут быть предком и потомком в одной связи и потомком и предком – в другой;

• предок и потомок могут быть одного типа записи.

На рис. 2.3 показан простой пример схемы сетевой БД. На этом рисунке показаны три типа записи: Отдел, Служащие и Руководитель и три типа связи: Состоит из служащих, Имеет руководителя и Является служащим. В типе связи Состоит из служащих типом записи-предком является Отдел, а типом записи-потомком – Служащие (экземпляр этого типа связи связывает экземпляр типа записи Отдел со многими экземплярами типа записи Служащие, соответствующими всем служащим данного отдела). В типе связи Имеет руководителя типом записи-предком является Отдел, а типом записи-потомком – Руководитель (экземпляр этого типа связи связывает экземпляр типа записи Отдел с одним экземпляром типа записи Руководитель, соответствующим руководителю данного отдела). Наконец, в типе связи Является служащим типом записи-предком является Руководитель, а типом записи-потомком – Служащие (экземпляр этого типа связи связывает экземпляр типа записи Руководитель с одним экземпляром типа записи Служащие, соответствующим тому служащему, которым является данный руководитель).

Рис. 2.3. Пример схемы сетевой базы данных

Манипулирование данными

Вот примерный набор операций манипулирования данными:

• найти конкретную запись в наборе однотипных записей (например, служащего с именем Иванов);

• перейти от предка к первому потомку по некоторой связи (например, к первому служащему отдела 625);

• перейти к следующему потомку в некоторой связи (например, от Иванова к Сидорову);

• перейти от потомка к предку по некоторой связи (например, найти отдел, в котором работает Сидоров);

• создать новую запись;

• уничтожить запись;

• модифицировать запись;

• включить в связь;

• исключить из связи;

• переставить в другую связь и т.д.

Ограничения целостности

Имеется (необязательная) возможность потребовать для конкретного типа связи отсутствие потомков, не участвующих ни в одном экземпляре этого типа связи (как в иерархической модели).

1 Заметим, что перечисляемые ниже характеристики в полной мере относятся и к другим не реляционным подходам к организации баз данных, которые возникли до появления реляционного подхода или почти одновременно с ним. В частности, подобными свойствами обладают системы, основанные на подходах MUMPS (наиболее известной в России является реализация этого подхода в СУБД Cache компании Intersystems) и Pick (этот подход реализован во многих СУБД, в частности, в СУБД UniVerse и UniData семейства U2 компании IBM).

2.4. Неформальное введение в реляционную модель данных

Как уже говорилось в начале этой лекции, основные идеи реляционной модели данных были предложены Эдгаром Коддом в 1969 г. [2.1]. Следует заметить, что, несмотря на общепризнанную значимость этой и последующих работ Кодда, посвященных реляционной модели данных, эти работы писались на идейном уровне, не были (по теперешним меркам) глубоко технически проработанными, во многих важных местах допускали неоднозначное толкование, и поэтому эти работы невозможно было использовать как непосредственное руководство для реализации СУБД, поддерживающей реляционную модель.

За прошедшие десятилетия реляционная модель развивалась в двух направлениях. Первое направление заложил знаменитый экспериментальный проект компании IBM System R (см. лекцию 12). В этом проекте возник язык SQL, изначально основанный на идеях Кодда (который также работал в IBM), но нарушающий некоторые принципиальные предписания реляционной модели. К настоящему времени в действующем стандарте языка SQL, по сути, специфицирована некоторая собственная, законченная модель данных, обзор которой мы приведем в следующем разделе этой лекции, а более подробно обсудим в лекциях 15-23.

Второе направление, начиная с 1990-х гг., возглавляет Кристофер Дейт, к которому позже примкнул Хью Дарвен. Оба этих ученых также работали в компании IBM и до 1990-х гг. внесли большой вклад в развитие языка SQL. Однако в 1990-е гг. Дейт и Дарвен пришли к выводу, что искажения реляционной модели данных, свойственные языку SQL, достигли настолько высокого уровня, что пришло время предложить альтернативу, опирающуюся на неискаженные идеи Эдгара Кодда и обеспечивающую все возможности как SQL, так и объектно-ориентированного подхода к организации баз данных и СУБД (обзор объектно-ориентированной модели данных приводится в следующем разделе).

Новые идеи Дейта и Дарвена были впервые изложены в их Третьем манифесте [2.8], а позже на основе этих идей была специфицирована модель данных [1.5]. Авторы считают, что в [1.5], на самом деле, приводится всего лишь современная и полная интерпретация идей Кодда. С этим можно соглашаться или спорить, но бесспорен один факт – Кодд не участвовал в написании этих материалов и никогда не писал ничего подобного. В следующих лекциях, тем не менее, при обсуждении реляционной модели мы будем использовать, в основном, интерпретацию Дейта и Дарвена.

В этой же лекции мы сначала приведем в данном разделе краткий и неформальный обзор основных идей реляционной модели в том виде, в котором она была предложена Коддом, а в следующем разделе также кратко и неформально обсудим предложения Дейта и Дарвена. Более строгое и формальное описание реляционной модели данных приводится в лекциях 3-6.

2.4.1. Реляционные структуры данных

Основная идея Кодда состояла в том, чтобы выбрать в качестве родовой логической структуры хранения данных структуру, которая, с одной стороны, была бы достаточно удобной для большинства приложений и, с другой стороны, допускала бы возможность выполнения над базой данных ненавигационных операций. Иерархические и, в особенности, сетевые структуры данных являются навигационными по своей природе. Ненавигационному использованию таблиц мешает упорядоченность их столбцов и, в особенности, строк.

По сути, Кодд предложил использовать в качестве родовой структуры БД «таблицы», в которых и столбцы, и строки не являются упорядоченными. Легко видеть, что такая «таблица» со множеством столбцов {A₁, A₂, …, A_n}, в которой каждый столбец A_i может содержать значения из множества T_i = {v_i1, v_i2, …, v_im} (все множества конечны), в математическом смысле представляет собой отношение над множествами {T₁, T₂, …, T_n}. Напомню, что в математике отношением над множествами {T₁, T₂, …, T_n} называется подмножество декартова произведения этих множеств, т.е. некоторое множество кортежей {{v₁, v₂, …, v_n}}, где v_i T_i. Поэтому для обозначения родовой структуры Кодд стал использовать термин отношение (relation), а для обозначения элементов отношения – термин кортеж. Соответственно, модель данных получила название реляционной модели.

Схема БД в реляционной модели данных – это набор именованных заголовков отношений вида H_i = {<A_i¹, T_i¹>, < A_i², T_i²>, …, < A_iⁿⁱ, T_iⁿⁱ>}. T_i называется доменом атрибута A_i. По Кодду, каждый домен T_i является подмножеством значений некоторого базового типа данных T_i⁺, а значит, к его элементам применимы все операции этого базового типа (в конце 1960-х гг. базовыми типами данных считались типы данных распространенных тогда языков программирования; в IBM наиболее популярными языками были PL1 и COBOL).

Реляционная база данных в каждый момент времени представляет собой набор именованных отношений, каждое из которых обладает заголовком, таким как он определен в схеме БД, и телом. Имя отношения R_i совпадает с именем заголовка этого отношения H_Ri. Тело отношения B_Ri – это множество кортежей вида {<A_i¹, T_i¹, v_i¹>, < A_i², T_i², v_i²>, …, < A_iⁿⁱ, T_iⁿⁱ, v_iⁿⁱ>}, где t_i^j T_i^j2). Во время жизни БД тела отношений могут изменяться, но все содержащиеся в них кортежи должны соответствовать заголовкам соответствующих отношений.

2.4.2. Манипулирование реляционными данными

Поскольку в реляционной модели данных заголовок и тело любого отношения представляют собой множества, к отношениям, вообще говоря, применимы обычные теоретико-множественные операции: объединение, пересечение, вычитание, взятие декартова произведения. Напомним, что для двух множеств S₁ {s₁} и S₂ {s₂} результатом операции объединения этих двух множеств S₁ UNION S₂ является множество S {s} такое, что s S₁ или s S₂. Результатом операции пересечения S₁ INTERSECT S₂ является множество S {s} такое, что s S₁ и s S₂. Результатом операции вычитания S₁ MINUS S₂ является множество S {s} такое, что s S₁ и s S₂³⁾. На рис. 2.4 эти операции проиллюстрированы в интуитивной графической форме. Про операцию взятия декартова произведения уже говорилось выше.

Рис. 2.4. Иллюстрация результатов теоретико-множественных операций

Понятно, что эти операции применимы к любым телам отношений, но результатом не будет являться отношение, если у отношений-операндов не совпадают заголовки. Кодд предложил в качестве средства манипулирования реляционными базами данных специальный набор операций, которые гарантированно производят отношения. Этот набор операций принято называть реляционной алгеброй Кодда, хотя он и не является алгеброй в математическом смысле этого термина, поскольку некоторые бинарные операции этого набора применимы не к произвольным парам отношений.

Характеристики

Список файлов лекций