30510

Определение иерархической и реляционной модели, их достоинства и недостатки. Основные операции реляционной алгебры. Общий процесс преобразования ER-диаграммы в реляционную схему

Доклад

Математика и математический анализ

Пример табличной формы представления отношения Номер зачетной книжки Дисциплина Оценка C12298 Программирование 5 C1229891 Дискретная математика 4 C14407 Программирование 3 . Элементы отношения называют кортежами или записями. Каждый кортеж отношения соответствует одному экземпляру сущности определённого типа. Операции реляционной алгебры ВЫБОРКАНа входе используется одно отношение результат новое отношение построенное по той же схеме содержащее подмножество кортежей исходного отношения удовлетворяющих условию выборки.

Русский

2013-08-24

87.94 KB

9 чел.

42

Определение иерархической и реляционной модели, их достоинства и недостатки.  Основные операции реляционной алгебры. Общий процесс преобразования ER-диаграммы в реляционную схему

  1.  Часть I (доска)

Рис. 1. Пример фрагмента иерархической базы данных

  1.  Часть II (выступление)

Группа

ФИО
студента

Номер
зачетной
книжки

Год
рождения

Размер
стипендии

C-72

Волкова Елена Павловна

С-12298

1991

1550.00

C-91

Белов Сергей Юрьевич

С-12299

1990

1400.00

.....

C-72

Фролов Юрий Вадимович

С-14407

1991

0

Рис. 2. Пример табличной формы представления отношения

Номер зачетной книжки

Дисциплина

Оценка

C-12298

Программирование

5

C-1229891

Дискретная математика

4

C-14407

Программирование

3

.....

Рис. 3. Связь отношений "Оценки" и "Студенты" по внешнему ключу

Табельный
номер

Номер
отдела

ФИО

Должность

Руководитель

002

1

Сухов К.А.

директор

-

034

1

Петрова К.В.

секретарь

002

988

2

Рюмин В.П.

нач. отдела

002

909

2

Серова Т.В.

вед. программист

988

Рис. 4. Внешний ключ "Руководитель", ссылающийся на первичный ключ этой же таблицы

Иерархическая модель данных (ИМД)

Иерархическая модель позволяет строить БД с иерархической древовидной структурой. В основе ИМД лежит понятие дерева.

В иерархических моделях данных используется ориентация древовидной структуры от корня к листьям. Пример иерархической базы данных приведён на рис. 1. Каждая некорневая вершина в ИМД связана с родительской вершиной иерархическим групповым отношением. Тип сущности характеризуется произвольным количеством атрибутов, связанных с ней отношением 1:1. Атрибуты, связанные с сущностью отношением 1:n, образуют отдельную сущность и переносятся на следующий уровень иерархии. Реализация связей типа n:m не поддерживается.

Тип вершины определяется типом сущности и набором её атрибутов. Каждая вершина дерева хранит экземпляры сущностей – записи. Следствием внутренних ограничений иерархической модели является то, что каждому экземпляру зависимой группы в БД соответствует уникальное множество экземпляров родительских записей – по одному экземпляру (записи) каждого типа вершин вышестоящих уровней.

Корневая запись дерева должна содержать ключ с уникальным значением. Ключи некорневых записей должны иметь уникальные значения только в экземплярах групповых отношений, т.е. на одном и том же уровне иерархии в разных ветвях дерева могут быть экземпляры записей с одинаковыми ключами. Это объясняется тем, что каждая запись идентифицируется полным сцепленным ключом, который образуется путём конкатенации всех ключей экземпляров родительских записей. Например, для студента (рис. 1) ключ – это (Шифр_факультета+Номер_курса+Номер_группы+Номер_зачётной_книжки).

Достоинства и недостатки ИМД

Основным недостатком ИМД является дублирование данных. Оно вызвано тем, что каждая сущность (атрибут) может относиться только к одной родительской сущности. Например, если в БД хранятся данные о детях сотрудников, а на предприятии работает и отец, и мать ребёнка, то сведения об этом ребёнке нужно хранить дважды. Аналогичная ситуация возникает, если нужно отразить в БД связь «многие ко многим». Дублирование данных может вызвать нарушение логической целостности БД при внесении изменений в эти данные.

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

Реляционная модель данных (РМД)

Базовой структурой РМД является отношение, основанное на декартовом произведении доменов. Домен – это множество значений, которое может принимать элемент данных (например, множество целых чисел, множество дат, множество комбинаций символов длиной N и т.п.). Домен может задаваться перечислением элементов, указанием диапазона значений, функцией и т.д.

Пусть D1, D2 ,…, Dk – произвольные конечные и не обязательно различные множества (домены). Декартово произведение этих множеств определяется следующим образом:

