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.


 

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

804. Теория и особенности познания 235.5 KB
  Познание как предмет философского анализа. Структура знания. Чувственное и рациональное познание. Теория истины. Понятие как основная форма рационального познания.
805. Экоинформационные системы как инструмент комплексного маниторинга окружающей среды 284.5 KB
  История возникновения экоинформатики. Задачи решаемые экоинформационной системой. Информационное обеспечение подготовки и принятия управленческих решений по охране природы и здоровья человека. Обмен информации о состоянии окружающей среды об других экоинформационных системах.
806. Радиальная скорость 234.5 KB
  Несущая частота сигнала наземного передающего пункта. Релятивистские частотно-фазовые соотношения между параметрами сигналов. Геоцентрические радиус-векторы передающего пункта, космического аппарата и приемного пункта .
807. Зоогигиена с проектированием и строительством животноводческой фермы 230.5 KB
  Роль конструктивных решений животноводческих помещений в формировании оптимального микроклимата и комфортных условий для животных. Характеристика площадки для строительства. Состав основных производственных зданий. Взаимное расположение построек на участке.
808. Исследование линейного четырехполюсника 222.5 KB
  Измерение Z-параметров линейного пассивного четырехполюсника и экспериментальные исследования по косвенной проверке результатов измерений. Схема подключения приборов для измерения параметров Z21 и Z12.
809. Проектирование механического привода конвейера для транспортирования сухих сыпучих материалов 182 KB
  Определение мощности и выбор электродвигателя. Определение общего передаточного отношения привода и разбивка передаточного числа редуктора по ступеням. Определение вращающих моментов на валах редуктора. Проверочный расчет передач на контактную прочность. Уточненный расчет промежуточного вала.
810. ППП Евфрат 231.5 KB
  Удобный инструмент для адаптирования системы конкретно под нужды и структуры организации, позволяет создать полный маршрут движения определенного типа документа, что в процессе работы позволяет экономить время и ресуры, затрачиваемые на обработку документа.
811. Сравнительный анализ требований зарубежных (национальных) и отечественных нормативных и технических документов 300.5 KB
  Сравнительный анализ методов контроля обсадных труб по ГОСТ 632-80, документам API. Попробуем сравнить российские национальные стандарты со стандартами Американского института нефти (API) на примере стандартов API 5CT/ISO 11960:2001 и ГОСТ 632-80.
812. База данных 250.5 KB
  Совокупность сведений о реальных объектах, процессах, событиях или явлениях, относящихся к определённой теме или задаче. Создание базы данных Продажи книг. Описание структуры базы данных, обработка данных и управление данными.