ПЛЕЩ. Учебное пособие содержит

• Название: Учебное пособие содержит
• Анкор: ПЛЕЩ.docx
• Дата: 29.06.2018
• Размер: 3.78 Mb.
• Имя файла: ПЛЕЩ.docx
• Тип: Учебное пособие; #20888
• страница: 7 из 20

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

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

СОТРУДНИК

ПОДРАЗДЕЛЕНИЕ

РАБОТА

Рисунок 1.3.6.1. Пример иерархической структуры

Рассмотрим ряд терминов иерархической модели.

Высота, вес и момент дерева  число уровней, листьев и узлов в дереве.

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

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

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

Бинарное (двоичное) дерево  сбалансированное дерево с исходными узлами степени два. Любое дерево можно преобразовать в бинарное дерево. Поиск данных в бинарном дереве наиболее быстрый.

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

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

Иерархическая модель данных является наиболее простой среди всех даталогических моделей. Исторически она появилась первой: именно эту модель поддерживает первая из зарегистрированных промышленных СУБД IMS фирмы IBM.

Рассмотрим основные понятия этой СУБД.

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

Поле данных - это минимальная, неделимая единица данных, доступная пользователю с помощью СУБД.

Сегмент – это запись,при этом определяются два понятия: тип сегмента или тип записи и экземпляр сегмента или экземпляр записи.

Тип сегмента - это поименованная совокупность типов элементов данных, в него входящих.

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

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

В иерархической модели сегменты объединяются в ориентированный древовидный граф (содержание этого и следующих параграфов скопировано из работы [19]). При этом полагают, что дуги отражают иерархические связи между сегментами: каждому экземпляру сегмента, стоящему выше по иерархии и соединенному с данным типом сегмента, соответствует несколько (множество) экземпляров данного (подчиненного) типа сегмента. Тип сегмента, находящийся на более высоком уровне иерархии, называется логически исходным по отношению к типам сегментов, соединенным с данным направленными иерархическими ребрами, которые в свою очередь называются логически подчиненными по отношению к этому типу сегмента. Иногда исходные сегменты называют сегментами-предками, а подчиненные сегменты называют сегментами-потомками.

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

Каждая физическая БД удовлетворяет следующим иерархическим ограничениям:

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

Сегмент является экземпляром типа сегмента. Между экземплярами сегментов также существуют иерархические связи.

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

В рамках иерархической модели выделяют языковые средства описания данных (DDL, Data Definition Language) и средства манипулирования данными (DML, Data Manipulation Language).

Каждая физическая база описывается набором операторов, определяющих как ее логическую структуру, так и структуру хранения БД. Описание начинается с оператора определения базы - DBD (Data Base Definition):

DBD Name = < имя БД>, ACCESS = < способ доступа>

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

Определено 4 способа доступа:

HDAM - hierarchicaldirectaccessmethod(иерархически прямой метод) - максимально быстрый, но не компактно хранящий данные;

HSAM - hierarchicalsequentialaccessmethod(иерархически последовательный метод) - наиболее медленный, но компактно хранящий данные;

HIDAM - hierarchicalindexdirectaccessmethod(иерархически индексно-прямой метод) – компромиссный вариант, ближе к HDAM.

HISAM - hierarchicalindexsequentialaccessmethod(иерархически индексно-последовательный метод) - компромиссный вариант, ближе к HSAM;

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

Представление внешней модели называется логической базой данных и определяется совокупностью блоков связи данного приложения с физическими БД, входящими в концептуальную схему БД. Блок связи – РСВ, program communication bloc – описывает связь с одной физической БД. Совокупность блоков РСВ образует полное внешнее представление данного приложения, называемое «блоком спецификации программ» (PSB, program specification block).

При формировании исполнимого файла прикладной программы модуль с описанием базы данных и подсхемы (PSB) включались в исполнимый файл и использовались при выполнении программы.

 Для организации физического размещения иерархических данных в памяти ЭВМ могут использоваться следующие группы методов: 

представление линейным списком с последовательным распределением памяти (адресная арифметика, левосписковые структуры); 

представление связными линейными списками (методы, использующие указатели и справочники).  

К основным операциям манипулирования иерархически организованными данными относятся следующие: 

поиск указанного экземпляра БД (например, дерева со значением 10 в поле Отд_номер); 

переход от одного дерева к другому; 

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

ставка новой записи в указанную позицию; 

удаление текущей записи и т. д. 

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

К достоинствам иерархической модели данных относятся эффективное использование памяти ЭВМ и неплохие показатели времени выполнения основных операций над данными. Иерархическая модель данных удобна для работы с иерархически упорядоченной информацией. 

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