D1×D2×...×Dk={(d1, d2,...,dk | di  Di, I=1,...,k)}

Таким образом, декартово произведение позволяет получить все возможные комбинации значений элементов исходных множеств.

Пример. Для доменов D1 = (1, 2), D2 = (A, B, C) декартово произведение D = D1×D2будет таким: D = {(1,A), (1,B), (1,C), (2,A), (2,B), (2,C)}

Подмножество декартова произведения доменов называется отношением.

Отношение содержит данные о сущностях определённого типа. Поясним это на примере. Если построить произведение трёх доменов Должности ('директор', 'бухгалтер', 'водитель', 'продавец'), Оклады (x | 20000?x?80000), Надбавки (1.1, 1.2, 1.3), то мы получим 4*60001*3=720012 комбинаций. Но реально отношение «Штатное расписание» содержит по одной строке на каждую должность, т.е. является именно подмножеством декартова произведения доменов.

Элементы отношения называют кортежами (или записями). Каждый кортеж отношения соответствует одному экземпляру сущности определённого типа. Элементы кортежа принято называть атрибутами (или полями).

Достоинства и недостатки РМД

Простота представления и формирования базы данных, универсальностью и удобством обработки данных, посредством языка SQL.

Моделирование предметной области в рамках реляционной модели создаёт некоторые сложности, т. к. в этой модели нет специальных средств для отображения различных типов связей и агрегатов. Отсутствие агрегатов приводит к тому, что при проектировании реляционной БД приходится проводить нормализацию отношений. После нормализации данные об одной сущности предметной области распределяются по нескольким таблицам, что усложняет работу с БД.

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

Операции реляционной алгебры

ВЫБОРКА
На входе используется одно отношение, результат - новое отношение, построенное по той же схеме, содержащее подмножество кортежей исходного отношения, удовлетворяющих условию выборки.

 

ОБЪЕДИНЕНИЕ

Отношения-операнды в этом случае должны быть определены по одной схеме. Результирующее отношение содержит все строки операндов за исключением повторяющихся.

 

ПЕРЕСЕЧЕНИЕ
На входе операции два отношения,  определенные по одной схеме. На выходе - отношение, содержащие кортежи, которые присутствуют в обоих исходных отношениях.

   

СОЕДИНЕНИЕ
Данная операция имеет сходство с ДЕКАРТОВЫМ ПРОИЗВЕДЕНИЕМ. Однако, здесь добавлено условие, согласно которому вместо полного произведения всех строк в результирующее отношение включаются только строки, удовлетворяющие определенному соотношению между атрибутами соединения 
1,A2) соответствующих отношений.

Получение реляционной схемы из ER-диаграммы

Существуют два способа формирования схемы реляционной БД при наличии взаимно исключающих связей (имеются в виду связи «один ко многим», причем конец связи «многие» находится на стороне сущности, для которой связи являются взаимно исключающими):

  1. (a) общее хранение внешних ключей;
  2. (b) раздельное хранение внешних ключей.

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

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

Преимущество подхода (a) состоит в том, что в таблице, соответствующей сущности, появляется всего два дополнительных столбца. Очевидным недостатком является усложнение выполнения операции соединения: чтобы воспользоваться для соединения одной из альтернативных связей, нужно сначала произвести ограничение таблицы в соответствии с нужным значением столбца, содержащего идентификаторы связей.

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

 
Рис. 10.14.  Возможные модификации ER-диаграмм, позволяющие избежать взаимно исключающих связей

Модификация, показанная на рис. 10.14 (b), основана на том наблюдении, что коль скоро связи являются альтернативными, то они разделяют множество экземпляров сущности  A на два или более непересекающихся подмножества, которые могут лежать в основе определения подтипов  A1 и A2. Это хороший вариант, если такие подтипы могут пригодиться еще для чего-нибудь. Например, в случае взаимно исключающей связи, представленной на рис. 10.12, у исправных и неисправных самолетов могут имется несовпадающие множества атрибутов (скажем, у типа сущности  ИСПРАВНЫЕ САМОЛЕТЫ может иметься атрибут  дата завершения гарантийного срока, а у типа сущности  НЕИСПРАВНЫЕ САМОЛЕТЫ – атрибут  тип неисправности). С другой стороны, как отмечалось в предыдущем разделе, для использования этого подхода требуется возможность динамического изменения типа существующего экземпляра.

Модификация, показанная на рис. 10.14 (с), основана на том наблюдении, что коль скоро типы сущности B и C участвуют в альтернативной связи, то, по всей видимости, у этих сущностей имеется что-то общее. Возможно, их было бы правильнее определять как подтипы некоторого общего типа сущности. Заметим, что пример с рис. 10.12 явно демонстрирует, что далеко не всегда типы сущности, участвующие в альтернативной связи, обладают общими чертами.

 

  1.  Часть III (дополнительно)

