41118

Представление данных в памяти компьютера

Лекция

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

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

Русский

2013-10-22

1.96 MB

44 чел.

Оглавление

[1] Оглавление

[2]
1. Введение. Представление данных в памяти компьютера

[2.1] 1.1 ПРЕДМЕТ ДИСЦИПЛИНЫ И ЕЁ ЗАДАЧИ

[2.2] 1.2 ОСНОВНЫЕ ПОНЯТИЯ

[2.3] 1.3 ФАЙЛОВЫЕ СИСТЕМЫ, КАК ПЕРВЫЙ ШАГ К СОЗДАНИЮ СУБД

[2.4] 1.4 СТРУКТУРНАЯ СХЕМА СУБД И ОСНОВНЫЕ ФУНКЦИИ

[2.5] 1.5 ПРЕИМУЩЕСТВА И НЕДОСТАТКИ СУБД ПО СРАВНЕНИЮ С ФАЙЛОВЫМИ СИСТЕМАМИ

[2.6] 1.6 ОРГАНИЗАЦИЯ ВНЕШНЕЙ ПАМЯТИ РЕЛЯЦИОННОЙ СУБД

[2.7] 1.7 Типы и структуры данных

[2.8] 1.8 Типы и структуры данных, применяемые в реляционных БД

[2.9] 1.9 Типы и структуры данных, применяемые в объектно-реляционных БД

[2.10] 1.10 Понятие модели данных

[3]
2. МОДЕЛИ ПРЕДСТАВЛЕНИЯ ДАННЫХ

[3.1] 2.1 ИЕРАРХИЧЕСКАЯ МОДЕЛЬ ДАННЫХ

[3.2] 2.2 Сетевая модель данных

[3.3] 2.3 Реляционная модель данных

[3.4] 2.4 Свойства отношений. Отличие отношений от таблиц.

[3.5] 2.5 Понятие целостности данных

[3.6] 2.6 Ограничения реляционных баз данных

[3.7] 2.7 Суть постреляционного объектно-ориентированного подхода

[3.8] 2.8 Объектно-ориентированные СУБД и стандарт ODMG

[3.9] 2.9 Объектно-реляционные СУБД

[4]
3. Проектирование реляционных БД

[4.1] 3.1 Этапы разработки базы данных

[4.2] 3.2 Критерии оценки качества логической модели данных

[4.3] 3.3 Проектирование баз данных на основе нормализации отношений

[4.4] 3.4 Первая нормальная форма

[4.5] 3.5 Аномалии обновления

[4.6] 3.6 Функциональные зависимости

[4.7] 3.7 Вторая нормальная форма

[4.8] 3.8 Третья нормальная форма

[4.9] 3.9 Алгоритм нормализации (приведение к 3NF)

[4.10] 3.10 OLTP и OLAP-системы

[4.11] 3.11 Корректность процедуры нормализации. Теорема Хеза

[4.12] 3.12 Нормальная Форма Бойса-Кодда (NFBK)

[4.13] 3.13 Четвертая Нормальная Форма

[4.14] 3.14  Пятая Нормальная Форма

[4.15] 3.15 Продолжение алгоритма нормализации (приведение к 5 NF)

[5] 5. CASE – технологии

[5.1] 5.1 Общие вопросы проектирования ИС, понятие CASE-технологии

[5.2] 5.2 Жизненный цикл ПО ИС

[5.3] 5.3 Модели жизненного цикла ПО

[5.4] 5.4 Методология RAD

[5.5] 5.5 Структурный подход к проектированию ИС

[5.6] 5.6 Методология функционального моделирования SADT (IDEF0)

[5.7] 5.8 Методы построения диаграмм «сущность-связь» (ERD)

[5.8] 5.9 Моделирование данных CASE-методом Баркера

[5.9]  

[5.10] 5.10 Методология IDEF1

[6] 6. Организация доступа прикладной программы

[7] к серверу базы данных

[7.1] 6.1 Общие сведения

[7.2] 6.2 Использование специализированных библиотек и встраиваемого SQL

[7.3] 6.3 CLI – интерфейс уровня вызовов

[7.4] 6.4 ODBC – открытый интерфейс к БД на платформе MS Windows

[7.5] 6.5 JDBC - интерфейс к базам данных на платформе Java

[8]
Литература


1. Введение. Представление данных в памяти компьютера

1.1 ПРЕДМЕТ ДИСЦИПЛИНЫ И ЕЁ ЗАДАЧИ

Предметом изучения дисциплины «Информационное обеспечение систем управления» (ИОСУ) являются модели представления данных и, созданные на их основе, системы управления базами данных (СУБД).

Цель изучения данного курса – получение и систематизация знаний об основных идеях и методах создания реляционных и постреляционных СУБД

Основными задачами являются: приобретение студентом знаний о способах хранения данных в памяти компьютера и методах доступа к ним, о методах проектирования реляционных моделей данных, об использовании CASE-технологий при разработке приложений; приобретение навыков самостоятельной работы при создании концептуальных и логических моделей данных, при разработке физических моделей и управлению базой данных (БД) в среде СУБД Microsoft Access, а также изучение структурированного языка запросов (SQL), процедурного языка программирования PL/SQL и СУБД Oracle.

Дисциплина ИОСУ связана с курсом «Основы алгоритмизации и программирования» и предполагает наличие у студентов опыта программирования на объектно-ориентированных языках программирования третьего поколения (С++, Visual C, ASP.net, Java и др.)

В результате освоения курса «Информационное обеспечение систем управления» инженер по специальности «Информационные технологии и управление в технических системах» должен знать:

- структуру представления данных в памяти ЭВМ, методы доступа к данным и методы обеспечения целостности данных;

- состав и классификацию информационных систем, информационного обеспечения, моделей БД, СУБД и современные тенденции их развития;

- теорию реляционных БД, современные методы создания их проектирования;

- принципы построения и реализации операторов SQL, их стандартный синтаксис;

- инструменты и средства разработки клиентских приложений, использующих реляционные БД;

- современное состояние систем управления производственной информацией.

уметь:

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

- создавать диаграммы потоков данных и диаграммы «сущность-связь»;

- создавать реляционные модели БД;

приобрести навыки:

- создания физических моделей реляционных БД в конкретной среде разработки;

- работы с информационным обеспечением систем управления под управлением СУБД Microsoft Ассеss и Oracle.

1.2 ОСНОВНЫЕ ПОНЯТИЯ

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

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

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

Основные виды информации по форме представления и способам кодирования и хранения − это графическая или изобразительная; звуковая; текстовая; числовая; видеоинформация.

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

Информационное обеспечение в широком смысле имеет три значения:

1) обеспечение фактическими данными управленческих структур;

2) использование информационных данных для автоматизированных систем управления (АСУ);

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

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

Вторым важным направлением ИО является формирование информационных данных для автоматизированных систем управления. Вводимая в БД АСУ информация является необходимым элементом работы всей системы, без которой невозможно ее математическое, техническое, организационно-правовое функционирование. Информация, вводимая в систему, ее предмашинная обработка − основа современных автоматизированных информационных систем (АИС).

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

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

ИО информационных систем (ИС) является средством для решения следующих задач:

однозначного и экономичного представления информации в системе (на основе кодирования объектов);

организации процедур анализа и обработки информации с учетом характера связей между объектами (на основе классификации объектов);

организации взаимодействия пользователей с системой (на основе экранных форм ввода-вывода данных);

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

ИО ИС включает два комплекса: внемашинное информационное обеспечение (классификаторы технико-экономической информации, документы, методические инструктивные материалы) и внутримашинное информационное обеспечение (макеты/экранные формы для ввода первичных данных в ЭВМ или вывода результатной информации, структуры информационной базы: входных, выходных файлов, базы данных).

К ИО предъявляются следующие общие требования:

ИО должно быть достаточным для поддержания всех автоматизируемых функций объекта;

для кодирования информации должны использоваться принятые у заказчика классификаторы;

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

должна быть обеспечена совместимость с ИО систем, взаимодействующих с разрабатываемой системой;

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

структура документов и экранных форм должна соответствовать характеристикам терминалов на рабочих местах конечных пользователей;

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

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

Основными источниками информации для ИО служат:

информационно-справочная информация;

отчетные формы документов;

информация вышестоящих органов;

бухгалтерская информация.

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

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

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

Другими словами ИС требует создания в памяти ЭВМ динамически обновляемой модели внешнего мира с использованием единого хранилища – базы данных.

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

Рис. 1 Структура ИС

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

Рис. 2. Классификация информационных систем

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

По степени автоматизации информационных процессов ИС делятся на ручные, автоматические и автоматизированные.

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

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

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

В зависимости от характера обработки данных ИС делятся на информационно-поисковые и информационно-решающие.

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

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

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

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

В зависимости от сферы применения различают:

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

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

ИС управления технологическими процессами (АСУ ТП) − служат для автоматизации функций производственного персонала по контролю и управлению производственными операциями. В таких системах обычно предусматривается наличие развитых средств измерения параметров ТП (температуры, давления, химического состава и т.п.), процедур контроля допустимости значений параметров и регулирования ТП.

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

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

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

База данных − это организованная в соответствии с определёнными правилами и поддерживаемая в памяти компьютера совокупность данных, характеризующая актуальное состояние некоторой предметной области и используемая для удовлетворения информационных потребностей пользователей [2].

База данных – это совместно используемый набор логически связанных данных (и описание этих данных), предназначенный для удовлетворения информационных потребностей организации [3].

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

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

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

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

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

Существует огромное количество разновидностей БД, отличающихся по различным критериям. Например, в [2] определяются свыше 50 видов БД.

Рассмотрим самые важные для изучаемого курса признаки классификации.

В зависимости от модели данных различают следующие БД:

иерархические;

сетевые;

реляционные;

объектно-реляционные;

объектно-ориентированные (объектные).

Иногда иерархические и сетевые модели данных называют дореляционными, а объектно-реляционные и объектно-ориентированные – постреляционными.

Существует классификация БД по технологии хранения данных в памяти компьютера:

БД во вторичной памяти (традиционные);

БД в оперативной памяти (in-memory databases);

БД в третичной памяти (tertiary databases).

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

По степени распределённости хранимых данных различают: централизованные (сосредоточенные) и распределённые БД.

По характеру содержимого БД бывают: географические, исторические, научные, мультимедийные и т.д.

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

СУБД – это специализированная программа (комплекс программ), предназначенная для организации и ведения БД.

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

1. управление данными во внешней памяти;

2. управление буферами оперативной памяти;

3. управление транзакциями;

4. журнализация;

5. поддержка языков БД.

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

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

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

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

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

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

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

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

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

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

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

Журнал – это особая часть БД, недоступная пользователям СУБД и поддерживаемая с особой тщательностью (иногда существуют две копии журнала, располагаемые на разных физических дисках), в которую поступают записи обо всех изменениях основной части БД. Во всех случаях придерживается стратегия "упреждающей" записи в журнал (протокол Write Ahead Log – WAL). Эта стратегия заключается в том, что запись об изменении любого объекта БД должна попасть во внешнюю память журнала раньше, чем сам измененный объект попадет во внешнюю память основной части БД. Таким образом, если в СУБД корректно соблюдается протокол WAL, то с помощью журнала можно решить все проблемы восстановления БД практически после любого сбоя.

Поддержка языков БД. Для работы с БД используются специальные языки, в целом называемые языками баз данных. В ранних СУБД поддерживалось несколько специализированных по своим функциям языков, таких как язык определения схемы данных (DDL  – Data Definition Language) и язык манипулирования данными (DML – Data Manipulation Language).

В современных СУБД обычно поддерживается единый интегрированный язык, содержащий все необходимые средства для работы с БД, начиная от ее создания, и заканчивая обеспечением базового пользовательского интерфейса. Стандартным языком реляционных СУБД является язык SQL (Structured Query Language). SQL сочетает средства DDL и DML, т.е. позволяет определять схему реляционной БД и манипулировать данными. Язык SQL содержит также операторы для определения ограничений целостности БД, позволяет создавать представления, фактически являющиеся хранимыми в БД запросами, индексы, домены, синонимы, последовательности и другие, хранимые в схеме пользователя объекты. Кроме этого, позволяет решать вопросы авторизации доступа к объектам БД и выделения полномочий (привилегий) на работу с ними, управляет работой транзакций – эти специальные средства иногда определяют как третью составную часть SQL (в дополнение к DDL и DML) и называют языком управления данными (DCL - Data Control Language)[4].

1.3 ФАЙЛОВЫЕ СИСТЕМЫ, КАК ПЕРВЫЙ ШАГ К СОЗДАНИЮ СУБД

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

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

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

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

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

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

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

В широком смысле понятие файловой системы включает:

совокупность всех файлов на диске,

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

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

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

Файлы бывают разных типов: обычные файлы, специальные файлы, файлы-каталоги.

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

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

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

Различают два основных подхода к определению прав доступа:

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

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

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

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

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

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

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

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