На иерархической модели данных основано сравнительно ограниченное количество СУБД, в числе которых можно назвать зарубежные системы IMS, PC/Focus, Team-Up и Data Edge, а также отечественные системы Ока, ИНЭС и МИРИС.

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

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


ЗАВОД

ИЗДЕЛИЕ



ВЫПУСК ИЗДЕЛИЯ



Рисунок 1.3.7.1. Пример сетевой структуры
Стандарт сетевой модели впервые был определен в 1975 году организацией CODASYL (Conference of Data System Languages), которая определила базовые понятия модели и формальный язык описания.

Базовыми объектами модели являются следующие.

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

Агрегат данных - соответствует следующему уровню обобщения в модели. В модели определены агрегаты двух типов: агрегат типа вектор и агрегат типа повторяющаяся группа

Запись - совокупность агрегатов или элементов данных, моделирующая некоторый класс объектов реального мира. Понятие записи соответствует понятию «сегмент» в иерархической модели. Для записи, так же как и для сегмента, вводятся понятия типа записи и экземпляра записи.

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

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

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

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

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

Достоинство: универсальность. Недостатки: сложность и жесткость.

Примеры СУБД: IDMS, dbVista, Сеть, Сетор, Компас, Банк ОС.

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

1.3.8.1. Отношения

Американский математик Э. Ф. Кодд в 1970 году впервые сформулировал основные понятия и ограничения реляционной модели, ограничив набор операций в ней семью основными и одной дополнительной операцией (содержание данного пункта скопировано из работы [19]).

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

N-арным отношением R называют подмножество декартова произведения D,xD₂x ... xD_n множеств D,, D₂, ..., D_n (n > 1), необязательно различных. Исходные множества D₁, D₂, ..., D_n называют в модели доменами.

Полное декартово произведение (D₁xD₂x ...xD_n) – это набор всевозможных сочетаний из n элементов каждое, где каждый элемент берется из своего домена. Например, имеем три домена: D₁ содержит три фамилии, D₂ – набор из двух учебных дисциплин и D₃ – набор из трех оценок. Допустим, содержимое доменов следующее:

D₁ = {Иванов, Крылов, Степанов};

D₂ = (Теория автоматов, Базы данных};

D₃ = {3, 4, 5}

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

Фамилия	Дисциплина	Оценка
Агеев	Теория автоматов	4
Агеев	Базы данных	3
Сидоров	Теория автоматов	5
Петров	Теория автоматов	5
Петров	Базы данных	4

Данная таблица обладает рядом специфических свойств:

1. 
   В таблице нет двух одинаковых строк.
   
2. 
   Таблица имеет столбцы, соответствующие атрибутам отношения.
   
3. 
   Каждый атрибут в отношении имеет уникальное имя.
   
4. 
   Порядок строк в таблице произвольный.
   

Вхождение домена в отношение принято называть атрибутом. Строки отношения называются кортежами.

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

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

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

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

S_R = (А₁, А₂, …, А_n) А_i принадлежит D_i

Если атрибуты принимают значения из одного и того же домена, то они называются Q-сравпимыми, где Q– множество допустимых операций сравнения, заданных для данного домена. Например, если домен содержит числовые данные , то для него допустимы все операции сравнения, тогда Q = {=, <>,>=,<-,<,>}. Однако и для доменов, содержащих символьные данные, могут быть заданы не только операции сравнения по равенству и неравенству значений. Если для данного домена задано лексикографическое упорядочение, то он имеет также полный спектр операций сравнения.

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

S_R1 = (A₁, A₂, ..., A_n) – схема отношения R₁.

S_R2 ⁼ (B_i1, B_i2,..., B_in) – схема отношения R₂после упорядочения имен атрибутов.

Тогда s_R1s_R2<=>1. n=m, или 2. А_j, Bij принадлежатD_j

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

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

1.3.8.2. Теоретико-множественные операции с отношениями

Алгеброй - называется множество объектов с заданной на нем совокупностью операции, замкнутых относительно этого множества (результаты принадлежат этому множеству), называемого основным множеством (содержание данного пункта скопировано из работы [19]).

Основное множество в реляционной алгебре - это всё возможное множество отношений.

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

Объединение двух отношений - это отношение, содержащее множество кортежей, принадлежащих либо первому, либо второму исходным отношениям, либо обоим отношениям одновременно.

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

Пересечение отношений в реляционной алгебре - это отношение, которое содержит множество кортежей, принадлежащих одновременно и первому и второму отношениям. R₁ и R₂:

