какие существуют модели представления данных a линейная b иерархическая c сетевая d реляционная

Иерархические, сетевые и реляционные модели данных.

Дата добавления: 2013-12-23 ; просмотров: 25670 ; Нарушение авторских прав

Базы данных.

Лекция №12.

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

Система управления базами данных (СУБД) – система, обеспечивающая ввод данных в БД, их хранение и восстановление в случае сбоев, манипулирование данными, поиск и вывод данных по запросу пользователя.

По моделям представления, базы данных делятся на:

Иерархические базы данных – это самая первая модель представления данных, в которой все записи базы данных представлены в виде дерева, с соотношением предок-потомок (рис. 30).

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

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

Рис. 30. Иерархическая база данных.

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

Рис. 31. Сетевая база данных.

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

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

В реляционной базе данных вся информации представляется в виде таблиц, и любые операции над данными – это операции над таблицами. Таблицы строят из строк и столбцов. Строки – это записи, а столбцы представляют собой структуру записи (каждый столбец имеет определенный тип данных и длину данных). Строки в таблице не упорядочены – не существует первой или десятой строки. Однако поскольку на строки необходимо как-то ссылаться, то вводится понятие «первичный ключ».

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

Некоторые СУБД требуют в явном виде указать первичный ключ таблицы, а некоторые позволяют пользователю не задавать для таблицы первичный ключ – в таком случае СУБД сама добавляет в таблицу столбец – первичный ключ, не отображаемый на экране (так, например, в СУБД Oracle у любой таблицы существует псевдо-столбец ROWID, формируемый Oracle, который содержит уникальный адрес каждой строки). Отношения предок-потомок в реляционных БД реализуются при помощи внешних ключей.

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

Так, например, на рис. 32 столбец «Ответственный» таблицы «Мероприятия» является внешним ключом для таблицы «Сотрудники» (первичный ключ – столбец «Фамилия»).

Рис. 32. Отношения предок-потомок в реляционных базах данных.

Важным моментом является также использование значения NULL в таблицах реляционной базе данных. NULL – это отсутствующее значение, отсутствие информации по данной позиции. Не допускается использование 0 или пробела вместо NULL: понятно, что «нулевой» объем продаж – это не тоже самое, что «неизвестный» объем продаж. По этой же причине, ни одно значение NULL не равно другому значению NULL. В реляционной базе данных, при запросах, группировке, сравнениях, и т.д., значения NULL обрабатываются особым образом.

Объектно-реляционные базы данных появились в последнее время у значительного числа производителей СУБД (Oracle, Informix, PostgreSQL) и сочетают в себе реляционную модель данных с концепциями объектно-ориентированного программирования (полиморфизм, инкапсуляция, наследование).

Источник

Какие существуют модели представления данных a линейная b иерархическая c сетевая d реляционная

Ядром любой базы данных является модель данных. С помощью модели данных могут быть представлены объекты предметной области и взаимосвязи между ними.

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

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

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

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

Каждая реляционная таблица представляет собой двумерный массив и обладает следующими свойствами:

1. Каждый элемент таблицы соответствует одному элементу данных.

2. Все столбцы в таблице однородные, т.е. все элементы в столбце имеют одинаковый тип и длину.

3. Каждый столбец имеет уникальное имя.

4. Одинаковые строки в таблице отсутствуют;

5. Порядок следования строк и столбцов может быть произвольным.

Источник

Модели данных: иерархическая, сетевая, реляционная.

Иерархическая модель.

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

В терминологии иерархической моде­ли используются более конкретные понятия: «элемент» (узел); «уро­вень» и «связь». Узел чаще всего представляет собой атрибут (при­знак), описывающий некоторый объект.

Эта модель представляет собой совокупность элементов, расположенных в порядке их подчинения от общего к частному и образующих граф – дерево с иерархической структу­рой (рисунок 2,3).

Такой граф имеет единственную вершину, не под­чиненную никакой другой вершине и находящуюся на самом верх­нем (первом) уровне. Число вершин первого уровня определяет число деревьев в базе данных. Запрещены взаимосвязи на одном уровне.

Рисунок 3 – Пример иерархической модели данных

Сетевая модель.

Сетевая модель более демократична. В сетевой модели отсутству­ет понятие главного и подчиненного объекта (рисунок 4,5). Один и тот же объект может выступать как главный и как подчиненный, то есть иметь любое количество взаимосвязей. Здесь допустимы связи на одном уровне. Эта модель использует ту же термино­логию, что и иерархическая модель: «узел», «уровень» и «связь».

Как известно из теории графов, сетевой граф мо­жет быть преобразован в граф-дерево.

Рисунок 5 – Пример сетевой модели данных

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

Реляционная алгебра Процедурный язык обработки реляционных таблиц.