Реализуем данную ИС на основе файловой системы и воспользуемся при этом одним файлом, расширив базовые возможности файловой системы за счет специальной библиотеки функций. Поскольку минимальной информационной единицей является сотрудник, естественно потребовать, чтобы в этом файле содержалась одна запись для каждого сотрудника. Очевидно, что поля таких записей должны содержать полное имя сотрудника (СОТР_ИМЯ), номер его удостоверения (СОТР_НОМЕР), информацию о его соответствии занимаемой должности (СОТР_СТАТ - для простоты, «да» или «нет»), размер зарплаты (СОТР_ЗАРП), номер отдела (СОТР_ОТД_НОМЕР) и эта же запись должна содержать имя руководителя отдела (СОТР_ОТД_РУК).

Для поддержания нормальной работы ИС требуется возможность многоключевого доступа к этому файлу по уникальным ключам  СОТР_ИМЯ и СОТР_НОМЕР. Кроме того, должна обеспечиваться возможность выбора всех записей с общим заданным значением СОТР_ОТД_НОМЕР, то есть доступ по неуникальному ключу. Чтобы получить численность отдела или общий размер зарплаты, ИС должна будет каждый раз выбирать все записи о сотрудниках отдела и подсчитывать соответствующие общие значения.

Таким образом, для реализации даже такой простой ИС на базе файловой системы, во-первых, требуется создание достаточно сложной надстройки, обеспечивающей многоключевой доступ к файлам, и, во-вторых, неизбежны существенная избыточность хранения (для каждого сотрудника данного отдела повторяется имя руководителя отдела) и выполнение массовой выборки и вычислений для получения сводной информации об отделах. Кроме того, если в ходе эксплуатации системы возникнет потребность, например, выдавать списки сотрудников, получающих заданную зарплату, то придется либо полностью просматривать файл, либо реструктурировать его, объявляя ключевым поле СОТР_ЗАРП.

Для решения проблем первое, что необходимо, это поддерживать два многоключевых файла СОТРУДНИКИ и ОТДЕЛЫ. Тогда первый файл должен содержать поля СОТР_ИМЯ, СОТР_НОМЕР, СОТР_СТАТ, СОТР_ЗАРП и СОТР_ОТД_НОМЕР, а второй - ОТД_НОМЕР, ОТД_РУК, СОТР_ЗАРП (общий размер зарплаты) и ОТД_РАЗМЕР (общее число сотрудников в отделе). Каждый из файлов будет содержать только недублируемую информацию, а необходимость в динамических вычислениях сводной информации не возникнет.

Обновленная таким образом ИС будет обладать возможностями, сближающими ее с СУБД. Прежде всего, теперь система должна знать, что работает с двумя информационно связанными файлами, ей должны быть известны структура и смысл каждого поля (например, что СОТР_ОТД_НОМЕР в файле СОТРУДНИКИ и ОТД_НОМЕР в файле ОТДЕЛЫ означают одно и то же), а также понимать, что в ряде случаев изменение информации в одном файле должно вызывать модификацию второго файла, чтобы общее содержимое файлов было согласованным. Например, если на работу принимается новый сотрудник, то необходимо добавить запись в файл СОТРУДНИКИ, а также соответствующим образом изменить поля ОТД_ЗАРП и ОТД_РАЗМЕР в записи файла ОТДЕЛЫ, описывающей отдел этого сотрудника.

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

Рассмотрим еще несколько особенностей работы с данным, хранящимися в файлах. Представим, что обрабатывается операция регистрации нового сотрудника. Следуя требованиям согласованного изменения файлов, сначала вставим новую запись в файл СОТРУДНИКИ, а затем будем модифицировать запись файла ОТДЕЛЫ, но если именно в этот момент произойдет аварийное выключение электрического питания, то после перезапуска системы файловая БД будет находиться в рассогласованном состоянии. Потребуется явно проверить соответствие информации в файлах СОТРУДНИКИ и ОТДЕЛЫ и привести информацию в согласованное состояние. Настоящие СУБД берут такую работу на себя.

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

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

1.4 СТРУКТУРНАЯ СХЕМА СУБД И ОСНОВНЫЕ ФУНКЦИИ

Типовая структурная схема СУБД [3] представлена на рис.3.

Рис. 3 Структурная схема СУБД

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

Перечислим основные программные компоненты, входящие в состав контроллера БД.

Модуль прав доступа проверяет наличие у пользователя полномочий для выполнения затребованной операции.

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

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

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

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

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

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

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

Процессор запросов преобразует SQL запросы в последовательность низкоуровневых инструкций для контроллера БД.

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

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

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

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

Перечислим и опишем основные функции современных СУБД:

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

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

Основными преимуществами ведения системного каталога являются:

контроль доступа к его данным, как к любому другому ресурсу БД;

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

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

протоколирование внесенных в БД изменений;

дополнительное усиление мер обеспечения безопасности;

новые возможности организации поддержки целостности данных;

аудит сохраняемой информации.

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

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

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

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

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

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

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

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

утилиты импортирования и экспортирования, предназначенные для загрузки и выгрузки БД в плоские файлы;

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

программы статистического анализа, позволяющие оценить производительность или степень использования БД;

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

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

1.5 ПРЕИМУЩЕСТВА И НЕДОСТАТКИ СУБД ПО СРАВНЕНИЮ С ФАЙЛОВЫМИ СИСТЕМАМИ

СУБД обладают существенными преимуществами по сравнению с файловыми системами, но имеют и недостатки [3].

Рассмотрим основные преимущества:

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

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

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

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

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

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

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

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

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

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

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

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

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

К недостаткам относятся:

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

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

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

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

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

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

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

1.6 ОРГАНИЗАЦИЯ ВНЕШНЕЙ ПАМЯТИ РЕЛЯЦИОННОЙ СУБД

СУБД обладает рядом особенностей, влияющих на организацию внешней памяти [4, 6]. К наиболее важным можно отнести следующие:

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

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

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

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

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

строки таблиц – основная часть БД, непосредственно видимая пользователям;

управляющие структуры – индексы, создаваемые из соображений повышения эффективности выполнения запросов и обычно автоматически поддерживаемые нижним уровнем системы;

журнал - специальный файл, поддерживаемый для удовлетворения потребности в надежном хранении данных;

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

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

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

Опишем основные принципы организации хранения кортежей.

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

Обычно каждый кортеж хранится целиком в одной странице. Из этого следует, что максимальная длина кортежа любой таблицы ограничена размерами страницы и возникает вопрос хранения «длинных» данных. Для его решения применяется несколько методов: хранение таких данных в отдельных файлах вне БД с заменой «длинного» данного в кортеже на имя соответствующего файла; хранение внутри БД в отдельном наборе страниц внешней памяти, связанном физическими ссылками; хранение в виде B-деревьев последовательностей байт.

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

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

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

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

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

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

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

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

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

Поиск в B-дереве – это прохождение от корня к листу в соответствии с заданным значением ключа. Заметим, что поскольку деревья сильноветвистые и сбалансированные, то для выполнения поиска по любому значению ключа потребуется одно и то же (и обычно небольшое) число обменов с внешней памятью. Более точно: если в сбалансированном дереве на внутренней странице помещается n ключей, то при хранении m записей требуется дерево глубиной logn(m), где logn – логарифм по основанию n. Если n достаточно велико, то глубина дерева невелика, и производится быстрый поиск.

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

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

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

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

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

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

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

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

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

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

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

1.7 Типы и структуры данных

Данные, хранящиеся непосредственно в памяти ЭВМ, представляют собой совокупность нулей и единиц (битов). Биты объединяются в последовательности: байты, слова и т.д. Каждому участку оперативной памяти, который может вместить один байт или слово, присваивается порядковый номер (адрес).

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

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

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

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

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

Данные простого типа – это символы, числа и т.п. элементы, дальнейшее дробление которых на составные части, большие, чем биты не имеет смысла.

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

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

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

Важный признак структуры данных − ее изменчивость − изменение числа элементов и (или) связей между элементами структуры. По признаку изменчивости различают структуры статические, полустатические, динамические, которые характерны для оперативной памяти и часто называются оперативными структурами. Файловые структуры соответствуют структурам данных для внешней памяти. Классификация структур данных по признаку изменчивости приведена на рис. 4.

Рис. 4. Классификация структур данных

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

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

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

логический тип BOOLEAN обычно содержит два значения - TRUE (истина) и FALSE (ложь). Несмотря на то, что для хранения значений этого типа теоретически достаточно одного бита, обычно переменные занимают один байт памяти. Над булевскими значениями возможны операции конъюнкции (& или AND), дизъюнкции (| или OR) и отрицания (~ или NOT).

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

Наряду со знаковыми целыми типами в языках часто поддерживаются беззнаковые целые. Для поддержки численных вычислений в языках обычно специфицируется встроенный тип чисел с плавающей точкой с базовым названием REAL или FLOAT.

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

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

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

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

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

Наиболее распространенные разновидности конструируемых типов – это типы массивов, записей и множеств.

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

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

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

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

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

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

1.8 Типы и структуры данных, применяемые в реляционных БД

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

Практически все современные реляционные СУБД опираются на стандартный язык БД − SQL и поддерживают встроенные типы данных, специфицированные в этом языке [5].

Значение любого типа является примитивным в том смысле, что в соответствии со стандартом оно не может быть логически разбито на другие значения. Значения могут быть определенными или неопределенными. Неопределенное значение – это зависящее от реализации значение, которое гарантированно отлично от любого определенного значения соответствующего типа. Можно считать, что имеется всего одно неопределенное значение, входящее в любой тип данных языка SQL. Для неопределенного значения отсутствует представляющий его литерал, хотя в некоторых случаях используется ключевое слово NULL для выражения того, что желательно именно неопределенное значение.

В стандарте SQL обычно определены типы данных, обозначаемые следующими ключевыми словами: CHARACTER, CHARACTER VARYING, BIT, BIT VARYING, NUMERIC, DECIMAL, INTEGER, SMALLINT, FLOAT, REAL, DOUBLE PRECISION, DATE, TIME, TIMESTAMP и INTERVAL.

Типы данных CHARACTER и CHARACTER VARYING называются типами данных символьных строк; типы данных BIT и BIT VARYING - типами данных битовых строк. Типы данных символьных и битовых строк совместно называются строчными типами данных, а значения строчных типов называются строками.

Типы данных NUMERIC, DECIMAL, INTEGER и SMALLINT совместно называются типами данных точных чисел. Типы данных FLOAT, REAL и DOUBLE PRECISION называются типами данных приблизительных чисел. Типы данных точных чисел и типы данных приблизительных чисел называются числовыми типами. Значения числовых типов называются числами.

Типы данных DATE, TIME и TIMESTAMP называются типами даты-времени. Значения типов даты-времени называются «дата-время».

Тип данных INTERVAL называется интервальным типом.

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

Важным понятием реляционных БД в стандарте языка SQL является понятие домена.

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

Значения всех упомянутых типов (и определенных на них доменов) имеют фиксированную или, по крайней мере, ограниченную длину. Даже для типов CHARACTER VARYING и BIT VARYING длина допустимого значения обычно ограничена размером страниц внешней памяти, используемых СУБД для хранения БД. В связи с потребностями современных приложений (географических, мультимедийных и т.д.) в большинстве СУБД поддерживается дополнительный, не специфицированный в стандарте SQL псевдотип данных BLOB (Binary Large Object). Значения этого типа представляют собой последовательности байт, на которые на уровне СУБД не накладывается более сложная структура и длина которых практически не ограничена (в 32-разрядных архитектурах − до 2 Гб). Традиционные СУБД обеспечивают очень примитивный набор операций со столбцами типа BLOB − выбрать значение столбца в основную память или в файл и занести в столбец значение из основной памяти или файла.

1.9 Типы и структуры данных, применяемые в объектно-реляционных БД

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

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

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

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

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

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

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

После полной спецификации объектного типа его можно использовать как встроенный или любой ранее определенный тип. В современных объектно-реляционных СУБД реализована полная возможность наследования объектных типов.

1.10 Понятие модели данных

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

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

Таким образом, любая модель данных содержит три основных компонента:

структура данных, которая описывает точку зрения пользователя на представление данных;

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

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

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

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

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

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

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

иерархическая,

сетевая,

реляционная,

объектно-реляционная,

объектно-ориентированная (объектная).

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

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


2. МОДЕЛИ ПРЕДСТАВЛЕНИЯ ДАННЫХ

 

2.1 ИЕРАРХИЧЕСКАЯ МОДЕЛЬ ДАННЫХ

 

Первые иерархические и сетевые СУБД появились в начале 60-х годов. Причиной создания послужила необходимость управления миллионами записей, связанных друг с другом иерархическим образом, например, при информационной поддержке лунного проекта Аполлон. Самая распространенная иерархическая СУБД - IMS (Information Management System) компании IBM. Первая версия системы появилась в 1968 году. Известны и другие иерархические системы: TDMS (Time-Shared Date Management System) компании Development Corporation; Mark IV Multi - Access Retrieval System компании Control Data Corporation; System - 2000разработки SAS-Institute [6].

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

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

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

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

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

При графическом изображении (диаграмма Бахмана) групповые отношения изображают дугами ориентированного графа, а типы записей – вершинами.

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

Пример 1. Рассмотрим модель данных предприятия (рис. 5): предприятие состоит из отделов, в которых работают сотрудники. В каждом отделе может работать несколько сотрудников, но сотрудник не может работать более чем в одном отделе.