Пример, отношение R₄ содержатся перечень деталей, которые выпускаются одновременно на двух участках цеха.

Разность отношений в реляционной алгебре - это отношение R₁ и R₂, содержащее множество кортежей, принадлежащих R₁ и не принадлежащих

Пример, отношение R₅ содержит перечень деталей, изготавливаемых только на участке 1, отношение R₆ содержит перечень деталей, изготавливаемых только на участке 2.

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

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

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

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

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

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

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

Операция условного соединения. Соединением отношений R и Q при условии Р будет подмножество декартова произведения отношений R и Q и связанных по группе атрибутов и кортежи, которого удовлетворяют условию Р.

Операция деления. Поясним эту операцию на примере. Операция деления удобна тогда, когда требуется сравнить некоторое множество характеристик отдельных атрибутов. Например, пусть у нас есть отношение R₁, которое содержит номенклатуру всех выпускаемых деталей на нашем предприятии, а в отношении R₂ хранятся сведения о том, что и в каких цехах действительно выпускается. Поставим задачу определить перечень цехов (R₃₎, в которых выпускается вся номенклатура деталей.

Тогда решением этой задачи будет операция деления отношения R₂ на отношение R₁ по набору атрибутов (Шифр детали, Наименование детали).

R₃ ⁼ R₂[Шифр детали, Наименование детали: Шифр детали, Наименование детали] R₁

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

В заключении можно отметить, что данные операции реализованы средствами команды Select языка запросов SQL и не используются в такой математической форме.

1.3.8.3. Правила Кодда

В 1985 году в двух статьях в журнале Computer World Э.Ф. Кодд сформулировал правила, которым должны соответствовать настоящие реляционные базы данных (содержание данного пункта скопировано из работы [19]).

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

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

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

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

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

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

Правило 6 (правило обновления представлений). Все представления, которые теоретически можно обновить, должны быть обновляемы.

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

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

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

Правило 10 (правило независимости условий целостности). Должна существовать возможность формулировки правил целостности специфических для данной базы данных на языке реляционных баз данных.

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

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

Таким образом, если коротко, то реляционная база данных представляет собой набор взаимосвязанных двухмерных таблиц (отношений).

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

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

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

Практически все современные СУБД (Oracle (Oracle), Access, MS SQL Server, Visual FoxPro (Microsoft), Interbase (Borland) и др.) являются реляционными.

1.3.8.4. Индексирование таблиц

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

Физическая организация индексов, обычно скрыта от программиста и для различных СУБД она различная. Например, для Access индексы хранятся вместе с данными в одном файле, а для Visual FoxPro – в отдельном файле для одного и группы индексов.

Пример. Создадим для таблицы сотрудников (таблица 1.3.8.4.1) индекса по табельному номеру (таблица 1.3.8.4.2).

Таблица 1.3.8.4.1

Таблица «Сотрудники»

Запись №	Табельный №	Фамилия	Код подразделения	Другие поля
1	20	Иванов	2	…
2	50	Сидоров	1	…
3	30	Петров	2	…
4	10	Агеев	1	…
5	60	Смирнов	2	…

Таблица 1.3.8.4.2

Таблица индексов по табельному номеру

Табельный №	Запись №
10	4
20	1
30	3
50	2
60	5

При изменении информации в таблице автоматически обновляются все индексы таблицы.

Наличие индекса позволяет:

1. 
   Обработать таблицу в нужной последовательности (логическая сортировка таблицы). Для этого назначается главный индекс, который задает порядок (по возрастанию или убыванию значения индекса) чтения записей таблицы (в примере по возрастанию значения табельного номера). Главный индекс можно определить при помощи специальных команд управления индексами (например, Set Index to для FoxPro, или фразой фраза SetOrderTo оператора Select языка SQL).
   
2. 
   Осуществить прямой поиск нужной записи по ее индексу (например, табельного номера равного 30) методом двоичного поиска записи индексной таблицы и сравнения текущего индекса с искомым значением индекса (30). Если текущий индекс не совпадает с исходным, то СУБД выводит сообщение об отсутствии записи с исходным значение индекса (обычно, это может случиться после аварийного завершения работы с базой данных, например, при отключении электропитания или “зависания” операционной системы). После нахождения записи в индексном файле выбирается адрес (номер записи 3), и запись таблицы с данным адресом (под номером 3) становится текущей. Так как размеры индексных файлов небольшие, то они хранятся в оперативной памяти и двоичный поиск в оперативной памяти производится максимально быстро. В нашем примере, нужно найти запись о сотруднике с табельным номером 30, то будет не последовательный поиск нужной записи, а двоичный в индексной таблице, что значительно быстрее (число шагов поиска равно двоичному логарифму из числа всех записей в индексной таблице). Если учесть, что СУБД все знает о своих файлах, размерах записей и таблиц, о типе и емкости дисководов, то она рассчитывает точный физический адрес записи по ее номеру в таблице (имя диска, номер цилиндра, дорожки и сектора) и головка чтения за одно перемещение находит и читает нужную запись. Таким образом, время поиска и чтения практически не зависит от числа записей в таблице и примерно равно времени механического перемещения головки чтения и записи дисковода и одного оборота диска. Если индексная таблица содержит много записей, то могут использоваться иерархическая, а не линейная организация хранения индексов, что ускоряет поиск записей (это внутренняя задача самой СУБД, программист освобожден от этого).
   
3. 
   Организовать быстрый последовательный поиск группы записей таблицы по условию их отбора путем использования фильтрованного индекса или использовать индексы вместо полей записей таблицы в условиях отбора записей. Например, вывести сотрудников подразделения с кодом 2.
   
4. 
   Для полей связей таблиц должны быть созданы индексы.
   

Обычно выделяют следующие типы индексов.

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

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

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

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

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

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

1.3.8.5. Связывание таблиц

Таблицы обычно связываются попарно через ключи связи (п. 1.3.1). Ключи связи должны быть одинакового типа в родительской и дочерней таблицах. Связи бывают постоянные и временные. Постоянные связи устанавливаются до выполнения прикладной программы при создании логической модели данных (обычно визуальными средствами). Этими связями можно пользоваться в прикладной программе. Временные связи устанавливаются при выполнении прикладной программы (в FoxPro командой Set Relation, в языке SQL – в фразах JOIN и WHERE оператора SELECT) и удаляются после ее выполнения. Использование связанных таблиц существенно упрощает пользователю обработку таблиц (так, перемещаясь по родительской таблице, происходит автоматическое перемещение по ее дочерним таблицам по условию равенства ключей связи), автоматически обеспечивая контроль целостности (п. 1.3.5). Дочерняя таблица должна иметь индекс по ключу связи.

1.3.9. Постреляционная модель

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

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

Пример. Имеется реляционная база из двух таблиц:

НАКЛАДНЫЕ (номер накладной, дата поставки, код поставщика).

ТОВАРЫ (номер накладной, код товара, количество, единица измерения).

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

НАКЛАДНЫЕТОВАРЫ (номер накладной, дата поставки, код поставщика, товары в накладной).

Поле “Товары в накладной” является таблицей “ТОВАРЫ”.

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

Примеры СУБД: uniVers, Bubba, Dasdb.

1.3.10. Многомерная модель

Информация, накопленная в базах данных, является чрезвычайно ценным материалом, и в настоящий момент широко распространяются методы обработки баз данных с точки зрения извлечения из них дополнительных знаний, методов, которые связаны с обобщением и различными дополнительными способами обработки данных (содержание данного пункта скопировано из работы [19]). Базы данных в данной концепции выступают как хранилища информации, это направление называется «Хранилища данных» (Data Warehouse).

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

В бизнес-приложениях наибольший интерес представляет интеграция методов интеллектуального анализа данных с технологией оперативной аналитической обработки данных (On-Line Analytical Processing, OLAP). OLAP использует многомерное представление агрегированных данных для быстрого доступа к важной информации и дальнейшего ее анализа.

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

В основе концепции оперативной аналитической обработки (OLAP) лежит многомерное представление данных. Термин OLAP ввел Кодд (Е. F. Codd) в 1993 году.

Одновременный анализ по нескольким измерениям данных определяется как многомерный анализ. Каждое измерение включает направления интеграции данных, состоящие из серии последовательных уровней обобщения, где каждый вышестоящий уровень соответствует большей степени агрегации данных по соответствующему измерению. Так, измерение Исполнитель может определяться направлением консолидации, состоящим из уровней обобщения «предприятие–подразделение–отдел-служащий». Измерение Время может даже включать два направления консолидации – «год–квартал–месяц–день» и «неделя–день», поскольку счет времени по месяцам и по неделям несовместим. В этом случае становится возможным произвольный выбор желаемого уровня детализации информации по каждому из измерений. Операция спуска (drilling down) соответствует движению от высших ступеней консолидации к низшим; напротив, операция подъема (rolling up) означает движение от низших уровней к высшим.

Многомерная модель  узкоспециализированная модель, предназначенная для хранения данных в виде многомерного массива (гиперкуба), используемых системами оперативной аналитической обработки типа OLAP или систем поддержки принятия решений DSS (Decision Support. System, пример MS DSS).

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

Рассмотрим ряд терминов этой модели.

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

Историчность данных подразумевает привязку данных ко времени (наличие временных рядов).

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

Срез (Slice)  подмножество гиперкуба, полученное в результате фиксации одного или нескольких измерений.

Пример. Если ограничить значения измерения “Марка автомобиля” маркой “ВАЗ 2105”, то получим двухмерную таблицу продажи автомобилей этой марки по городам и годам.

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

Агрегация/детализация (Drill Up/Down)  переход к более общему/детальному представлению информации пользователю из гиперкуба.

Пример. Можно сформировать итоговую таблицу продаж автомобилей (независимо от их марок) по городам и годам.

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

Примеры СУБД: Essbase (Arbor Software), Media Multimatrix и Media/MR (Speedware), Oracle Express Server (Oracle), Cache.

1.3.11. Объектноориентированная модель

В объектно-ориентированной модели предметная область моделируется как множество классов взаимодействующих объектов (содержание данного пункта скопировано из работы [19]). Каждый объект характеризуется набором свойств, которые являются как бы его пассивными характеристиками и набором методов работы с этим объектом. Работать с объектом можно только с использованием его методов. Атрибуты объекта могут принимать определенное множество допустимых значений, набор конкретных значений атрибутов объекта определяет его состояние. Используя методы работы с объектом, можно изменять значение его атрибутов и тем самым как бы изменять состояние самого объекта. Множество объектов с одним и тем же набором атрибутов и методов образует класс объектов. Объект должен принадлежать только одному классу (если не учитывать возможности наследования). Допускается наличие примитивных предопределенных классов, объекты-экземпляры которых не имеют атрибутов: целые, строки и т. д. Класс, объекты которого могут служить значениями атрибута объектов другого класса, называется доменом этого атрибута.

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

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

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

Специфика применения объектно-ориентированного подхода для организации и управления БД потребовала уточненного толкования классических концепций и некоторого их расширения.

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

Для перехода к объектно-ориентированным БД стандарт объектного проектирования был дополнен стандартизованными средствами доступа к базам данных (стандарт ODMG93).

Многие фирмы обратилась к объектным технологиям и продуктивно сотрудничает с разработчиками объектно-ориентированных СУБД. IBM и Oracle доработали свои СУБД (соответственно, DB2 и ORACLE), добавив объектную надстройку над реляционным ядром системы. Другой путь выбрал Informix, который приобрел серьезную объектно-реляционную СУБД Illustra и встроил ее в свою СУБД. В результате получился продукт, именующийся универсальным сервером. Другой лидер рынка СУБД – Computer Associates, поступил иначе. Он сделал ставку на чисто объектную базу Jasmine, активно пропагандируя ее достоинства.

Объектноориентированную модель можно представить в виде дерева объектовклассов. У каждого объекта имеется набор свойств. Свойство типа “класс” есть экземпляр соответствующего класса, который является потомком объекта, в котором он определен как свойство.

Пример базы данных учета товаров на складе. База состоит из объектов (атрибутыобъекты выделены прописными буквами) (рисунок 1.3.11.1):

ПОТРЕБИТЕЛЬ

СКЛАД

ВЫДАЧА

ТОВАР
Рисунок 1.3.11.1. Объектноориентированная модель базы учета товаров на складе
СКЛАД (Наименование склада, ПОТРЕБИТЕЛЬ, НОМЕНКЛАТУРА, ВЫДАЧА, телефон).

ПОТРЕБИТЕЛЬ (Код потребителя, наименование потребителя, телефон).

ВЫДАЧА (Код потребителя, код товара, дата выдачи, количество, единица измерения).

ТОВАР (Код товара, наименование товара, количество на складе, единица измерения).

Объект “СКЛАД” является родительским для объектовэкземпляров классов “ПОТРЕБИТЕЛЬ”, “НОМЕНКЛАТУРА”, “ВЫДАЧА”.

Достоинства: возможность отображения более сложных связей объектов и определения для каждой отдельной записи базы функций их обработки. Недостатки: сложность и низкая скорость обработки.

Примеры СУБД: POET (POET Software), Jasmine (Computer Associates), Versant (Versant Technologies), O2 (Ardent Software), ODBJupiter (НПЦ “Интеллект Плюс”), Iris, Orion, Postgres.