17223

ОРГАНИЗАЦИЯ СЕТЕВЫХ И ИЕРАРХИЧЕСКИХ МОДЕЛЕЙ ДАННЫХ

Лекция

Информатика, кибернетика и программирование

Лекция №2 Организация сетевых и иерархических моделей данных Практика построения БД выделяет три основных модели данных: иерархическую сетевую и реляционную. Основное отличие формирование моделей данных заключается в выборе типа отношения R и соответственно оп

Русский

2013-06-30

96.5 KB

0 чел.

Лекция №2

Организация сетевых и иерархических моделей данных

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

Организация данных в моделях сетевого и иерархического типа определяется в терминах: элемент данных, запись (агрегат), групповое отношение, база данных. 

  •  Атрибут (элемент данных) - наименьшая единица структуры данных. Каждому элементу при описании БД присваивается уникальное имя.
  •  Запись - именованная совокупность атрибутов. Использование записей позволяет за одно обращение к базе получить некоторую логически связанную совокупность данных. Именно записи изменяются, добавляются и удаляются. Тип записи определяется составом ее атрибутов.
  •  Групповое отношение - иерархическое отношение между записями двух типов. Владелец группового отношения называется исходной записью, а члены группового отношения - подчиненными.
  •  База данных – совокупность записей и групповых отношений, связанных ассоциациями (связями) различного вида.

Например.

Для описания данных используются либо структуры данных разработанные рабочими группами по языкам БД, такими как CODASYL (сетевые структуры) или IMS (иерархические структуры). На современном этапе развития языков программирования можно использовать такие структуры как записи, наследование в объектно-ориентированной технологии программирования, технология описания данных XML и др.

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

Недостатки – сложность реализации, индивидуальный подход для каждой структуры БД.

Реляционная модель данных

Устно. В конце 60-х годов появились работы, в которых обсуждались возможности применения различных табличных моделей данных, т.е. возможности использования привычных и естественных способов представления данных. Наиболее значительной из них была статья сотрудника фирмы IBM д-ра Э.Кодда где, вероятно, впервые был применен термин "реляционная модель данных" (РМД). 

В статье автора РМД (Е.Ф.Кодд) утверждается, что "реляционная модель предоставляет средства описания данных на основе их естественной структуры, т.е. без потребности введения какой-либо дополнительной структуры для машинного представления". Другими словами, представление данных в РМД не зависит от способа их физической организации. Это обеспечивается за счет использования теории множеств и отношений (само название "реляционная" происходит от английского relation - "отношение").

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

Декартово произведение: Для заданных конечных множеств (не обязательно различных) декартовым произведением называется множество произведений вида: , где

Пример: если даны два множества A={a1,a2,a3} и B={b1,b2}, их декартово произведение будет иметь вид С=AB={<a1,b1>, <a2,b1>, <a3,b1>, <a1,b2>,< a2,b2>,< a3,b2>} 

Отношение: Отношением R, определенным на множествах  называется подмножество декартова произведения ,

то есть R  D1D2Dn.

Пример: на множестве С из предыдущего примера могут быть определены отношения R1= {<a1,b1>,<a3,b2>} или R2 = {<a1,b1>, <a2,b1>, <a1,b2>).

Множества  называются доменами. Домен это множество однотипных семантически однозначных (одинаковых по смыслу) значений элемента данных.

Элементы декартова произведения называются кортежами, число n определяет степень отношения (n=1 - унарное, n=2 - бинарное, ..., n-арное), количество кортежей определяет мощностью отношения.

Пусть a = {a1,…,an} – множество имен доменов, тогда если задать отображение вида

dom : ai  Di,

то пары Ai = <ai, dom ai> называют атрибутами отношения, где dom ai – сокращенная запись dom : a  D.

Схемой отношения R будем называть выражение (A1,…An) в котором все атрибуты Ai различны. При этом экземпляр отношения определяется, как подмножество декартова произведения доменов

ri  dom ai  dom an

Отношений ri со схемой Ri будем обозначать как Ri(ri) (для простоты обозначений в дальнейшем отношений будем обозначать Ri). Отмети, что перестановка атрибутов в схеме не порождает нового состояния БД. Таким образом, множество атрибутов {A1,…,An} задает тип отношения и определяет его свойства.

Схему БД будем обозначать как множество схем отношений

U = {R1,…, Rn}

где Ri  R и все Ri различны. Соответственно экземпляр БД будем обозначать множество экземпляров отношений U(r1,…,rn).

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

Объекты определённого типа обладают вполне определённым набором свойств (задаётся схемой отношения), а свойства имеют вполне определённые наборы возможных значений (задаётся отображением dom).

В простейшем случае можно предположить, что схема U задаёт набор объектов, без их взаимосвязи, а целостность определяется тем, что БД используется для решения одной прикладной задачи.

Очевидно, такой подход является неэффективным и даже неадекватным целям моделирования ПрО. (Следует из того, что между объектами ПрО могут существовать отношения подчиненности, отношения "часть-целое" и другие, необходимые для описания поведения ПрО). С другой стороны, некоторые отношения, в целях повышения эффективности хранения данных, целесообразно реструктуризировать, представляя их наборами взаимосвязанных отношений БД.

Ключи отношений

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

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

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

  1.  Свойством уникальности - в отношении не может быть двух различных кортежей, с одинаковым значением .
  2.  Свойством неизбыточности (минимальности) - никакое подмножество в  не обладает свойством уникальности.

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

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

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

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

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

Устно. Понятие потенциального ключа является семантическим понятием и отражает некоторый смысл понятий из конкретной ПрО. Для того чтобы проиллюстрировать этот факт рассмотрим следующее отношение "Сотрудники":

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