Поэтому, для ИС управления персоналом необходимо создать групповое отношение, состоящее из родительской записи ОТДЕЛ (НАИМЕНОВАНИЕ_ОТДЕЛА, ЧИСЛО_РАБОТНИКОВ) и дочерней записи СОТРУДНИК (ФАМИЛИЯ, ДОЛЖНОСТЬ, ОКЛАД). Это отношение для двух дочерних записей показано на рис. 5 а.

Для автоматизации учета контрактов с заказчиками необходимо создание еще одной иерархической структуры: заказчик - контракты с ним - сотрудники, задействованные в работе над контрактом. Это дерево будет включать записи ЗАКАЗЧИК (НАИМЕНОВАНИЕ_ЗАКАЗЧИКА, АДРЕС), КОНТРАКТ (НОМЕР, ДАТА, СУММА), ИСПОЛНИТЕЛЬ (ФАМИЛИЯ, ДОЛЖНОСТЬ, НАИМЕНОВАНИЕ_ОТДЕЛА) (рис. 5 б).

 

Рис. 5 – Иерархическая модель данных

 

На рис. 5 хорошо видны недостатки иерархических БД:

1) Частично дублируется информация между записями СОТРУДНИК и ИСПОЛНИТЕЛЬ (такие записи называют парными), причем в иерархической модели данных не предусмотрена поддержка соответствия между ними.

2) Иерархическая модель реализует отношение «один ко многим» между исходной и дочерней записью, то есть одной родительской записи может соответствовать любое число дочерних. Допустим, что исполнитель может принимать участие более чем в одном контракте (т.е. возникает связь «многие ко многим»). В этом случае в БД необходимо ввести еще одно групповое отношение, в котором ИСПОЛНИТЕЛЬ будет являться исходной записью, а КОНТРАКТ – дочерней (рис. 5 в), что снова приведет к дублированию информации.

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

-ДОБАВИТЬ в БД новую запись. При этом для корневой записи обязательно формирование значения ключа.

-ИЗМЕНИТЬ значение данных предварительно извлеченной записи. При этом ключевые данные не должны подвергаться изменениям.

- УДАЛИТЬ некоторую запись и все подчиненные ей записи.

- ИЗВЛЕЧЬ: корневую запись по ключевому значению, следующую запись (извлекается в порядке левостороннего обхода дерева), допускается также последовательный просмотр корневых записей и задание условий выборки.

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

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

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

2.2 Сетевая модель данных

В конце 60-х годов конференция по языкам систем данных (Conference on Data Systems Languages, CODASYL) поручила подгруппе, названной Database Task Group (DTBG), разработать стандарт систем управления БД. На разработку этого стандарта большое влияние оказал американский ученый Ч. Бахман и архитектура, использованная в одной из самых первых СУБД – Integrated Data Store (IDS), созданной компанией General Electric. В результате в качестве стандарта была рекомендована сетевая модель данных [6].

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

Сетевая модель данных – это представление данных сетевыми структурами типов записей и связанных отношениями “один к одному” или “один ко многим”.

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

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

Иерархическая структура (рис. 5) преобразовывается в сетевую следующим образом (рис. 6):

деревья на рис. 5 a, б заменяются одной сетевой структурой, в которой запись СОТРУДНИК входит в два групповых отношения;

для отображения отношения «многие ко многим» (рис. 5 в), вводится запись СОТРУДНИК_КОНТРАКТ, которая в данном примере не имеет собственных полей (в этой записи может храниться и полезная информация, например, доля вознаграждения сотрудника по данному контракту) и служит только для связи записей КОНТРАКТ и СОТРУДНИК.

Рис. 6 – Сетевая модель данных

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

произвольный;

хронологический (очередь);

обратный хронологический (стек);

сортированный.

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

автоматический, когда невозможно занести в БД запись без того, чтобы она была сразу же закреплена за владельцем;

ручной, который позволяет запоминать в БД подчиненную запись,  не включая ее немедленно в экземпляр группового отношения;

режим исключения.

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

Фиксированное. Подчиненная запись жестко связана с записью владельцем и ее можно исключить из группового отношения, только удалив. При удалении записи-владельца все подчиненные записи тоже автоматически удаляются. В рассмотренном примере фиксированное членство предполагается между записями КОНТРАКТ и ЗАКАЗЧИК, поскольку контракт не может существовать без заказчика.

Обязательное. Допускается переключение подчиненной записи на другого владельца, но невозможно ее существование без владельца. Для удаления записи-владельца необходимо, чтобы она не имела подчиненных записей с обязательным членством. Таким отношением связаны записи СОТРУДНИК и ОТДЕЛ. Если отдел расформировывается, все его сотрудники должны быть либо переведены в другие отделы, либо уволены.

Необязательное. Можно исключить запись из группового отношения, но сохранить ее в БД, не прикрепляя к другому владельцу. Примером может служить связь между записями СОТРУДНИК и КОНТРАКТ, поскольку в организации могут существовать работники, чья деятельность не связана с выполнением каких-либо договорных обязательств перед заказчиками.

Операции над данными, определенные в сетевой модели:

ДОБАВИТЬ - внести запись в БД и, в зависимости от режима включения, либо включить ее в групповое отношение, где она объявлена подчиненной, либо не включать ни в какое групповое отношение.

ВКЛЮЧИТЬ В ГРУППОВОЕ ОТНОШЕНИЕ - связать существующую подчиненную запись с записью-владельцем.

ПЕРЕКЛЮЧИТЬ - связать существующую подчиненную запись с другой записью-владельцем в том же групповом отношении.

ОБНОВИТЬ - изменить значение элементов предварительно извлеченной записи.

ИЗВЛЕЧЬ - извлечь записи последовательно по значению ключа, а также, используя групповые отношения,  от владельца можно перейти к записям-членам, а от подчиненной записи к владельцу набора.

УДАЛИТЬ - убрать из БД запись. Если эта запись является владельцем группового отношения, то анализируется класс членства подчиненных записей. Обязательные члены должны быть предварительно исключены из группового отношения, фиксированные удалены вместе с владельцем, необязательные останутся в БД.

ИСКЛЮЧИТЬ ИЗ ГРУППОВОГО ОТНОШЕНИЯ - разорвать связь между записью-владельцем и записью-членом.

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

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

В 1970-1971 годах Е. Ф. Кодд опубликовал две статьи, в которых впервые ввел понятия реляционной модели данных и реляционных языков обработки данных - реляционной алгебры и реляционного исчисления.

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

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

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

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

Рис. 7.- Основные компоненты реляционного отношения

Рассмотрим основные понятия реляционной модели данных [3, 4, 6].

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

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

Атрибут отношения – это пара вида «имя_атрибута, имя_домена». Имена атрибутов должны быть уникальны в пределах отношения. Часто имена атрибутов отношения совпадают с именами соответствующих доменов.

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

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

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

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

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

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

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

В целом в реляционных моделях используются следующие виды реляционных ключей:

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

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

Первичный ключ – потенциальный ключ, который выбран для уникальной идентификации кортежей внутри отношения.

Альтернативный ключ – потенциальный ключ, не являющийся первичным ключом.

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

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

Заголовок отношения содержит фиксированное количество атрибутов отношения. Он описывает декартово произведение доменов, на котором задано отношение. Заголовок статичен, он не меняется во время работы с БД. Если в отношении изменены, добавлены или удалены атрибуты, то в результате получим уже другое отношение (пусть даже с прежним именем).

Набор заголовков отношений, входящих в БД называется схемой реляционной БД.

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

Число атрибутов в отношении называют степенью (или -арностью) отношения.

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

Таким образом, реляционной БД называется набор отношений.

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

Рис. 8 - Пример реляционной модели данных

2.4 Свойства отношений. Отличие отношений от таблиц.

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

Сформулируем фундаментальные свойства отношений [6].

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

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

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

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

2.5 Понятие целостности данных

 

При описании реляционной модели использовалась наиболее распространенная трактовка, которая принадлежит К. Дейту. Также согласно Дейту, реляционная модель состоит из трех частей [6, 7]:

структурной части,

целостной части,

манипуляционной части.

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

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

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

Помимо этого задаются 3 группы правил целостности, которые являются ограничениям для всех допустимых состояний БД:

целостность сущностей (отношений),

целостность внешних ключей,

целостность, которая определяется пользователем.

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

NULL указывает, что значение атрибута в настоящий момент неизвестно. Его не следует воспринимать как логическую величину “неизвестно” (никакое значение еще не задано) или понимать как нулевое численное значение или заполненную пробелами текстовую строку. Нули и пробелы представляют собой некоторые значения, тогда как ключевое слово NULL призвано обозначать отсутствие какого-либо значения.

По определению, первичный ключ (primary key) - это уникальный идентификатор кортежей отношения. Это значит, что никакое подмножество ключа не может быть достаточным для уникальной идентификации кортежей. Если допустить присутствие значения NULL в любой части первичного ключа, это равноценно утверждению, что не все его атрибуты необходимы для идентификации, что противоречит определению.

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

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

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

Корпоративные ограничения целостности - это дополнительные правила поддержки целостности данных, определяемые пользователями или администраторами БД.

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

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

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

Таблица 1

Реляционный термин

Табличный термин

База данных

Набор таблиц

Схема базы данных

Набор заголовков таблиц

Отношение

Таблица

Заголовок отношения

Заголовок таблицы

Тело отношения

Тело таблицы

Атрибут отношения

Наименование столбца таблицы (столбец, поле)

Кортеж отношения

Строка таблицы (запись)

Степень (-арность) отношения

Количество столбцов таблицы

Мощность отношения

Количество строк таблицы

Домены и типы данных

Типы данных в ячейках таблицы

Также следует понимать, что обычно строка или запись означает на самом деле «экземпляр записи», а атрибут или поле – имя и тип поля.

2.6 Ограничения реляционных баз данных

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

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

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

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

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

Обойти эти ограничения можно было бы в том случае, если бы реляционная модель допускала:

возможность определения новых типов данных;

определение наборов операций, связанных с данными определенного типа.

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

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

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

Первые работы, в которых отмечались эти и ряд других недостатков, появились уже в начале 80-х годов. Одна из наиболее ярких статей была опубликована в 1990 г. – Системы баз данных третьего поколения: Манифест. Вслед за первым манифестом последовали Манифест систем объектно-ориентированных баз данных. (М. Аткинсон, Ф. Бансилон, Д. ДеВитт, К. Диттрих, Д. Майер, С.Здоник, СУБД № 4 1995) и Третий манифест (Х.Дарвин, К.Дэйт, СУБД № 1 1996).

2.7 Суть постреляционного объектно-ориентированного подхода

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

Существует множество постреляционных СУБД, но одними из первых появились Adabas, Pick и Universe.

Термин «объект» в программной индустрии впервые был введен в языке Simula (1967 г.) и означал какой-либо аспект моделируемой реальности. Сейчас под объектом понимается «нечто, имеющее четко определенные границы» (определение известного американского специалиста Г.Буча). Объекты, обладающие одинаковыми свойствами, составляют классы. Обычно класс описывается как новый тип данных, а объекты (экземпляры класса) как определенные на его основе переменные.

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

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

Структура объектно-ориентированной модели описываются с помощью трех ключевых понятий:

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

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

полиморфизм – различные объекты могут по-разному реагировать на одинаковые внешние события в зависимости от того, как реализованы их методы.

Для поддержания целостности объектно-ориентированный подход предлагает использовать следующие средства:

автоматическое поддержание отношений наследования;

возможность объявить некоторые поля данных и методы объекта как «скрытые», не видимые для других объектов; такие поля и методы используются только методами самого объекта;

создание процедур контроля целостности внутри объекта.

К сожалению, в объектно-ориентированном программировании отсутствуют общие средства манипулирования данными, такие как реляционная алгебра или реляционное исчисление. Поэтому работа с данными ведется с помощью одного из объектно-ориентированных языков программирования общего назначения, обычно это SmallTalk, C++ или Java, что значительно усложняет процесс работы с данными. Так все запросы приходится писать на процедурных языках, и проблема их оптимизации возлагается на программиста. Вместо чисто декларативных ограничений целостности (типа явного объявления первичных и внешних ключей реляционных таблиц) или полудекларативных триггеров для обеспечения внутренней целостности также приходится писать процедурный код.

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

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

расширение объектно-ориентированных языков в сторону управления данными (стандарт ODMG)  и развитие так называемых объектно-ориентированных СУБД (ОО СУБД);

добавление объектных свойств в реляционные СУБД (стандарт SQL-3) и развитие объектно-реляционных СУБД (ОР СУБД).

2.8 Объектно-ориентированные СУБД и стандарт ODMG

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

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

ObjectStore поддерживает транзакции (в один момент времени может существовать только одна транзакция), допускает следующие методы доступа: хеш-таблица для несортированных данных и B-дерево для сортированных, также возможно использование SQL.

ODMG (Object Data Management Group) – консорциум поставщиков ОО БД и других заинтересованных организаций, созданный в 1991 г. Его задачей является разработка стандарта на хранение объектов в БД. Рассмотрим кратко основные положения этого документа.