Реляционное исчисление Непроцедурный язык создания запросов.

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

Существует два подхода к проектированию реляционной базы данных.

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

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

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

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

Таблица 1 – Структура реляционной таблицы

Рассмотрим пример реляционной модели данных (таблица 2).

На рисунке 6 показано разделение таблицы 2 на две связанные таблицы.

Реляционные модели данных, или реляционные базы данных, являются в настоящее время основным способом в проектировании и организации информационных систем в производстве и бизнесе.

Источник

Основные модели данных: иерархическая, сетевая, реляционная

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

Иерархическая модель

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

Продукт IMS (Information Management System) фирмы IBM, считающийся первой промышленной СУБД, реализует именно иерархическую модель.

Разработанная в 1966 году, эта СУБД до сих пор эксплуатируется на новейших мэйнфреймах серии Z, обеспечивая высокую производительность обработки порядка сотни тысяч транзакций в секунду.

Современной массово доступной каждому программисту реализацией иерархической модели данных является XML, точнее, разнообразные

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

Последний пункт важен: без использования XML-схемы (XML schema) или описания типов DTD (Data Type Definition) документ XML относится к неполно структурированным моделям данных, рассматриваемым в следующей главе.

Если взглянуть на структуру XML-документа, то иерархия элементов данных становится видна, что называется, невооружённым глазом.

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

Преимуществом такой структуры является возможность выполнения поисковых запросов без соединений. Например, чтобы выбрать все заказы клиента «Пирожки ООО», в которых он покупал муку в количестве более 50 кг, язык XPath [1] позволяет сделать в программе следующее:

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

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

Частично, эта проблема решается введением ссылок на элементы XML- документа.

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

На XML-документах небольшого размера с сотнями элементов подобные запросы выполняются быстро, но с ростом объёма данных неизбежно возникает необходимость их индексировать. В СУБД, поддерживающих XML хотя бы на уровне типа данных колонки таблицы, имеется возможность такой индексации. Например, в MS SQL Server вначале строится так называемый первичный XML-индекс, затем несколько вторичных, для которых нужно указывать их специализацию: PATH для запросов типа проверки

существования элементов, PROPERTY — для извлечения значений элементов и атрибутов или VALUE — для сквозного поиска элементов по значению. Без достаточного понимания таких особенностей физической организации данных хранилище XML начнёт испытывать проблемы с производительностью уже на небольших объёмах.

Кроме XML и поддерживающих его СУБД существуют и другие реализации. Наиболее известная отечественная разработка — СУБД ИНЕС, являвшаяся фактически стандартом на советских ЭВМ серии ЕС. К сожалению, эволюция системы прервалась вместе с прекращением выпуска своих ЭВМ, до наших дней этот продукт не дожил.

К иерархическим также можно отнести СУБД на базе подхода MUMPS [2] (в СССР назывался «ДИАМС»), лежащий в основе линейки продуктов InterSystems: от выпущенной в 1970-х годах СУБД ISM (InterSystem M), через OpenM периода 1980-х к СУБД Cache с конца 1990-х и по наше время, реализующей современные подходы к организации иерархий.

Так, например, в MUMPS можно обращаться к значениям полей:

Здесь сущность «Автомобиль» представлена в виде дерева, одним из верхних узлов которого является элемент «Корпус», в состав которого, в свою очередь, входит «Дверь», имеющая пока ещё листовой узел «Цвет».

Иерархию несложно динамически расширять как в ширину:

Общий принцип распознавания лежащей в основе СУБД иерархической модели можно сформулировать так.

Если при использовании входного языка и/или API наиболее низкого уровня из доступных программисту для доступа к данным (значениям узлов, переменных, полей и т д.) требуется указывать некоторый путь, то лежащая в основе СУБД модель базируется на иерархиях.

Иерархическая модель: плюсы и минусы

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

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

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

Сетевая модель

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

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

В 1975 году конференция CODASYL (Conference of Data System Languages) стандартизовала базовые понятия и формальный язык описания. Широко известной системой, основанной на сетевой модели данных, являлась СУБД IDMS (Integrated Database Management System), использовавшаяся на мэйнфреймах IBM. В настоящее время IDMS принадлежит компании Computer Associates, имеющей неформальный статус «лавки старьёвщика» в мире софтостроения: как правило, все купленные компанией продукты берутся на сопровождение, но не развиваются, доживая до своего естественного конца.

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

СУБД Raima изначально использовалась, как встроенная с достаточно низкоуровневым API для языка Си. Постепенно, в систему был добавлен интерфейс доступа на SQL, а сама СУБД получила возможность работы в режиме клиент-сервер. По-прежнему Raima используется для транзакционных приложений как лёгкое (lightweight) кросс-платформенное решение.