Свойства отношений

Отношение обладает двумя основными свойствами:

  1.  В отношении не должно быть одинаковых кортежей, т.к. это множество.
  2.  Порядок кортежей в отношении несущественен.

Таким образом, в отношении не бывает первого, второго или последнего кортежа: при выводе данных отношения кортежи выводятся в произвольном порядке, если не задано упорядочение по значениям полей.

Отношение удобно представлять как таблицу, где строка является кортежем, а столбец соответствует домену (рис. 2, отношение СТУДЕНТЫ). Количество строк в таблице (кортежей в отношении) называется мощностью отношения, количество столбцов (атрибутов) – арностью.

Отношение имеет имя, которое отличает его от имён всех других отношений. Атрибутам реляционного отношения назначаются имена, уникальные в рамках отношения. Обращение к отношению происходит по его имени, а обращение к атрибуту – по имени отношения и имени атрибута.

Каждый атрибут определён на некотором домене, несколько атрибутов отношения могут быть определены на одном и том же домене (например, номера рабочего и домашнего телефонов). Домен задаётся типом данных, размером и ограничениями целостности: например, пол – это символьное поле длиной 1, которое может принимать значения из множества ('м', 'ж').

Перечень атрибутов отношения с их типами данных и размерами определяют схему отношения. Отношения, построенные по одинаковой схеме, называют односхемными; по различным схемам – разносхемными.

Ключ отношения – это атрибут (группа атрибутов), значения которого классифицируют или идентифицируют кортеж. Например, значение атрибута Группа отношения СТУДЕНТЫ позволяет выделить среди всех студентов института студентов конкретной группы. Если ключ состоит из нескольких атрибутов, он называется составным. Если значения ключа уникальны в рамках столбца отношения, то такой ключ называетсяпотенциальным. Потенциальных ключей может быть несколько (или не быть ни одного), но для отношения выделяется один основной ключ – первичный. Первичный ключи дентифицирует экземпляр сущности, его значение должно быть уникальным (unique) и обязательным (not null). (На рис. 2 первичный ключ выделен полужирным шрифтом). Неуникальные ключи ещё называют вторичными.

РМД не поддерживает групповые отношения (по версии CODASYL). Для связей между отношениями используются внешние ключи. Внешний ключ (foreign key) – это атрибут подчинённого (дочернего) отношения, который является копией первичного (primary key) или уникального (unique) ключа родительского отношения. (Пример – отношение ОЦЕНКИ, связанное с отношением СТУДЕНТЫ внешним ключом Номер зачётной книжки, рис. 3).

Фактически внешние ключи логически связывают экземпляры сущностей разных типов (родительской и подчинённой сущностей).

Подмножество декартова произведения доменов называется отношением.

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

Ограничение целостности по внешнему ключу проверяется в двух случаях:

  1.  при добавлении записи в подчинённую таблицу СУБД проверяет, что в родительской таблице есть запись с таким же значением первичного ключа;
  2.  при удалении записи из родительской таблицы СУБД проверяет, что в подчинённой таблице нет записей с таким же значением внешнего ключа.

Примечание: внешний ключ может ссылаться на первичный ключ этой же таблицы. Это позволяет описывать унарную связь – иерархию однотипных сущностей. Например, если в таблицу СОТРУДНИКИ добавить поле Руководитель и описать его как внешний ключ на эту же таблицу, то в этом поле будет храниться идентификатор руководителя данного сотрудника (рис. 2.9). Атрибут Руководитель является необязательным.

Все операции над данными в РМД выполняются над отношением и требуют задания имени отношения. Если операция применяется к части отношения, то может потребоваться идентификация кортежа или группы кортежей и задание имён атрибутов. В РМД используются следующие операции:

  1.  запомнить: внесение информации в БД (требует формирования значений уникального ключа и обязательных атрибутов кортежа);
  2.  извлечь: чтение данных;
  3.  обновить: модификация данных – изменение значений атрибутов кортежей;
  4.  удалить: физическое или логическое удаление данных (кортежей).

ПРОЕКЦИЯ (ВЕРТИКАЛЬНОЕ ПОДМНОЖЕСТВО)

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

РАЗНОСТЬ

Операция во многом похожая на ПЕРЕСЕЧЕНИЕ, за исключением того, что в результирующем отношении содержатся кортежи, присутствующие в первом и отсутствующие во втором исходных отношениях.

ДЕКАРТОВО ПРОИЗВЕДЕНИЕ
Входные отношения могут быть определены по разным схемам. Схема результирующего отношения включает все атрибуты исходных. Кроме того:

  1.  степень результирующего отношения равна сумме степеней исходных отношений
  2.  мощность результирующего отношения равна произведению мощностей исходных отношений.

 