Стандарт на хранение объектов ODMG разработан на основе трех существующих стандартов: языка управления БД (SQL), языка управления объектами (стандарты OMG – Object Management Group) и стандарты на ОО языки программирования (C++, Smalltalk, Java).

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

Объектная модель – унифицированная основа всего стандарта. Она расширяет объектную модель консорциума OMG за счет введения таких свойств как связи и транзакции для обеспечения функциональности, требуемой при взаимодействии с БД. Ключевые концепции объектной модели ODMG:

наделение объектов такими свойствами как атрибуты и связи;

методы объектов (поведение);

множественное наследование;

идентификаторы объектов (ключи);

определение таких совокупностей объектов как списки, наборы, массивы и т.д.

блокировка объектов и изоляция доступа.

Язык описания объектов (ODL - Object Defifnition Language) – средство определения схемы БД (по аналогии с DDL в реляционных СУБД). ODL является расширением IDL (Interface Definition Language - язык описания интерфейсов) модели OMG и предоставляет средства для определения объектных типов, их атрибутов, связей и методов. ODL создает слой абстрактных описаний так, что схема БД становится независима как от языка программирования, так и от СУБД. ODL рассматривает только описание объектных типов данных, не вдаваясь в детали реализации их методов. Это позволяет переносить схему БД между различными ODMG-совместимыми СУБД и языками программирования, а также транслировать ее в другие DDL.

Язык объектных запросов (OQL - Object Query Language) – это SQL-подобный декларативный язык, который предоставляет эффективные средства для извлечения объектов из БД, включая высокоуровневые примитивы для наборов объектов и объектных структур. OQL-запросы могут вызываться из ОО языка, точно также из OQL-запросов могут делаться обращения к процедурам, написанным на OO языке. OQL предоставляет средства обеспечения целостности объектов (вызов объектных методов и использование собственных операторов изменения данных).

Связывание с ОО языками. Стандарт связывания с C++, Smalltalk и Java определяет Object Manipulation Language (OML) - язык манипулирования объектами, который расширяет базовые ОО языки средствами манипулирования и хранения объектов. Также включаются OQL, средства навигации и поддержка транзакций. Каждый ОО язык имеет свой собственный OML, поэтому разработчик остается в одной языковой среде, ему нет необходимости разделять средства программирования и доступа к данным.

2.9 Объектно-реляционные СУБД

Этот способ объединения возможностей реляционного и объектно-ориентированного подхода к управлению данными предложил известный американский ученый Майкл Стоунбрейкер [6]. Согласно его воззрениям реляционную СУБД нужно просто дополнить средствами доступа к сложным данным. При этом ядро СУБД не требует переработки и сохраняет все присущие реляционным системам достоинства. Объектные расширения реализуются в виде надстроек, которые динамически подключаются к ядру. На основе этой идеи под руководством М. Стоунбрейкера в университете Беркли (Калифорния, США) была разработана СУБД Postgres, которая имеет следующие ключевые возможности.

Типы, операторы и методы доступа, определяемые пользователем. Для решения проблем с примером о хранении земельных участков, можно определить новый тип данных «участок», необходимые операции над ним (например, вычисление площади), а также метод доступа, поскольку с помощью B-дерева нельзя выполнить двумерный поиск в задаче о перекрывающихся многоугольниках. Здесь целесообразно использовать дерево более высокой размерности (R-дерево) или другие методы.

Поддержка сложных объектов, представляющих собой наборы других объектов.

Перегрузка операторов манипулирования данными.

Создание функций, определяемых пользователем.

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

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

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

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

Все вышеописанные функции развиваются и в коммерческой СУБД Informix. Тем не менее, проект Postgres продолжается до сих пор, уже международной группой независимых разработчиков. К возможностям СУБД была добавлена поддержка SQL, поэтому несколько было изменено название – PostgreSQL, оптимизатор запросов на основе генетических алгоритмов и многое другое. При этом PostgreSQL остается свободно распространяемой системой, причем бесплатно можно получить как исходный код, так и бинарные файлы, собранные для той или иной платформы (поддерживаются практически все разновидности ОС Unix).


3. Проектирование р
еляционных БД

3.1 Этапы разработки базы данных

Существует два подхода к проектированию реляционных БД [8].

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

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

Целью разработки любой БД является хранение и использование информации о какой-либо предметной области. Для реализации этой цели имеются следующие инструменты: реляционная модель данных – удобный способ представления данных предметной области и язык SQL – универсальный способ манипулирования такими данными.

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

анализ предметной области;

модель предметной области;

логическая модель данных;

физическая модель данных;

собственно БД и приложения.

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

Модель предметной области. Модель предметной области – это отражение наших знаний о предметной области. Знания могут быть как в виде неформальных суждений в голове эксперта, так и выражены формально при помощи каких-либо средств. В качестве таких средств могут выступать текстовые описания предметной области, наборы должностных инструкций, правила ведения дел в компании и т.п. Опыт показывает, что текстовый способ представления модели предметной области крайне неэффективен. Гораздо более информативными и полезными при разработке БД являются описания предметной области, выполненные при помощи специализированных графических нотаций. Имеется большое количество графических методик описания предметной области. Из наиболее известных можно назвать следующие: метод структурного анализа (SADT) и основанные на нем IDEF0, IDEF1 диаграммы, диаграммы потоков данных Гейна-Сарсона, метод объектно-ориентированного анализа (UML) и др. От того, насколько правильно смоделирована предметная область, зависит успех дальнейшей разработки приложений и БД.

Логическая модель данных. На следующем, более низком уровне находится логическая модель данных предметной области. Логическая модель описывает понятия предметной области, их взаимосвязь, а также ограничения на данные, налагаемые предметной областью. Примеры понятий: «сотрудник», «отдел», «проект», «зарплата». Примеры взаимосвязей между понятиями: «сотрудник числится ровно в одном отделе», «сотрудник может выполнять несколько проектов», «над одним проектом может работать несколько сотрудников". Примеры ограничений: «возраст сотрудника не менее 16 и не более 60 лет», «дата поставки не может быть меньше текущей даты», «в поле могут быть только перечисленные в списке значения».

Логическая модель данных является начальным прототипом будущей БД. Логическая модель строится в терминах информационных единиц, но без привязки к конкретной СУБД. Более того, логическая модель данных необязательно должна быть выражена средствами именно реляционной модели данных. Основным средством разработки логической модели данных являются различные варианты ER-диаграмм (Entity-Relationship). Одну и ту же ER-модель можно преобразовать как в реляционную модель данных, так и в модель данных для иерархических и сетевых СУБД, или в постреляционную модель данных. Однако, т.к. мы рассматриваем именно реляционные СУБД, то можно считать, что логическая модель данных для нас формулируется в терминах реляционной модели данных.

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

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

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

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

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

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

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

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

3.2 Критерии оценки качества логической модели данных

Рассмотрим некоторые принципы построения хороших логических моделей данных [8]. Хороших в том смысле, что решения, принятые в процессе логического проектирования приводили бы к хорошим физическим моделям и в конечном итоге к хорошей работе БД.

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

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

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

состояние БД в каждый момент времени должно соответствовать состоянию предметной области;

изменение состояния предметной области должно приводить к соответствующему изменению состояния БД;

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

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

Хранимые процедуры – это процедуры и функции, хранящиеся непосредственно в БД в откомпилированном виде и которые могут запускаться пользователями или приложениями, работающими с БД. Хранимые процедуры обычно пишутся либо на специальном процедурном расширении языка SQL (например, PL/SQL для ORACLE или Transact-SQL для MS SQL Server), или на некотором универсальном языке программирования, например, C++, с включением в код операторов SQL в соответствии со специальными правилами такого включения. Основное назначение хранимых процедур – реализация бизнес-процессов предметной области.

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

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

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

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

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

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

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

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

3.3 Проектирование баз данных на основе нормализации отношений

 

Рассмотрим классический подход, при котором процесс проектирования БД производится в терминах реляционной модели данных методом последовательных приближений к удовлетворительному набору схем отношений [7, 8, 12].

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

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

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

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

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

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

первая нормальная форма (1NF);

вторая нормальная форма (2NF);

третья нормальная форма (3NF);

нормальная форма Бойса-Кодда (BCNF);

четвертая нормальная форма (4NF);

пятая нормальная форма, или нормальная форма проекции-соединения (5NF или PJ/NF).

В качестве общих свойств для всех нормальных форм можно отметить:

каждая следующая нормальная форма в некотором смысле лучше предыдущей;

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

3.4 Первая нормальная форма

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

в отношении нет одинаковых кортежей;

кортежи не упорядочены;

атрибуты не упорядочены и различаются по наименованию;

все значения атрибутов атомарны.

Пример 2. Рассмотрим в качестве примера предметной области организацию, выполняющую некоторые проекты [8]. Модель предметной области опишем следующим неформальным текстом:

Сотрудники организации выполняют проекты.

Проекты состоят из нескольких заданий.

Каждый сотрудник может участвовать в одном или нескольких проектах, или временно не участвовать ни в каких проектах.

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

Над каждым заданием в проекте работает только один сотрудник.

Каждый сотрудник числится в одном отделе.

Каждый сотрудник имеет телефон, находящийся в отделе сотрудника.

Также допустим, что в ходе уточнения того, какие данные необходимо учитывать, выяснились следующие факты.

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

Каждый отдел имеет уникальный номер.

Каждый проект имеет уникальный номер и наименование.

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

В ходе логического моделирования на первом шаге предложено хранить данные в одном отношении СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ (Н_СОТР, ФАМ, Н_ОТД, ТЕЛ, Н_ПРО, ПРОЕКТ, Н_ЗАДАН), имеющем следующие атрибуты:

Н_СОТР – табельный номер сотрудника;

ФАМ – фамилия сотрудника;

Н_ОТД – номер отдела, в котором числится сотрудник;

ТЕЛ – телефон сотрудника;

Н_ПРО – номер проекта, над которым работает сотрудник;

ПРОЕКТ – наименование проекта, над которым работает сотрудник;

Н_ЗАДАН – номер задания, над которым работает сотрудник.

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

Пусть в текущий момент состояние предметной области отражается нижеследующими фактами в табл. 2.

Сотрудник Иванов, работающий в 1 отделе, выполняет в первом проекте "Космос" задание 1 и во втором проекте "Климат" задание 1.

Сотрудник Петров, работающий в 1 отделе, выполняет в первом проекте "Космос" задание 2.

Сотрудник Сидоров, работающий во 2 отделе, выполняет в первом проекте "Космос" задание 3 и во втором проекте "Климат" задание 2.

Таблица 2. СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ

Н_СОТР

ФАМ

Н_ОТД

ТЕЛ

Н_ПРО

ПРОЕКТ

Н_ЗАДАН

1

Иванов

1

11-22-33

1

Космос

1

1

Иванов

1

11-22-33

2

Климат

1

2

Петров

1

11-22-33

1

Космос

2

3

Сидоров

2

33-22-11

1

Космос

3

3

Сидоров

2

33-22-11

2

Климат

2

3.5 Аномалии обновления

Даже одного взгляда на табл. 2 СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ достаточно, чтобы увидеть, что данные хранятся в ней с большой избыточностью. Во многих строках повторяются фамилии сотрудников, номера телефонов, наименования проектов. Кроме того, в данном отношении хранятся вместе независимые друг от друга данные о сотрудниках, об отделах, о проектах и о работах по проектам. Пока никаких действий с отношением не производится, это не страшно. Но как только состояние предметной области изменяется, то, при попытках соответствующим образом изменить состояние БД, возникает большое количество проблем.

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

Различают следующие виды аномалий:

аномалии вставки (INSERT);

аномалии обновления (UPDATE);

аномалии удаления (DELETE).

Рассмотрим примеры аномалий в отношении СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ.

Аномалии вставки (INSERT). В отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ нельзя вставить данные о сотруднике, который пока не участвует ни в одном проекте. Действительно, если, например, во втором отделе появляется новый сотрудник, скажем, Пушников, и он пока не участвует ни в одном проекте, то мы должны вставить в отношение кортеж (4, Пушников, 2, 33-22-11, null, null, null). Это сделать невозможно, т.к. атрибут Н_ПРО (номер проекта) входит в состав потенциального ключа, и, следовательно, не может содержать null-значений. Точно также нельзя вставить данные о проекте, над которым пока не работает ни один сотрудник.

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

Аномалии удаления (DELETE). При удалении некоторых данных может произойти потеря другой информации. Например, если закрыть проект "Космос" и удалить все строки, в которых он встречается, то будут потеряны все данные о сотруднике Петрове. Если удалить сотрудника Сидорова, то будет потеряна информация о том, что в отделе номер 2 находится телефон 33-22-11. Если по проекту временно прекращены работы, то при удалении данных о работах по этому проекту будут удалены и данные о самом проекте. При этом если бы был сотрудник, который работал только над этим проектом, то будут потеряны и данные об этом сотруднике.

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

3.6 Функциональные зависимости

Отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ находится в 1NF, но при этом, логическая модель данных не адекватна модели предметной области. Таким образом, первой нормальной формы недостаточно для правильного моделирования данных и для устранения указанных аномалий применяется метод нормализации отношений.