Напротив, развитие СУБД Кронос пошло в сторону аналитической обработки. Это та область, где преимущества сетевой модели могут быть использованы полнее, а недостатки обойдены более просто. Для объяснений нам все же придётся кратко познакомиться с основными понятиями сетевой модели.

Термин запись соответствует аналогичному понятию структурного типа в традиционных языках программирования: record в Паскаль-подобных или struct в наследниках Си.

Набор данных служит для связывания двух типов записей отношением «один-ко-многим».

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

В СУБД Кронос также реализовано объединение наборов, позволяющее одной записи ссылаться на записи двух и более типов. Такая возможность очень удобна при моделировании. Например, если имеется тип записи «Адрес», который используется записями «Лица» и «Организации», то объединённый набор «Относится к лицу или организации» отобразит все возможные связи.

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

Поясню на упрощённом примере. Связь между двумя таблицами в реляционной модели осуществляется по значениям, соответственно, первичного и внешних ключей. Для выбранной строки подчинённой таблицы берётся значение внешнего ключа, которое затем ищется среди значений первичного ключа главной таблицы. Если таблица отсортирована в физическом порядке следования значений первичного ключа (так называемый кластерный ключ, подробнее см. «Физическая организация памяти»), то строка данных находится в той же области памяти, что и найденное значение. Если нет, то происходит дополнительный поиск связанной со значением первичного ключа строки по её идентификатору (row id).

Рис. 1. Организация связей между типами записей в сетевой модели

В случае сетевой модели запись одного типа имеет одну или несколько ссылок на записи другого типа; по этой ссылке непосредственно извлекается связанная запись.

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

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

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

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

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

Сетевая модель: плюсы и минусы

К преимуществам сетевой модели можно отнести следующие особенности:

О недостатках уже было упомянуто:

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

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

Как и положено доминирующей на протяжении десятков лет массово внедрённой парадигме, реляционная модель имеет свой основополагающий миф. Речь, конечно, идёт об известной работе Эдгара Кодда «Реляционная модель данных для больших совместно используемых банков данных», опубликованной в CACM [3] в 1970 году. «Да будет свет!» — сказал Кодд, и появился свет, и начали рождаться реляционные СУБД.

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

Кроме того, Кодд начал свои публикации раньше, в 1969 году, исследовательским отчётом «Derivability, Redundency, and Consistency of Relations Stored in Large Data Banks» в среде ограниченного круга подписчиков. В дальнейшем концепция эволюционировала, известный эксперт в области СУБД Майкл Стоунбрейкер отмечал, что «можно видеть четыре разных версии» модели:

версия 2, определена в статье по поводу Тьюринговской премии в 1981 г.;

Из сказанного Стоунбрейкером становится понятным, что Кодд, как и положено учёному, в течение десятилетий продолжал исследования, пересматривая свои подходы и концепции. И полнота реализации теории в промышленных СУБД волновала её автора в меньшей степени, потому что «дюжина Кодда» до сих пор является актуальной для оценки соответствия, а последние стандарты SQL полностью не реализованы ни в одном продукте.

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

Реляционная модель, как и другая, более известная программистам — объектная, относится к логическим. Определённые в рамках модели структуры, операции над ними и задаваемые ограничения не зависят от способов реализации физической организации данных и управления ими. Тем не менее, каждая СУБД имеет свои особенности физической организации, поэтому одна и та же схема данных в рамках реляционной модели может иметь специфические параметры и опции, оптимизирующие работу с данными. Например, соответствующая понятию «отношение» таблица может быть организована в виде кластера, сегмента памяти (кучи), материализованной проекции, секционированной таблицы. К такого рода неоднозначности мы вернёмся в разделе, посвящённом проектированию.

Что же представляет собой отношение с более формальной точки зрения? Обратимся к первоисточнику.

является отношением на этих n множествах, если представляет собой множество кортежей степени n, у каждого из которых первый элемент взят из множества S1, второй — из множества S2 и т.д. Мы будем называть Sj j- тым доменом R. Говорят, что такое отношение R имеет степень n. Отношения степени 1 часто называют унарными, степени 2 — бинарными, степени 3 — тернарными и степени n — n-арными.

Для лучшего понимания столь лаконичного определения воспользуемся его графической интерпретацией.

Рис. 2. Отношение, как множество кортежей, заданных на доменах

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

Реляционная модель: плюсы и минусы

К преимуществам реляционной модели можно отнести следующие особенности:

Недостатки:

[1] XPath (от англ. XML Path Language) — язык запросов к элементам XML-документа.

[2] MUMPS — Massachusetts General Hospital Utility Multi-Programming System, позднее Multi-User Multi-Programming System, разработка датирована 1966 годом.

Источник