Фамилия

Зарплата

1

Иванов

1000

2

Петров

2000

3

Сидоров

3000

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

Попробуем представить это отношение в другом виде, изменив наименования атрибутов:

A

B

C

1

Иванов

1000

2

Петров

2000

3

Сидоров

3000

Очевидно, что невозможно судить, не понимая смысла данных, может или не может в этом отношении появиться, например, кортеж (1, Петров, 3000). Если бы, такой кортеж появился (что, на первый взгляд, вполне возможно, т.к. не нарушается уникальность кортежей), то мы точно смогли бы сказать, что не является альтернативным ключом - ни один из атрибутов по отдельности.

Целостность данных

Требование целостности отношений заключается в следующем:

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

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

Поддержка целостности отношений обеспечивается средствами СУБД.

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

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

Требование ссылочной целостности заключается в следующем:

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

Дадим точное определение.

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

  1.  Существует отношение ( и не обязательно различны) с потенциальным ключом .
  2.  Каждое значение в отношении  всегда совпадает со значением для некоторого кортежа из , либо является null-значением.

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

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

Если внешний ключ все-таки обладает свойством уникальности, то связь между отношениями имеет тип "один-к-одному". Чаще всего такие отношения объединяются в одно отношение.

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

Для внешнего ключа не требуется, чтобы он был компонентом некоторого потенциального ключа.

Null-значения для атрибутов внешнего ключа допустимы только в том случае, когда атрибуты внешнего ключа не входят в состав никакого потенциального ключа

Контроль за правильностью заполнения значений внешнего ключа возлагается на СУБД.


 

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

21316. Юридические вопросы информационной безопасности 202.5 KB
  Независимо от способа совершения компьютерного преступления его исполнители должны быть наказаны и профессионалы работающие в сфере информационной безопасности должны уметь собирать информацию необходимую правоохранительным органам при задержании и вынесении приговора лицам несущим ответственность за это преступление. В новом законодательстве нашли отражение вопросы безопасности финансовой информации о клиентах и конфиденциальности сведений медицинского характера. Все эти проблемы требуют понимания и изучения профессионалами работающими...
21317. Состав текущих затрат, сформированный в зависимости от производственно-хозяйственных целей предприятия РГБ 195.5 KB
  Все затраты на производство и реализацию продукции (работ, услуг) должны быть документально обоснованы и иметь исключительно целевое назначение. Поскольку издержки производства и обращения являются главной составляющей при расчете прибыли организации, они участвуют в расчете налогооблагаемой прибыли...
21318. Категории атак на информацию 317.5 KB
  Существуют четыре основных категории атак: атаки доступа; атаки модификации; атаки на отказ в обслуживании; атаки на отказ от обязательств. Атаки такого рода наиболее разрушительны. Атаки нацеленные на захват информации хранящейся в электронном виде имеют одну интересную особенность: информация не похищается а копируется. Определение атаки доступа Атака доступа это попытка получения злоумышленником информации для просмотра которой у него нет разрешений.
21319. Предмет і завдання екології. Місце екології у системі інших наук. Значення екології для людської цивілізації. Глобальні проблеми екології 56 KB
  З розвитком виробництва очевидною стає обмеженість традиційно використовуваних природних багатств суші, тому в наш час перспективи розвитку виробництва все в більшій мірі звязують з використанням ресурсів Світового океану та космічного простору. Тому можна сказати, що в наш час екологічні проблеми поширилися навіть за межі Землі.
21320. Безопасность сетей 113.46 KB
  Обеспечение безопасности сетей представляет собой сумму мероприятий направленных на предотвращение несанкционированного доступа к ресурсам сети а именно: Безопасность входа в систему Безопасность доступа к файловой системе Безопасность передачи данных по сети Физическая защита оборудования и помещений. Следует отметить что доступ к сети вообще говоря не означает полного доступа ко всем ресурсам. Поэтому в решении этой задачи предусмотрены как средства аутентификации пользователя так и средства описывающие права доступа к различным...
21321. Виртуальная частная сеть. Концепция построения виртуальных частных сетей VPN 161.96 KB
  Концепция построения виртуальных частных сетей VPN. Виртуальной частной сетью Virtual Private Network VPN называют объединение локальных сетей через открытую внешнюю среду глобальную сеть в единую корпоративную сеть обеспечивающую безопасное циркулирование данных. Объединение осуществляется на основе создания туннеля VPN в глобальной сети по которому передаются криптографически защищенные пакеты сообщений. Безопасность использования туннеля основана на взаимной аутентификации сторон криптографическом закрытии передаваемых данных...
21322. Жестовые методики ввода информации в интерактивных системах компьютерной визуализации 41 KB
  Трёхмерность, особенно в случае использования средств виртуальной реальности или “больших” экранов (то есть экранов, диагональ которых измеряется метрами, а количество пикселей – десятками миллионов) требует и новые средства ввода и связанные с ними новые пользовательские интерфейсы
21324. Криптографическая защита информации 144.5 KB
  Кpиптоанализ исследование возможности расшифровывания информации без знания ключей.Шеннона Теория связи в секретных системах стала началом новой эры научной криптологии с секретными ключами. Классификация криптографических систем Тайнопись Криптография с ключом Симметричные криптоалгоритмы Шифры перестановки Шифры замены подстановки Простой замены Сложной замены Сложные составные шифры Асимметричные криптоалгоритмы Комбинированные гибридные криптосистемы Тайнопись Отправитель и получатель производят над сообщением...