Нормализация основана на понятии функциональной зависимости атрибутов отношения.

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

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

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

Пример. В отношении СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ можно привести следующие примеры функциональных зависимостей:

  •  зависимость атрибутов от ключа отношения:

(Н_СОТР, Н_ПРО)ФАМ;

(Н_СОТР, Н_ПРО)Н_ОТД;

(Н_СОТР, Н_ПРО)ТЕЛ;

(Н_СОТР, Н_ПРО)ПРОЕКТ;

(Н_СОТР, Н_ПРО)Н_ЗАДАН;

  •  зависимость атрибутов, характеризующих сотрудника от табельного номера сотрудника: Н_СОТР ФАМ; Н_СОТРН_ОТД; Н_СОТРТЕЛ;
  •  зависимость наименования проекта от номера проекта: Н_ПРОПРОЕК;
  •  зависимость номера телефона от номера отдела: Н_ОТДТЕЛ.

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

Функциональная зависимость атрибутов отношения напоминает понятие функциональной зависимости в математике. Но это не одно и то же.

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

Например, атрибут ФАМ функционально зависит от атрибута Н_СОТР. Предположим, что сейчас сотрудница с табельным номером 1 имеет фамилию Иванова, т.е. при значении детерминанта равного 1, значение зависимого аргумента равно «Иванова». Но сотрудница может сменить фамилию, например на Сидорова. Теперь при том же значении детерминанта, равного 1, значение зависимого аргумента равно «Сидорова».

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

 

3.7 Вторая нормальная форма

 

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

Если потенциальный ключ отношения является простым, то отношение автоматически находится в 2NF.

Отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ не находится в 2NF, т.к. есть атрибуты, зависящие от части сложного ключа:

-     зависимость атрибутов, характеризующих сотрудника от табельного номера сотрудника:

Н_СОТРФАМ;

Н_СОТРН_ОТД;

Н_СОТРТЕЛ;

-     зависимость наименования проекта от номера проекта:

Н_ПРОПРОЕКТ.

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

Отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ необходимо разбить на три отношения –  СОТРУДНИКИ_ОТДЕЛЫ, ПРОЕКТЫ, ЗАДАНИЯ:

1.  Отношение СОТРУДНИКИ_ОТДЕЛЫ (Н_СОТР, ФАМ, Н_ОТД, ТЕЛ) приведено в табл. 3:

 

Таблица 3. – Отношение СОТРУДНИКИ_ОТДЕЛЫ

Н_СОТР

ФАМ

Н_ОТД

ТЕЛ

1

Иванов

1

11-22-33

2

Петров

1

11-22-33

3

Сидоров

2

33-22-11

 

В отношении присутствуют следующие функциональные зависимости:

-     зависимость атрибутов, характеризующих сотрудника, от табельного номера сотрудника:

Н_СОТРФАМ;

Н_СОТРН_ОТД;

Н_СОТРТЕЛ;

-     зависимость номера телефона от номера отдела: Н_ОТДТЕЛ.

Отношение ПРОЕКТЫ (Н_ПРО, ПРОЕКТ) приведено в табл. 4:

 

Таблица  4. – Отношение ПРОЕКТЫ

Н_ПРО

ПРОЕКТ

1

Космос

2

Климат

 

Функциональная зависимость: Н_ПРОПРОЕКТ.

2.  Отношение ЗАДАНИЯ (Н_СОТР, Н_ПРО, Н_ЗАДАН) приведено в табл. 5.

 

Таблица 5. – Отношение ЗАДАНИЯ

Н_СОТР

Н_ПРО

Н_ЗАДАН

1

1

1

1

2

1

2

1

2

3

1

3

3

2

2

 

Функциональная зависимость: (Н_СОТР, Н_ПРО)Н_ЗАДАН.

Анализ декомпозированных отношений на аномалии. Отношения, полученные в результате декомпозиции, находятся в 2NF. Действительно, отношения СОТРУДНИКИ_ОТДЕЛЫ и ПРОЕКТЫ имеют простые ключи, следовательно, автоматически находятся в 2NF, отношение ЗАДАНИЯ имеет сложный ключ, но единственный неключевой атрибут Н_ЗАДАН функционально зависит от всего ключа (Н_СОТР, Н_ПРО).

Часть аномалий обновления устранена. Так, данные о сотрудниках и проектах теперь хранятся в различных отношениях, поэтому при появлении сотрудников, не участвующих ни в одном проекте просто добавляются кортежи в отношение СОТРУДНИКИ_ОТДЕЛЫ. Точно также, при появлении проекта, над которым не работает ни один сотрудник, вставляется кортеж в отношение ПРОЕКТЫ.

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

Если по проекту временно прекращены работы, но требуется, чтобы сам проект сохранился, то для этого проекта удаляются соответствующие кортежи в отношении ЗАДАНИЯ, а данные о самом проекте и данные о сотрудниках, участвовавших в проекте, остаются в отношениях ПРОЕКТЫ и СОТРУДНИКИ_ОТДЕЛЫ.

Тем не менее, часть аномалий разрешить не удалось.

Оставшиеся аномалии вставки (INSERT). В отношение СОТРУДНИКИ_ОТДЕЛЫ нельзя вставить кортеж (4, Пушников, 1, 33-22-11), т.к. при этом получится, что два сотрудника из 1-го отдела (Иванов и Пушников) имеют разные номера телефонов, а это противоречит модели предметной области. В этой ситуации можно предложить два решения, в зависимости от того, что реально произошло. Другой номер телефона может быть введен по двум причинам по ошибке человека, вводящего данные о новом сотруднике, или потому что номер в отделе действительно изменился. В любом случае необходимо написать триггер, который при вставке записи о сотруднике проверяет, совпадает ли телефон с уже имеющимся телефоном у другого сотрудника этого же отдела. Если номера отличаются, то система должна задать вопрос, оставить ли старый номер в отделе или заменить его новым. Если нужно оставить старый номер (новый номер введен ошибочно), то кортеж с данными о новом сотруднике будет вставлен, но номер телефона будет у него тот, который уже есть в отделе (в данном случае, 11-22-33). Если же номер в отделе действительно изменился, то кортеж будет вставлен с новым номером, и одновременно будут изменены номера телефонов у всех сотрудников этого же отдела.

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

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

Оставшиеся аномалии удаления (DELETE). При удалении некоторых данных по-прежнему может произойти потеря другой информации. Например, если удалить сотрудника Сидорова, то будет потеряна информация о том, что в отделе номер 2 находится телефон 33-22-11.

В итоге, логическая модель данных снова неадекватна модели предметной области и БД, основанная на такой модели, будет работать неправильно.

Заметим, что при переходе к 2NF отношения стали почти адекватными предметной области. Остались трудности, связанные с необходимостью написания триггеров, поддерживающих целостность БД, и они связаны только с одним отношением СОТРУДНИКИ_ОТДЕЛЫ.

 

3.8 Третья нормальная форма

 

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

Отношение  находится в третьей нормальной форме (3NF) тогда и только тогда, когда отношение находится в 2NF и все неключевые атрибуты взаимно независимы.

Отношение СОТРУДНИКИ_ОТДЕЛЫ не находится в 3NF, т.к. имеется функциональная зависимость неключевых атрибутов (зависимость номера телефона от номера отдела): Н_ОТДТЕЛ.

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

Отношение СОТРУДНИКИ_ОТДЕЛЫ нужно декомпозировать на два отношения – СОТРУДНИКИ и ОТДЕЛЫ.

Отношение СОТРУДНИКИ (Н_СОТР, ФАМ, Н_ОТД) включает следующие функциональные зависимости: Н_СОТРФАМ, Н_СОТРН_ОТД, Н_СОТРТЕЛ.

 

Таблица 6. – Отношение СОТРУДНИКИ

Н_СОТР

ФАМ

Н_ОТД

1

Иванов

1

2

Петров

1

3

Сидоров

2

 

Отношение ОТДЕЛЫ (Н_ОТД, ТЕЛ) включает функциональную зависимость номера телефона от номера отдела: Н_ОТДТЕЛ.

 

Таблица 7. – Отношение ОТДЕЛЫ

Н_ОТД

ТЕЛ

1

11-22-33

2

33-22-11

 

Отметим, что атрибут Н_ОТД, не являвшийся ключевым в отношении СОТРУДНИКИ_ОТДЕЛЫ, становится потенциальным ключом в отношении ОТДЕЛЫ. Именно за счет этого устраняется избыточность, связанная с многократным хранением одних и тех же номеров телефонов.

Таким образом, все обнаруженные аномалии обновления устранены. Реляционная модель данных, состоящая из четырех отношений - СОТРУДНИКИ, ОТДЕЛЫ, ПРОЕКТЫ, ЗАДАНИЯ, находится в 3NF, является адекватной описанной модели предметной области и предполагает наличие только тех триггеров, которые поддерживают ссылочную целостность. Такие триггеры являются стандартными и не требуют больших усилий в разработке.

3.9 Алгоритм нормализации (приведение к 3NF)

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

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

Исходное отношение: .

Ключ:  – сложный.

Функциональные зависимости:

– зависимость всех атрибутов от ключа отношения.

– зависимость некоторых атрибутов от части сложного ключа.

Декомпозированные отношения:

– остаток от исходного отношения. Ключ .

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

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

Исходное отношение: . Ключ: .

Функциональные зависимости:

– зависимость всех атрибутов от ключа отношения.

– зависимость некоторых неключевых атрибутов от других неключевых атрибутов.

Декомпозированные отношения:

– остаток от исходного отношения. Ключ .

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

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

Во-первых, этот алгоритм показывает, какие проблемы возникают при разработке слабо нормализованных отношений.

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

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

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

3.10 OLTP и OLAP-системы

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

Сильно нормализованные модели данных хорошо подходят для так называемых OLTP-приложений (On-Line Transaction Processing – оперативная обработка транзакций). Типичными примерами OLTP-приложений являются системы складского учета, системы заказов билетов, банковские системы, выполняющие операции по переводу денег и т.п. Основная функция подобных систем заключается в выполнении большого количества коротких транзакций. Сами транзакции выглядят относительно просто, например, «снять сумму денег со счета А, добавить эту сумму на счет В». Проблема заключается в том, что, во-первых, транзакций очень много, во-вторых, они выполняются одновременно (к системе может быть подключено несколько тысяч одновременно работающих пользователей), в-третьих, при возникновении ошибки, транзакция должна целиком откатиться и вернуть систему к состоянию, которое было до начала транзакции (не должно быть ситуации, когда деньги сняты со счета А, но не поступили на счет В). Практически все запросы к БД в OLTP-приложениях состоят из команд вставки, обновления, удаления. Запросы на выборку в основном предназначены для предоставления пользователям возможности выбора информации из различных справочников системы. Большая часть таких запросов, как правило, известна заранее, еще на этапе проектирования системы.

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

Другим типом приложений являются так называемые OLAP-приложения (On-Line Analitical Processing – оперативная аналитическая обработка данных). Это обобщенный термин, характеризующий принципы построения систем поддержки принятия решений (Decision Support System – DSS), хранилищ данных (Data Warehouse), систем интеллектуального анализа данных (Data Mining). Такие системы предназначены для нахождения зависимостей между данными (например, можно попытаться определить, как связан объем продаж товаров с характеристиками потенциальных покупателей), для проведения анализа типа «что если…?». OLAP-приложения оперируют с большими массивами данных, уже накопленными в OLTP-приложениях, взятыми из электронных таблиц или из других источников данных. Такие системы характеризуются следующими общими признаками:

добавление в систему новых данных происходит относительно редко крупными блоками (например, раз в квартал загружаются данные по итогам квартальных продаж из OLTP-приложения);

данные, добавленные в систему, обычно никогда не удаляются;

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

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

скорость выполнения запросов важна, но не критична.

Данные OLAP-приложений обычно представлены в виде одного или нескольких гиперкубов, измерения которого представляют собой справочные данные, а в ячейках самого гиперкуба хранятся собственно данные. Например, можно построить гиперкуб, измерениями которого являются: время (в кварталах, годах), тип товара и отделения компании, а в ячейках хранятся объемы продаж. Такой гиперкуб будет содержать данных о продажах различных типов товаров по кварталам и подразделениям. Основываясь на этих данных, можно отвечать на вопросы типа «у какого подразделения самые лучшие объемы продаж в текущем году?», или «каковы тенденции продаж отделений Юго-Западного региона в текущем году по сравнению с предыдущим годом?».

Физически гиперкуб может быть построен на основе специальной многомерной модели данных (MOLAP - Multidimensional OLAP) или средствами реляционной модели данных (ROLAP - Relational OLAP).

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

3.11 Корректность процедуры нормализации. Теорема Хеза

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

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

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

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

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

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

Таблица 8. – Отношение

Номер

Фамилия

Зарплата

1

Иванов

1000

2

Петров

1000

Рассмотрим первый вариант декомпозиции отношения  на два отношения:

Таблица 9. – Отношение

Таблица 10. – Отношение

Номер

Зарплата

1

1000

2

1000

Фамилия

Зарплата

Иванов

1000

Петров

1000

Естественное соединение этих проекций, имеющих общий атрибут Зарплата, будет следующим (каждая строка одной проекции соединится с каждой строкой другой проекции):