ДЕЛЕНИЕ

Пусть отношение R , называемое делимым, содержит атрибуты (A1,A2,...,An). Отношение S - делитель содержит подмножество атрибутов A(A1,A2,...,Ak) (k<n). Результирующее отношение C определено на атрибутах отношения R, которых нет в S, т.е. Ak+1,Ak+2,...,An. Кортежи включаются в результирующее отношение C только в том случае, если его декартово произведение с отношением S содержится в делимом R.


 

А также другие работы, которые могут Вас заинтересовать

81201. История формирования иудаизма 26.17 KB
  Выделяют различные периоды формирования и развития иудаизма. Возникновение иудаизма как религии принято связывать с именем Моисея получивший на горе Синай через Откровение десять заповедей образовавших основу монотеизма и религиозной этики. формируются основные черты иудаизма: строгий монотеизм централизация культа канонизация священных книг появлению веры в сверхъестественную помощь для освобождения от угнетателей и веры в избавителямессию.
81202. Догматы и культ иудаизма 26.33 KB
  Центральная доктрина иудаизма вера в единого Бога который бессмертен вечен всемогущ вездесущ и безграничен. В соответствии с нормами иудаизма верующий поддерживает связь с Богом через молитву а божья воля открывается человеку через Танах.
81203. Структура Ветхого завета в иудаизме 22.12 KB
  Книги Ветхого Завета были написаны в период с XIII по I в. Ветхий Завет состоит из следующих книг: 1 Книги закона Тора Учение или Пятикнижие Моисеево составление книг приписывается Моисею: Бытие сотворение мира и человека рай первые люди грехопадение размножение человечества всемирный потоп Ной патриархи родоначальники еврейского народа Авраам Исаак Иаков Иосиф с братьями поселение евреев в Египте; Исход Моисей 10 заповедей освобождение из плена; Левит религиозное законодательство; Числа законодательство и...
81204. Формирование ислама. Жизнь и деятельность Мухаммеда 25.03 KB
  Жизнь и деятельность Мухаммеда. Политическое и религиозное движение возглавил пророк Мухаммед. Мухаммед родился в 570 г. Мать Амина по обычаю мекканцев отдала Мухаммеда кормилицебедуинке у которой он рос до 5 лет.
81205. Вероучение ислама 24.39 KB
  Иман или вера включает: Веру в Единого Бога Аллаха. Веру в Ангелов и демонов. 3Веру в Святые Писания и в святость Корана который считается словом божьим божественным откровением которое передавал Аллах в виде видений Мухаммеду в течение 22 лет т. 4Веру в Пророков и в посланничество Мухаммеда.
81206. Коран – священная книга ислама 24.8 KB
  Главным источником веры является Коран священная книга мусульман состоящая из притч молитв и проповедей Мухаммеда. спустя почти два десятилетия после смерти пророка был составлен свод Коран чтение другие названия: китаб книга зикр предостережение . Святость Корана обусловлена тем что изречения пророку диктовал архангел Джебраил на протяжении 22 лет доносивший слова самого БогаАллаха. эти откровения составили канонический текст Корана который дошел до наших дней в неизменном виде.
81207. Основные направления в исламе 24.66 KB
  В результате внутренних противоречий в VII веке возникли два направления: сунниты и шииты. Последователи суннизма признавали законность власти первых четырех халифов а шииты считали единственным законным главой мусульман четвертого халифа Али ум. Шииты поклоняются этому имаму и верят что перед Страшным Судом явится махди для установления на земле равенства и справедливости. Шииты как и сунниты признают святость Корана а в Сунне признают лишь те хадисы авторами которых являются четвертый халиф Али и его последователи.
81208. Пять столпов ислама 24.1 KB
  Саум пост. Мусульманский пост заключается в воздержании от пищи питья наслаждения и развлечений. Главным и обязательным для всех кроме больных путешествующих военных и беременных является пост в месяц рамадан; кроме того существует еще дата в которой поститься желательно. Уразабайрам праздник разговенья окончания поста.
81209. Основные идеи шариата. Понятие джихада 26.17 KB
  Понятие джихада. Джихад с точки зрения шариата является общим понятием путей и методов достижения деяний высказываний и убеждений любимых и одобряемых Всевышним Аллахом а также отражения деяний высказываний и убеждений порицаемых и ненавистных Пречистому Аллаху. Ибн альКаййим: Джихад подразделяется на четыре уровня: джихад против самого себя джихад против шайтана джихад против неверующих и лицемеров и джихад против приверженцев несправедливости нововведений и порицаемых действий. Джихад против самого себя также имеет четыре уровня:...