Таблица 11. – Отношение

Номер

Фамилия

Зарплата

1

Иванов

1000

1

Петров

1000

2

Иванов

1000

2

Петров

1000

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

Рассмотрим другой вариант декомпозиции:

Таблица 12. – Отношение

Таблица 13. – Отношение

Номер

Фамилия

1

Иванов

2

Петров

Номер

Зарплата

1

1000

2

1000

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

Таблица 14. – Отношение в новом состоянии

Номер

Фамилия

Зарплата

1

Иванов

1000

2

Петров

1000

2

Сидоров

2000

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

Таблица 15. – Отношение

Таблица 16. – Отношение

Номер

Фамилия

1

Иванов

2

Петров

2

Сидоров

Номер

Зарплата

1

1000

2

1000

2

2000

Естественное соединение этих проекций снова будет содержать лишние кортежи:

 

Таблица 17. – Отношение

Номер

Фамилия

Зарплата

1

Иванов

1000

2

Петров

1000

2

Петров

2000

2

Сидоров

1000

2

Сидоров

2000

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

Такими дополнительными ограничениями и являются функциональные зависимости. Имеет место следующая теорема Хеза:

Пусть является отношением, и  − атрибуты или множества атрибутов этого отношения. Если имеется функциональная зависимость , то проекции  и  образуют декомпозицию без потерь.

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

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

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

3.12 Нормальная Форма Бойса-Кодда (NFBK)

 

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

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

 

Таблица 18. – Отношение ПОСТАВКИ

PNUM

PNAME

DNUM

VOLUME

1

Фирма 1

1

100

1

Фирма 1

2

200

1

Фирма 1

3

300

2

Фирма 2

1

150

2

Фирма 2

2

250

3

Фирма 3

1

1000

 

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

-     PNUMPNAME – наименование поставщика зависит от номера поставщика;

-     PNAMEPNUM – номер поставщика зависит от наименования поставщика;

-     (PNUM, DNUM)VOLUME – поставляемое количество зависит от первого ключа отношения;

-     (PNUM, DNUM)PNAME – наименование поставщика зависит от первого ключа отношения;

-     (PNAME, DNUM)VOLUME – поставляемое количество зависит от второго ключа отношения;

-     (PNAME, DNUM)PNUM – номер поставщика зависит от второго ключа отношения.

Данное отношение не содержит неключевых атрибутов, зависящих от части сложного ключа. Действительно, от части сложного ключа зависят атрибуты PNAME и PNUM, но они сами являются ключевыми. Таким образом, отношение находится в 2NF.

Кроме того, отношение не содержит зависимых друг от друга неключевых атрибутов, т.к. неключевой атрибут всего один – VOLUME. Таким образом, показано, что отношение ПОСТАВКИ находится в 3NF.

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

 

Таблица  19.– Отношение ПОСТАВЩИКИ

PNUM

PNAME

1

Фирма 1

2

Фирма 2

3

Фирма 3

 

Таблица 20.– Отношение ПОСТАВКИ2

PNUM

DNUM

VOLUME

1

1

100

1

2

200

1

3

300

2

1

150

2

2

250

3

1

1000

 

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

Если отношение находится в NFBK, то оно автоматически находится и в 3NF.

Отношение ПОСТАВКИ не находится в NFBK, т.к. имеются зависимости PNUMPNAME и PNAMEPNUM, детерминанты которых не являются потенциальными ключами.

Для того чтобы устранить зависимость от детерминантов, не являющихся потенциальными ключами, необходимо провести декомпозицию, вынося эти детерминанты и зависимые от них части в отдельное отношение. Отношения ПОСТАВЩИКИ и ПОСТАВКИ2, полученные в результате декомпозиции, находятся в NFBK.

Приведенная декомпозиция отношения ПОСТАВКИ на отношения ПОСТАВЩИКИ и ПОСТАВКИ2 не является единственно возможной. Альтернативной декомпозицией является декомпозиция на следующие отношения:

 

Таблица 21. – Отношение ПОСТАВЩИКИ

PNUM

PNAME

1

Фирма 1

2

Фирма 2

3

Фирма 3

 

Таблица 22. – Отношение ПОСТАВКИ3

PNAME

DNUM

VOLUME

Фирма 1

1

100

Фирма 1

2

200

Фирма 1

3

300

Фирма 2

1

150

Фирма 2

2

250

Фирма 3

1

1000

 

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

На самом деле никакого противоречия нет. В отношении ПОСТАВКИ3 атрибут PNAME является внешним ключом, служащим для связи с отношением ПОСТАВЩИКИ. Поэтому, при изменении наименования поставщика, это изменение происходит в отношении ПОСТАВЩИКИ и каскадно распространяется на отношение ПОСТАВКИ3 совершенно так, как изменение номера поставщика каскадно распространяется на отношение ПОСТАВКИ2. Поэтому, формально обе декомпозиции совершенно равноправны. В реальной работе разработчик выберет, конечно, первую декомпозицию, но тут важно подчеркнуть, что его выбор основан совсем на других соображениях, не имеющих отношения к формальной теории нормальных форм.

3.13 Четвертая Нормальная Форма

 

Понятие четвертой нормальной формы (4NF) рассмотрим на примере.

Пример 4. Пусть требуется учитывать данные об абитуриентах, поступающих в ВУЗ, и при анализе предметной области были выделены следующие требования:

- каждый абитуриент имеет право сдавать экзамены на несколько факультетов одновременно;

- каждый факультет имеет свой список сдаваемых предметов;

- один и тот же предмет может сдаваться на нескольких факультетах;

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

Предположим, что нам требуется хранить данные о том, какие предметы должен сдавать каждый абитуриент. Попытаемся хранить данные в одном отношении АБИТУРИЕНТЫ-ФАКУЛЬТЕТЫ-ПРЕДМЕТЫ:

 

Таблица 23. – Отношение АБИТУРИЕНТЫ-ФАКУЛЬТЕТЫ-ПРЕДМЕТЫ

Абитуриент

Факультет

Предмет

Иванов

Математический

Математика

Иванов

Математический

Информатика

Иванов

Физический

Математика

Иванов

Физический

Физика

Петров

Математический

Математика

Петров

Математический

Информатика

 

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

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

 

Таблица 24. – Новое отношение АБИТУРИЕНТЫ-ФАКУЛЬТЕТЫ-ПРЕДМЕТЫ

Номер абитуриента

Номер факультета

Номер предмета

1

1

1

1

1

2

1

2

1

1

2

3

2

1

1

2

1

2

 

Таблица 25. – Отношение АБИТУРИЕНТЫ

Номер абитуриента

Абитуриент

1

Иванов

2

Петров

 

Таблица 26. – Отношение ФАКУЛЬТЕТЫ

Номер факультета

Факультет

1

Математический

2

Физический

 

Таблица 27. – Отношение ПРЕДМЕТЫ

Номер предмета

Предмет

1

Математика

2

Информатика

3

Физика

 

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

Аномалия вставки. При попытке добавить в отношение АБИТУРИЕНТЫ-ФАКУЛЬТЕТЫ-ПРЕДМЕТЫ новый кортеж, например (Сидоров, Математический, Математика), мы обязаны добавить также и кортеж (Сидоров, Математический, Информатика), т.к. все абитуриенты математического факультета обязаны иметь один и тот же список сдаваемых предметов. Соответственно, при попытке вставить в новое отношении кортеж (3, 1, 1), мы обязаны вставить в него также и кортеж (3, 1, 2).

Аномалия удаления. При попытке удалить кортеж (Иванов, Математический, Математика), мы обязаны удалить также и кортеж (Иванов, Математический, Информатика) по той же причине, что и для вставки.

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

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

Декомпозиция отношения АБИТУРИЕНТЫ-ФАКУЛЬТЕТЫ-ПРЕДМЕТЫ для устранения указанных аномалий не может быть выполнена на основе функциональных зависимостей, т.к. это отношение не содержит никаких функциональных зависимостей. Это отношение является полностью ключевым, т.е. ключом отношения является все множество атрибутов. Но ясно, что какая-то взаимосвязь между атрибутами имеется. Эта взаимосвязь описывается понятием многозначной зависимости.

Пусть  − отношение, и    − некоторые из его атрибутов (или непересекающиеся множества атрибутов).

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

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

В отношении АБИТУРИЕНТЫ-ФАКУЛЬТЕТЫ-ПРЕДМЕТЫ имеется многозначная зависимость ФАКУЛЬТЕТАБИТУРИЕНТ|ПРЕДМЕТ.

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

Если в отношении  имеется не менее трех атрибутов    и есть функциональная зависимость , то есть и многозначная зависимость .

Таким образом, понятие многозначной зависимости является обобщением понятия функциональной зависимости.

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

В отношении АБИТУРИЕНТЫ-ФАКУЛЬТЕТЫ-ПРЕДМЕТЫ имеется именно нетривиальная многозначная зависимость ФАКУЛЬТЕТАБИТУРИЕНТ|ПРЕДМЕТ. В силу нетривиальности этой зависимости мы не можем воспользоваться теоремой Хеза для декомпозиции отношения.

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

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

Отношение  находится в четвертой нормальной форме (4NF) тогда и только тогда, когда отношение находится в НФБК и не содержит нетривиальных многозначных зависимостей.

Отношение АБИТУРИЕНТЫ-ФАКУЛЬТЕТЫ-ПРЕДМЕТЫ находится в NFBK, но не в 4NF. Согласно теореме Фейджина, это отношение можно без потерь декомпозировать на отношения ФАКУЛЬТЕТЫ-АБИТУРИЕНТЫ и ФАКУЛЬТЕТЫ-ПРЕДМЕТЫ:

 

Таблица 28. – Отношение ФАКУЛЬТЕТЫ-АБИТУРИЕНТЫ

Факультет

Абитуриент

Математический

Иванов

Физический

Иванов

Математический

Петров

Таблица 29. – Отношение ФАКУЛЬТЕТЫ-ПРЕДМЕТЫ

Факультет

Предмет

Математический

Математика

Математический

Информатика

Физический

Математика

Физический

Физика

В полученных отношениях устранены аномалии вставки и удаления, характерные для отношения АБИТУРИЕНТЫ-ФАКУЛЬТЕТЫ-ПРЕДМЕТЫ.

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

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

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

3.14  Пятая Нормальная Форма

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

Рассмотрим следующее отношение :

Таблица 30. – Отношение

X

Y

Z

1

1

2

1

2

1

2

1

1

1

1

1

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

 

Таблица 31.Проекция

Таблица 32. Проекция

Таблица 33. Проекция

X

Y

1

1

1

2

2

1

X

Z

1

2

1

1

2

1

Y

Z

1

2

2

1

1

1

 

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

Таблица 34. – Отношение

X

Y

Z

1

1

2

1

1

1

1

2

2

1

2

1

2

1

1

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

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

.

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

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

Можно предположить, что отношение  в рассматриваемом примере удовлетворяет следующей зависимости соединения:

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

Зависимость соединения является обобщением понятия многозначной зависимости, и теорема Фейджина для зависимости соединения может быть переформулирована следующим образом:

Отношение  удовлетворяет зависимости соединения тогда и только тогда, когда имеется многозначная зависимость .

Это значит, что многозначная зависимость является частным случаем зависимости соединения, т.е., если в отношении имеется многозначная зависимость, то имеется и зависимость соединения. Обратное, конечно, неверно.

Зависимость соединения называется нетривиальной зависимостью соединения, если выполняется два условия:

  1.  Одно из множеств атрибутов  не содержит потенциального ключа отношения .
  2.  Ни одно из множеств атрибутов не совпадает со всем множеством атрибутов отношения .

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

Зависимость соединения называется тривиальной зависимостью соединения, если выполняется одно из условий:

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

Отношение  находится в пятой нормальной форме (5NF) тогда и только тогда, когда любая имеющаяся зависимость соединения является тривиальной.

Определения 5NF может стать более понятным, если сформулировать его в отрицательной форме:

Отношение  не находится в 5NF, если в отношении найдется нетривиальная зависимость соединения.

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

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

a)  отношение является полностью ключевым (т.е. потенциальным ключом отношения является все множество атрибутов);

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

Тогда можно доказать [5], что при наличии ограничений a) и b) отношение находится в 4НФ, но не в 5НФ.

3.15 Продолжение алгоритма нормализации (приведение к 5 NF)

 

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

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

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

Подводя итоги, отметим, что обобщением 3NF на случай, когда отношение имеет более одного потенциального ключа, является нормальная форма Бойса-Кодда.

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

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

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

Атрибуты (множества атрибутов)  и  многозначно зависят от  () тогда и только тогда, когда из того, что в отношении  содержатся кортежи  и  следует, что в отношении  содержится также и кортеж к .

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

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

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

Отношение  находится в четвертой нормальной форме (4NF) тогда и только тогда, когда отношение находится в NFBK и не содержит нетривиальных многозначных зависимостей.

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

Отношение  находится в пятой нормальной форме (5NF) тогда и только тогда, когда любая имеющаяся зависимость соединения является тривиальной.


4 РЕЛЯЦИОННАЯ АЛГЕБРА

4.1 ОПЕРАЦИИ НАД ОТНОШЕНИЯМИ: ОБЩИЕ СВЕДЕНИЯ

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

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

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

2. Специальные реляционные операции, такие как выборка, проекция, соединение и деление.

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

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

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

В реализациях конкретных реляционных СУБД сейчас не используется в чистом виде ни реляционная алгебра, ни реляционное исчисление. Фактическим стандартом доступа к реляционным данным стал язык SEQUEL(SQL - Structured Query Language), который представляет собой смесь операторов реляционной алгебры и выражений реляционного исчисления, использующий синтаксис, близкий к фразам английского языка и расширенный дополнительными возможностями, отсутствующими в реляционной алгебре и реляционном исчислении.

Современные языки манипулирования данными SQL, QBE, ISBL и др., используемые в СУБД, реализуют широкий набор операций:

-     операции с данными: включение, модификация, удаление данных;

-     операции обработки данных:

-     арифметические выражения (вычисления, сравнения);

-     команды присваивания и печати;

-     агрегатные функции.

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

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

Рассмотрим операторы реляционной алгебры на примере РБД «Разработчики проектов» [9].

Пример 5. Пусть РБД «Разработчики проектов» состоит из шести таблиц:

 

Таблица 35. - РАЗРАБОТЧИКИ (R1)

 

Таблица 36. - ПРОГРАММИСТЫ (R2)

N_R

ФИО

Г_Р

Стаж

 

N_A

N_R_A

Я_П

Категория

R1

Белов А.

1940

21

 

A1

R4

Pas

1

R2

Крылов Г.

1962

17

 

A2

R2

C

2

R3

Фатов Р.

1964

11

 

A3

R5

Pas

3

R4

Белов А.

1953

21

 

A4

R4

C

1

R5

Крылов Г.

1964

10

 

A5

R2

Pas

2

 

Таблица 37- ПРОЕКТЫ (R3)

 

Таблица 38- ВТК (R4)

 

 

N_P

Назв_P

N_R_P

Г_Созд

 

N_ВТК

Назв_ВТК

N_комн

N_рук_ВТК

 

 

P1

ПР-1

R5

1982

 

B1

Луч

12

R5

 

 

P2

ПР-2

R2

1984

 

B2

Стрела

18

R3

 

 

P3

ПР-1

R1

1960

 

B3

Взлет

12

R2

 

 

P4

ПР-3

R2

1987

 

 

P5

ПР-4

R3

1985

 

 

 

Таблица 39. - СОСТАВЫ_ВТК(R5)

 

 

Таблица 40. - ИСПОЛЬЗОВАНИЕ_В_ГИП(R6)

 

N_ВТК

N_А_ВТК

 

N_P_ГИП

N_ГИП

N_R_ГИП

N_ВТК_ГИП

 

 

B1

A1

 

P5

TR1

R1

B3

 

 

B1

A3

 

P3

TR2

R4

B1

 

 

B1

A4

 

P5

TR5

R3

B3

 

 

B2

A2

 

P2

TR1

R1

B2

 

 

B2

A5

 

P4

TR2

R4

B1

 

 

B3

A1

 

 

B3

A5

 

 

4.2 СИНТАКСИС ОПЕРАТОРОВ РЕЛЯЦИОННОЙ АЛГЕБРЫ

 

Рассмотрим синтаксис основных операторов реляционной алгебры [8, 9].

1. Оператор объединение (union). Для двух РТ R1 и R2 одинаковой арности и с совпадающими типами полей формируется РТ R с записями, входящими хотя бы в одну исходную РТ.

 

R=Runion R2.

 

Пример 6. Объединить две РТ: R1 и R2 в одну РТ R.

 

R1:

A

B

R2:

A

B

Ответ R:

A

B

 

a

4

 

c

4

 

a

4

 

b

6

 

d

8

 

b

6

 

 

 

 

 

 

 

c

4

 

 

 

 

 

 

 

d

8

 

2. Оператор вычитание (difference). Для двух РТ R1 и R2 одинаковой арности и с совпадающими типами полей формируется РТ R c записями, содержащимися в уменьшаемом − таблице R1, но отсутствующими в вычитаемом − таблице R2.

 

R=R1 difference R2.

 

Пример 7. Вычесть из РТ R1 таблицу R2, результат записать в РТ R.

 

R1:

A

B

R2:

A

B

Ответ R:

A

B

 

a

4

 

a

3

 

a

4

 

b

6

 

b

6

 

 

 

 

 

c

6

 

 

3. Оператор пересечение (intersection). Для двух РТ R1 и R2 одинаковой арности и с совпадающими типами полей формируется РТ R с записями, входящими в обе РТ.

 

R=R1 intersection R2.

 

Пример 8. Выполнить пересечение таблиц R1 и R2, результат записать в таблицу R.

 

R1:

A

B

R2:

A

B

Ответ R:

A

B

 

a

4

 

a

5

 

b

6

 

b

6

 

b

6

 

 

 

 

4. Оператор проектирование (proj). Из РТ R1 оператор выбирает заданные типы полей и размещает в указанном порядке в таблице R

 

R = proj a1, …a(R1).

 

Пример 9. Из РТ РАЗРАБОТЧИКИ (R1) выбрать поля ФИО и Г_Р.

 

R= proj ФИО, Г_Р (R1).

 

Ответ R: 

ФИО

Г_Р

 

Белов А.

1940

 

Крылов Г.

1962

 

Фатов Р.

1964

 

Белов А.

1953

 

Крылов Г.

1964

 

5. Оператор выбор (sel). Из РТ R1 по заданному критерию выбирается требуемая совокупность записей. В частном случае результатом выборки может быть и пустое множество.

 

R= sel (F) (R1), где - критерий выбора.

 

Критерии выбора формулируются на основе операторов двух типов:

-     операторы сравнения: =, <>, <, >,<=, >=.

-     логические операторы: И (AND), ИЛИ (OR), НЕ (NOT).

Пример 10. В БД «Разработчики проектов» выбрать данные о Белове А.

 

R= sel (ФИО = ‘Белов А.’) (R1).

 

Ответ R:

N_R

ФИО

Г_Р

Стаж

 

R1

Белов А.

1940

21

 

R4

Белов А.

1953

21

 

Пример 11. В БД «Разработчики проектов» выбрать программистов выше третьей категории, работающих на Pascal.

 

R= sel (Я_П = ‘Pas’ AND Категория < 3) (R2).

 

Ответ R:

N_A

N_R_A

Я_П

Категория

 

A1

R4

Pas

1

 

A2

R2

Pas

2

 

Пример. 12. Выполним комбинированный запрос с операторами proj и sel. Пусть необходимо выбрать ФИО разработчиков со стажем от 12 лет, год рождения которых 1960 и позже.

Для запроса необходимо использовать РТ РАЗРАБОТЧИКИ, тогда запрос можно записать в виде:

 

R= proj ФИО sel (Стаж >= 12 AND  Г_Р >= 1960) (R1).

 

Ответ R:

ФИО

 

Крылов Г.

 

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

Следовательно, соединение может быть реализовано двумя способами:

-      по одному полю;

-      по нескольким полям.

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

 

R=R1 join R2.

 

 Пример 13. Соединить таблицы R1 и R2 с одним общим полем.

 

R1:

A

B

R2:

B

C

Ответ R:

A

B

C

 

d

3

 

3

a

 

d

3

a

 

h

7

 

3

b

 

d

3

b

 

y

4

 

7

a

 

h

7

a

 

 

 

 

9

c

 

 

Пример 14. Соединить таблицы R1 и R2 с двумя общими полями

 

R1:

A

B

C

R2:

B

C

D

Ответ R:

A

B

C

D

 

d

3

a

 

3

a

c

 

d

3

a

c

 

h

7

b

 

3

a

d

 

d

3

a

d

 

y

4

a

 

4

a

e

 

y

4

a

e

 

g

2

c

 

 

 

 

 

 

 

 

 

 

Пример 15. Рассмотрим запрос с соединением по одному полю к БД «Разработчики проектов». Пусть необходимо вывести названия проектов, созданных в период с 1970 по 1984 гг. включительно, а также ФИО и стаж разработчиков.

Алгоритм реализации:

1. Выделить названия РТ, задействованных в реализации запроса: ПРОЕКТЫ (R3) и РАЗРАБОТЧИКИ (R1).

2. Из R3 выбрать записи по условию запроса:

 

RT1 = sel (Г_Созд >= 1970 AND Г_Созд <= 1984)(R3).

 

RT1:

N_P

Назв_P

N_R_P

Г_Созд

 

P1

ПP-1

R5

1982

 

P2

ПP-2

R2

1984

 

3.  Соединить RT1 и R1 по общему полю N_R_P (в RT1) и N_RR1):

 

RT2 RT1 join R1.

 

Результирующая таблица RT2 будет иметь вид:

 

RT2:

N_P

Назв_P

N_R_P (N_R)

Г_Созд

ФИО

Г_Р

Стаж

P1

ПP-1

R5

1982

Крылов Г.

1964

10

P2

ПP-2

R2

1984

Крылов Г.

1962

17

 

4) Выбрать из RT2 Назв_P, ФИО и Стаж разработчиков:

 

= proj Назв_P, ФИО, Стаж (RT2).

 

Результирующая таблица R имеет вид:

 

R:

Назв_P

ФИО

Стаж

 

ПP-1

Крылов Г.

10

 

ПP-2

Крылов Г.

17

 

Общий алгоритм реализации запроса можно представить в виде:

 

= proj Назв_P, ФИО, Стаж (sel (Г_Созд >= 1970 AND Г_Созд <= 1984) (R3) join R1).

 

Пример 16. Рассмотрим запрос с соединением по нескольким полям. В БД «Разработчики проектов» выбрать Назв_P, N_R и ФИО разработчиков, выступающих и как руководители ВТК, и как программисты в них.

Алгоритм реализации:

1) Выделить названия РТ, задействованных в реализации запроса: ПРОЕКТЫ (R3), РАЗРАБОТЧИКИ (R1), ВТК (R4), Составы_ВТК (R5), ПРОГРАММИСТЫ (R2).

2) Для нахождения разработчиков проектов, выступающих одновременно и как руководители ВТК, объединить таблицы R3 и R4 по общему полю N_R_P (в R3) и N_рук_ВТК (в R4).

 

RT1 = R3 join R4.

RT1:

N_P

Назв_P

N_R_P (N_рук_ВТК)*

Г_Созд

N_ВТК

Назв_ВТК

N_Комн

P1

ПP-1

R5

1982

B1

Луч

12

P2

ПP-2

R2

1984

B3

Взлет

12

P3

ПP-3

R2

1987

B3

Взлет

12

P4

ПP-4

R3

1985

B2

Стрела

18

 

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

3) Для экономии памяти ПК и увеличения быстродействия выбрать из RT1 только участвующие в запросе поля:

 

RT2 = proj Назв_P, N_R_P, N_ВТК (RT1).

RT2:

Назв_P

N_R_P

N_ВТК

ПP-1

R5

B1

ПP-2

R2

B3

ПP-3

R2

B3

ПP-4

R3

B2

 

4) Для определения разработчиков-руководителей ВТК, являющихся одновременно и программистами, соединить RT2 и R2 по одному общему полю N_R_P (в RT2) и N_R_A (в R2):

 

RT3 = RT2 join R2.

RT3:

Назв_P

N_R_P

N_ВТК

N_A

Я_П

Категория

ПP-1

R5

B1

A3

Pas

3

ПP-2

R2

B3

A2

C

2

ПP-2

R2

B3

A5

Pas

2

ПP-3

R2

B3

A2

C

2

ПP-3

R2

B3

A5

Pas

2

 

5) Выберем из RT3 только участвующие в запросе поля:

 

RT4 = proj Назв_P, N_R_P, N_ВТК, N_A (RT3).

RT4:

Назв_P

 

N_R_P

 

N_ВТК

 

N_A

ПP-1

 

R5

 

B1

 

A3

ПP-2

 

R2

 

B3

 

A2

ПP-2

 

R2

 

B3

 

A5

ПP-3

 

R2

 

B3

 

A2

ПP-3

 

R2

 

B3

 

A5

 

6) Для определения разработчиков-руководителей ВТК, являющихся программистами именно в своих ВТК, сделать соединение таблиц RT4 и R5 по двум полям: N_ВТК и N_A

 

RT5 = RT4 join R5.

RT5:

Назв_P

N_R_P

N_ВТК

N_A_ВТК

ПP-1

R5

B1

A3

ПP-2

R2

B3

A5

ПP-3

R2

B3

A5

 

7) Выбрать из RT5 участвующие в запросе поля:

 

RT6 = proj Назв_P, N_R_P (RT5).

 

RT6:

Назв_P

N_R_P

ПP-1

R5

ПP-2

R2

ПP-3

R2

 

8) Для полного ответа на запрос объединим таблицы RT6 и R1 по общему полю N_R_P (в RT6) и N_(в R1) с последующим выделением полей, указанных в запросе:

 

RT7 = RT6 join R1.

RT7:

Назв_P

N_R_P

ФИО

Г_P

 

Стаж

ПP-1

R5

Крылов Г.

1964

 

10

ПP-2

R2

Крылов Г.

1962

 

17

ПP-3

R2

Крылов Г.

1962

 

17

 

9) Выберем из RT7 участвующие в запросе поля:

 

RT8 = proj Назв_P, N_R, ФИО (RT7).

 

 

RT8:

Назв_P

N_R_P

ФИО

ПP-1

R5

Крылов Г.

ПP-2

R2

Крылов Г.

ПP-3

R2

Крылов Г.

 

Таким образом, алгоритм ответа на запрос можно записать в виде:

 

proj Назв_PN_R_P, ФИО (proj Назв_PN_R_P

  8                                          6

(proj Назв_P, N_R_P, N_ВТК, N_A

   4

(proj Назв_P, N_R_P (R3 join R4) join R2) join R5) join R1).

   2                                      1           3            5           7

 

7) Оператор соединения по условию. Оператором join из двух РТ R1 и R2 формируется результирующая R, если выполняется заданное условие V:

= P1i G P2j,

 

где G - арифметический оператор сравнения, выбираемый из множества =, <>, <, >,<=, >=;

P1iP2j - типы полей в реляционных таблицах R1 и R2 соответственно.

Для оператора типа равенство оператор join называется эквисоединением.

 

R = R1 join R2.

       P1i G P2j

 

Пример 17. Соединить таблицы R1 и R2 по условию B = D:

 

R = R1 join R2.

       B = D

 

R1:

A

B

C

R2:

D

E

Ответ R:

A

B

C

D

E

 

a

b

c

 

a

u

 

g

e

z

e

k

 

d

u

p

 

e

k

 

 

g

e

z

 

 

8) Оператор умножение (product)

Для двух РТ R1 и R2 соответственно арности K1 и K2 формируется результирующая РТ R арности (K1 + K2), записи которой представляют собой конкатенацию каждой записи из таблицы R1 с каждой записью из таблицы R2. В таблице R имена полей формируются из двух частей, разделенных точкой. Префиксом имени поля принимается имя таблицы R1 или R2, в зависимости от того, из какой таблицы взято значение поля, а афиксом – соответствующие имена полей из этой таблицы.

 

R=R1 product R2.

 

Пример 18.

 

R1:

A

B

R2:

C

D

Ответ R:

R1.A

R1.B

R2.C

R2.D

 

b

4

 

c

4

 

b

4

c

4

 

d

7

 

d

R

 

b

4

d

R

 

 

 

 

 

 

 

d

7

c

4

 

 

 

 

 

 

 

d

7

d

R

 

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

Пример 19. В БД найти названия и годы создания проектов, разработанных до года рождения Фатова Р. с помощью оператора умножения, как одного из возможных вариантов решения данной задачи.

Алгоритм реализации:

1) Выделить названия РТ, задействованных в реализации запроса: РАЗРАБОТЧИКИ (R1), ПРОЕКТЫ (R3).

2) Сформировать таблицу с годом рождения Фатова Р. Для этого сначала выделить запись о нем из таблицы R1, а затем выбрать поле Г_Р.

 

RT1 = sel (ФИО = ‘Фатов Р.’) (R1).

 

RT1:

N_R

ФИО

Г_Р

Стаж

 

R3

Фатов О.

1964

11

 

RT2 = proj Г_Р (RT1)

 

RT2:

Г_Р

 

1964

 

3) Из R3 выделим поля Назв_P и Г_Созд.

 

RT3 = proj Назв_Р, Г_Созд (R3).

 

 

RT3:

Назв_P

Г_Созд

 

ПР-1

1982

 

ПР-2

1984

 

ПР-1

1960

 

ПР-3

1987

 

ПР-4

1985

 

4) Для реализации сравнения выполнить операцию перемножения таблиц RT2 и RT3:

 

RT4 = RT2 product RT3.

 

RT4:

RT2.Г_Р

RT3.Назв_P

RT3.Г_Созд

 

1964

ПР-1

1982

 

1964

ПР-2

1984

 

1964

ПР-1

1960

 

1964

ПР-3

1987

 

1964

ПР-4

1985

 

5) Из RT4 выберем запись по критерию запроса:

 

RT5 = sel (RT3. Г_Созд < RT2. Г_Р) (RT4)

 

RT5:

RT2.Г_Р

RT3.Назв_P

RT3.Г_Созд

 

1964

ПР-1

1960

 

6) Из RT5 выбрать поля, необходимые и достаточные для ответа на запрос:

 

RT6 = proj RT3.Назв_Р, RT3.Г_Созд (RT5).

 

RT6:

RT3.Назв_P

RT3.Г_Созд

 

ПР-1

1960

 

Таким образом, алгоритм ответа на запрос можно записать в виде:

 

proj RT3.Назв_PRT3.Г_Созд (sel (RT3.Г_Созд < RT2.Г_Р)

  6                                               5

(proj Г.Р. (sel(ФИО = 'Фатов Р.') (R1)) product

   2             1                                              4

(proj Назв_P, Г_Созд (R3))).

  3

 

10) Оператор деление (division)

Для двух РТ соответственно делимого R1 и делителя R2 таких, что:

а) каждому типу поля в делителе найдется соответствующий тип поля в делимом;

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

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

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

 

R = R1 division R2.

.

 

Пример 20.

 

R1:

D

E

F

R2:

E

F

Ответ R:

D

1

A

h

3

 

h

3

 

A

2

C

a

7

 

a

7

 

B

3

B

a

7

 

e

4

 

4

B

e

4

 

5

A

e

4

 

6

A

a

7

 

7

B

h

3

 

8

C

e

4

 

 

Примечания:

1) В таблице R лишь одно поле D, так как оно входит в делимое и отсутствует в делителе;

2) Значения и B входят в  R, так как в делимом они соответственно конкатенированы с каждой из трех записей делителя (см. в табл. R записи №№ 1, 5, 6 для D = A и №№ 3, 4, 7 для  = B);

3) Значение C отсутствует в  R, так как в R1 нет записи Ch3.

4.3 ОПТИМИЗАЦИЯ АЛГОРИТМОВ РЕАЛИЗАЦИИ ЗАПРОСОВ

Реляционные языки запросов обеспечивают высокоуровневый «декларативный» интерфейс для доступа к данным, хранимым в РБД. Кроме этого, в SQL для вычисления запросов обязательно присутствуют такие компоненты как оптимизатор запросов и подсистема выполнения запросов.

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

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

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

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

Для получения ответа возможно два алгоритма, дающих идентичные результаты:

,

.

 

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

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

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


5. CASE – технологии

5.1 Общие вопросы проектирования ИС, понятие CASE-технологии

 

Проектирование ИС охватывает три области:

1. Область проектирования объектов данных, которые будут реализованы в БД (ИО).

2. Разработка программ, экранных форм и отчетов, запросов (ПО).

3. Учет конкретной среды или технологий (топология сети, конфигурация аппаратных средств и  т.д.) (ТО).

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

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

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

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

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

наследуемость ИС или необходимость интеграции существующих и вновь разрабатываемых приложений;

функционирование в неоднородной среде на нескольких аппаратных платформах;

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

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

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

Ручная разработка обычно порождает следующие проблемы:

неадекватная спецификация требований;

неспособность обнаруживать ошибки в проектных решениях;

низкое качество документации, снижающее эксплуатационные качества;

затяжной цикл проектирования и неудовлетворительные результаты тестирования.

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

Перечисленные проблемы способствовали появлению программно-технологических средств специального класса – CASE-средств, реализующих CASE-технологию создания и сопровождения ИС. Термин CASE (Computer Aided Software Engineering) используется в настоящее время в весьма широком смысле. Первоначальное значение термина CASE, ограниченное вопросами автоматизации разработки только лишь ПО, в последнее время приобрело новый смысл, охватывающий процесс разработки сложных ИС в целом.

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

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

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

-     широкое внедрение и постоянный рост производительности компьютеров, позволившие использовать эффективные графические средства и автоматизировать большинство этапов проектирования;

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

CASE-технология – это методология проектирования ИС, а также набор инструментальных средств, позволяющих в наглядной форме моделировать предметную область, анализировать эту модель на всех этапах разработки и сопровождения ИС и разрабатывать приложения в соответствии с информационными потребностями пользователей. Большинство существующих CASE-средств основано на методологиях структурного или объектно-ориентированного анализа и проектирования, использующих спецификации в виде диаграмм или текстов для описания внешних требований, связей между моделями системы, динамики поведения системы и архитектуры программных средств.

Несмотря на все потенциальные возможности CASE-средств, существует множество примеров их неудачного внедрения, в результате которых CASE-средства становятся «полочным» ПО (shelfware). Причина такого явления кроется в следующих особенностях:

-     CASE-средства не обязательно дают немедленный эффект; он может быть получен только спустя какое-то время;

-     реальные затраты на внедрение CASE-средств обычно намного превышают затраты на их приобретение;

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

Для успешного внедрения CASE-средств организация должна обладать следующими качествами:

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

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

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

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

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

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

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

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

-     положительное воздействие на некоторые или все из перечисленных факторов: производительность, качество продукции, соблюдение стандартов, документирование;

-     приемлемый уровень отдачи от инвестиций в CASE-средства [10].

5.2 Жизненный цикл ПО ИС

Одним из базовых понятий методологии проектирования ИС является понятие жизненного цикла ее программного обеспечения (ЖЦ ПО).

ЖЦ ПО – это непрерывный процесс, который начинается с момента принятия решения о необходимости его создания и заканчивается в момент его полного изъятия из эксплуатации.

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

Основным нормативным документом, регламентирующим ЖЦ ПО, является международный стандарт ISO/IEC 12207: 1995 (российский аналог – ГОСТ Р ИСО/МЭК 12207-99). ISO (International Organization of Standardization) – это Международная организация по стандартизации, а IEC (International Electrotechnical Commission) – Международная комиссия по электротехнике.

По стандарту модель ЖЦ ПО включает в себя:

-     стадии;

-     результаты выполнения работ на каждой стадии;

-     ключевые события – точки завершения работ и принятия решений.

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

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

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

Структура ЖЦ ПО базируется на трех группах процессов:

-     основные (приобретение, поставка, разработка, эксплуатация, сопровождение);

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

-     организационные (управление, создание инфраструктуры, усовершенствование, обучение).

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

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

Рассмотрим некоторые процессы подробнее.

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

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

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

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

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

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

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

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

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

В РБ до настоящего времени при разработке ИС принято использовать советский стандарт ГОСТ 34.601-90, который предусматривает следующие стадии создания автоматизированной системы (АС): формирование требований, разработка концепции АС, разработка и утверждение технического задания на создание АС, эскизный проект, технический проект, рабочая документация, ввод в действие и сопровождение АС. Все стадии разбиты на  этапы, которые подробно описываются в тексте стандарта. Однако данный стандарт не вполне подходит для проведения разработок в настоящее время: многие процессы отражены недостаточно, а некоторые положения устарели.

5.3 Модели жизненного цикла ПО

 

Стандарт ISO/IEC 12207 описывает структуру процессов ЖЦ ПО, но не конкретизирует в деталях, как реализовать или выполнить действия и задачи, включенные в эти процессы.

Существует три основных модели ЖЦ ПО: каскадная модель (70-85 г.г.), каскадная модель с промежуточным контролем (итерационная), спиральная модель (86-90 г.г.) [10].

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

 

 

Рис. 9. - Каскадная модель ЖЦ ПО

 

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

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

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

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

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

 

 

Рис. 10. - Каскадная модель ЖЦ с промежуточным контролем

 

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

Для преодоления этого недостатка и была создана спиральная модель, ориентированная на активную работу с пользователями и представляющая разрабатываемую ИС как постоянно корректируемую во время разработки. В спиральной модели (рис. 11) основной упор делается на этапы анализа и проектирования, на которых реализуемость технических решений проверяется путем создания прототипов. Спиральная модель позволяет начинать работу над следующим этапом, не дожидаясь завершения предыдущего. Спиральная модель имеет целью, как можно раньше ознакомить пользователей с работоспособным продуктом, корректируя при необходимости требования к разрабатываемому продукту и каждый «виток» спирали означает создание фрагмента или версии. Основная проблема спирального цикла – определение момента перехода на следующий этап, и возможным ее решением является принудительное ограничение по времени для каждого из этапа ЖЦ. Наиболее полно достоинства такой модели проявляются при обслуживании программных средств.

 

Рис. 11. - Спиральная модель ЖЦ ПО

 

Основные недостатки спиральной модели:

-     наличие неработоспособных версий;

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

 

5.4 Методология RAD

 

Одним из возможных подходов к разработке ПО в рамках спиральной модели является получившая в последнее время широкое распространение методология быстрой разработки приложений RAD (Rapid Application Development) [10].

Под термином RAD обычно понимается процесс разработки ПО, содержащий 3 основных элемента:

-     небольшую команду программистов (от 2 до 10 человек);

-     короткий, но тщательно проработанный производственный график (от 2 до 6 месяцев);

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

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

Жизненный цикл ПО по методологии RAD состоит из четырех фаз:

1.  фаза анализа и планирования требований;

2.  фаза проектирования;

3.  фаза построения;

4.  фаза внедрения.

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

На фазе проектирования часть по