Базы данных и информационные технологии Лекция 1. Введение в базы данных и СУБД Одним из важнейших понятий теории базы данных является понятие информации. Здесь под информацией понимают любые сведения о каком-либо событии, процессе, объекте. С понятием информации тесно связано понятие данных. Данные – это информация, представленная в определенном виде, позволяющем автоматизировать ее сбор, хранение и обработку. База данных (БД) – совокупность специальным образом организованных данных, хранимых в памяти компьютера и отражающих состояние объектов и их отношений в рассматриваемой предметной области. Предметной областью принято называть ту часть реального мира, объекты которой описаны в базе данных. База данных состоит из множества связанных файлов. Логическую структуру хранимых в базе данных называют моделью данных. К основным моделям представления данных относят следующие: иерархическую, сетевую, реляционную, постреляционную, многомерную и объектно-ориентированную. Информацию о данных, хранимых в базе, принято называть метаданными (данными о данных). Совокупность всех метаданных образует словарь данных . База данных должна обладать определенными свойствами : 1. Восстанавливаемость – возможность восстановления базы данных после сбоя системы (проверка наличия файлов, дублирование базы данных). 2. Безопасность – предполагает защиту данных от преднамеренного и непреднамеренного доступа, защита от копирования, запрещение несанкционированного доступа. 3. Целостность . В каждый момент времени существования базы данных сведения, содержащиеся в ней, должны быть полными, непротиворечивыми и адекватно отражающими предметную область. В этом и заключается ее целостность. Целостность базы данных достигается вследствие введения ограничения целостности (указание диапазона допустимых значений, соотношение между значениями данных, ограничение на удаление информации и т.д.). Ограничения реализуются различными средствами СУБД, например, при помощи декларативных (объявленных при разработке базы данных ее разработчиком) ограничений целостности. 4. Эффективность – минимальное время реакции на запрос пользователя. Система управление базами данных (СУБД) – совокупность языковых и программных средств, предназначенных для создания, ведения и совместного использования базы данных многими пользователями. Обычно СУБД различают по используемой модели данных. Так, например, СУБД, основанные на использовании реляционной модели данных, называют реляционными СУБД. Основные функции СУБД 1. Администрирование базы данных. СУБД имеют развитые средства администрирования базы данных (определение доступа к базе, ее архивация). В связи с тем, что базы данных приникают сегодня во многие сферы деятельности человека, появилась новая профессия – администратор базы данных, человек, отвечающий за проектирование, создание, использование и сопровождение базы данных. В процессе эксплуатации БД администратор обычно следит за ее функционированием, обеспечивает защиту от несанкционированного доступа к хранимым данным, вносит изменения в структуру базы, контролирует достоверность информации в ней. 2. Непосредственное управление данными во внешней памяти. Эта функция предоставляет пользователю возможность выполнения основных операций с данными – хранение, извлечение и обновление информации. Она включает в себя обеспечение необходимых структур внешней памяти как для хранения данных, непосредственно входящих в БД, так и для служебных целей, например, для убыстрения доступа к данным. СУБД поддерживает собственную систему именования объектов БД. 3. Управление буферами оперативной памяти. СУБД обычно работают с БД значительного размера; по крайней мере этот размер обычно существенно больше доступного объема оперативной памяти. Понятно, что если при обращении к любому элементу данных будет производиться обмен с внешней памятью, то вся система будет работать со скоростью устройства внешней памяти. Практически единственным способом реального увеличения этой скорости является буферизация данных в оперативной памяти. Однако этого недостаточно для целей СУБД. Поэтому в развитых СУБД поддерживается собственный набор буферов оперативной памяти. 4. Управление транзакциями Транзакция – это последовательность операций над БД, которые рассматриваются СУБД как единое целое и позволяют добавлять, удалять или обновлять сведения о некотором объекте в базе (по существу это некоторый программный код, написанный на одном из языков управления данными). Либо транзакция успешно выполняется, и СУБД фиксирует изменения БД, произведенные этой транзакцией, либо ни одно из этих изменений никак не отражается на состоянии БД. Например, если в результате транзакции произошел сбой компьютера, база данных попадает в противоречивое положение – некоторые изменения уже внесены, остальные нет. Транзакция позволяет вернуть базу в первоначальное непротиворечивое состояние (отменить все выполненные изменения). 5. Журнализация Одним из основных требований к СУБД является надежность хранения данных во внешней памяти. Под надежностью хранения понимается то, что СУБД должна быть в состоянии восстановить последнее состояние БД после любого аппаратного или программного сбоя (аварийное выключение питания, аварийное завершение работы СУБД или аварийное завершение пользовательской программы). Понятно, что в любом случае для восстановления БД нужно располагать некоторой дополнительной информацией. Наиболее распространенным методом поддержания надежности хранения является ведение журнала изменений БД. Журнал – это особая часть БД, недоступная пользователям и поддерживаемая с особой тщательностью (иногда поддерживаются две копии журнала, располагаемые на разных физических дисках), в которую поступают записи обо всех изменениях основной части БД. Изменения БД журнализуются следующим образом: запись в журнале соответствует некоторой операции изменения БД (например, операции удаления строки из таблицы реляционной БД). С помощью журнала можно решить все проблемы восстановления БД после любого сбоя. 6. Поддержка языков БД СУБД включает язык определения данных , с помощью которого можно определить структуру базы, тип данных в ней, указать ограничения целостности (это язык, с помощью которого задаются различные имена, свойства объектов). Кроме того, СУБД позволяет вставлять, удалять, обновлять и извлекать информацию из базы данных посредством языка управления данными – языка запросов, который позволяет выполнять различные действия с данными, осуществлять их поиск и выборку. Он содержит набор различных операторов (заносить данные, удалять, модифицировать, выбирать и т.д.). Процесс извлечения данных и их обработка скрыты от пользователя. Стандартным языком наиболее распространенных в настоящее время СУБД является язык SQL (Structured Query Language). Он имеет сразу два компонента: язык определения данных и язык управления данными. Кроме того, одним из языков управления данными является язык QBE – язык запросов по образцу. Подробно о реализаций функций СУБД с помощью языка SQL будет рассказано на отдельных лекциях, посвященных языку SQL. Классификация СУБД 1. По степени универсальности все СУБД делятся на СУБД общего назначения и специализированные СУБД. СУБД общего назначения не ориентируются на информационные потребности конкретной группы пользователей. Они могут быть использованы для создания и использования баз данных в любой предметной области (документоведение, образование, риэлтерская деятельность и т.д.). К ним относят MSAccess, MSFoxPro. Однако в некоторых случаях доступные СУБД общего назначения не позволяют добиться требуемых результатов. С этой целью используют специализированные СУБД, которые позволяют осуществить работу с данными, описывающими информационные потребности узкого круга пользователе. К таким СУБД можно отнести Lotus. 2. По функциональности все СУБД делятся на полнофункциональные СУБД, серверы баз данных, клиенты баз данных.Полнофункциональные СУБД представляют собой традиционные СУБД, которые изначально создавались для больших ЭВМ, затем для ПЭВМ. Они являются наиболее многочисленными и мощными по своим возможностям. К ним относят MSAccess, MSFoxPro, Paradox, dBaseIV. Такие СУБД имеют развитый интерфейс, для создания отчетов и запросов используются мастера. Многие СУБД имеют встроенные языки программирования для профессиональных разработчиков. Серверы БД предназначены для организации центров обработки данных в локальной (или глобальной) сети. Они обладают скудным интерфейсом, однако их основное назначение – организация хранения баз данных удаленных пользователей, защита данных от несанкционированного доступа, ограничение доступа к данным, возможность одновременной работы с базой нескольким пользователям. Данная группа менее многочисленна, однако их количество постоянно растет за счет того, что сегодня практически в любой организации, на любом предприятии все компьютеры соединяются в локальную сеть. Следовательно возникает необходимость организации централизованного хранения базы и создания удаленного многопользовательского доступа к ней. Примером такой СУБД является СУБД MSSQLServer. В роли клиентов баз данных могут использоваться любые полнофункциональные СУБД. здесь их роль сводится к тому, чтобы обеспечить доступ к данным, их просмотр, поиск и выборку. 3. По характеру использования СУБД делят на персональные и многопользовательские. Персональные СУБД обычно обеспечивают возможность создания персональных баз данных. Такие СУБД могут выступать в роли клиентов БД. К ним относят MSAccess, MSFoxPro, Paradox, Clipper. Многопользовательские СУБД включают в себя сервер базы данных и клиентскую часть, могут работать в с различными операционными системами, с различными типами ЭВМ. К таким СУБд относят Oracle, Informix. Компоненты среды СУБД В СУБД можно выделить несколько основных компонентов : данные, пользователи, аппаратное обеспечение, программное обеспечение, процедуры. Данные являются наиболее важным компонентом. Для хранения данных и функционирования базы необходимо аппаратное обеспечение – набор физических устройств (ПК, сеть), на которых существует база и СУБД. Для того, чтобы можно было работать с данными, кроме аппаратного обеспечения необходимо иметь операционную систему, сетевое программное обеспечение, программное обеспечение самой СУБД и прикладные программы-приложения. Прикладные программы пишутся программистами на одном из языков высокого уровня (Pascal, C, VB) для нужд конкретной организации. Такие программы используют средства СУБД для обращения к данным в базе и их обработки, создавая различные свойственные данной организации формы, отчеты. Среди пользователей базой данной можно выделить 4 категории лиц: администраторы данных, администраторы баз данных, разработчики баз данных, непосредственно сами пользователи. Администраторы данных работают с данными с самого начала процесса ее создания. Отвечают за сбор информационных потребностей данной организации, проектирование будущей базы. Администратор базы данных отвечает за физическую реализацию базы, обеспечение безопасности, сопровождает базу в процессе ее эксплуатации, следит за достоверностью информации в базе и т.д. Разработчики баз данных – категория лиц, которые работают с ней только в процессе ее разработки по проекту, созданному администратором данных. Пользователи – это конечные пользователи, ради которых база проектировалась, создавалась и будет работать. Их часто называют клиентами. СУБД является достаточно сложным видом программного обеспечения, поэтому в составе СУБД можно выделить ряд программных компонентов : – ядро СУБД, которое отвечает за управление данными во внешней памяти, управление буферами оперативной памяти, транзакциями, журнализацию. Это главная часть СУБД. Ядро обладает собственным интерфейсом, недоступным пользователю напрямую. – компилятор языка БД (обычно SQL), предназначенный для работы с данными. – набор утилит. Лекция 2. Модели данных Первые СУБД использовали иерархическую модель данных. Типичным представителем СУБД, поддерживаемых данный вид моделей (наиболее известным и распространенным), является Information Management System (IMS) фирмы IBM. Первая версия появилась в 1968 г. и была создана для поддержки лунного проекта «Аполлон» (управление огромного количества деталей, иерархически связанных между собой). Структурная часть Основными информационными единицами являются сегмент, поле дерево. Поле данных – наименьшая неделимая поименованная информационная единица, сегмент (запись) образуется из конкретных значений полей данных, тип записи – набор взаимосвязанных сегментов одного уровня, дерево – набор записей данного типа (таблица). Иерархическая модель базируется на теории графов и представляет собой древовидный граф. Вершины графа – деревья базы данных, дуги, соединяющие вершины – связь «предок – потомок». Иерархическая модель из-за своего внешнего сходства часто называют деревом или набором деревьев. В вершине иерархии лежит корень дерева, ответвления – листья дерева. Между типами записи поддерживаются связи. База данных с такой схемой могла бы выглядеть следующим образом: Управляющая часть Примерами типичных операторов манипулирования иерархически организованными данными могут быть следующие: · Найти указанное дерево БД (например, отдел 310); · Перейти от одного дерева к другому; · Перейти от одной записи к другой внутри дерева (например, от отдела - к первому сотруднику); · Перейти от одной записи к другой в порядке обхода иерархии; · Вставить новую запись в указанную позицию; · Удалить текущую запись. В иерархической модели используются два метода доступа к данным: прямой порядок обхода дерева и обратный порядок. Прямой обход осуществляется сверху вниз, начинается с корня и постепенно делается обход всех предков в направлении сверху-вниз, слева-направо. Обратный подход начинается с доступа к самым нижним сегментам с постепенным переходом снизу-вверх, слева-направо. Ограничения целостности Целостность связи поддерживается между предками и потомками. Основное правило: никакой потомок не может существовать без своего родителя. Кроме того, иерархическая модель обладает следующими свойствами: 1. каждый потомок имеет только одного предка; 2. предок может не иметь потомков. К достоинствам иерархической модели данных относятся эффективное использование памяти компьютера и высокие временные показатели выполнения операций над данными. Недостатком иерархической модели является ее громоздкость для обработки информации с достаточно сложными связями. Примеры иерархических СУБД : Ока, ИНЭС, МИРИС, DataEdge Сетевая модель Сети – естественный способ представления реальных отношений между объектами. Сетевая модель также опирается на теорию графов. Появились в 70-х годах XX века. ТипичнымипредставителямиявляютсяСУБД Integrated Database Management System (IDMS) компании Cullinet Software, Inc. и Integrated Data Store (IDS) фирмы General Electric. Сетевой подход к организации данных является расширением иерархического. В иерархических структурах запись-потомок должна иметь в точности одного предка; в сетевой структуре данных потомок может иметь любое число предков. Структурная часть Основными элементами сетевой базы данных являются элемент данных, агрегат данных, запись, набор. Элемент данных – наименьшая неделимая поименованная информационная единица, доступная пользователю. Элемент данных может иметь свой тип. Агрегат данных – поименованная совокупность элементов данных внутри записи (дата – день, месяц, год). Запись – поименованная структура, содержащая элементы данных (запись в реляционной таблице). Тип записей – это совокупность логически связанных экземпляров записей, моделирует некоторый класс объектов реального мира. Набор – это поименованная двухуровневая иерархическая структура, которая выражает связи между двумя типами записей (один к одному, один ко многим). На формирование типов связи не накладываются особые ограничения; возможны, например, следующие ситуации: – Данный тип записи может быть предком для любого числа связей. – Данный тип записи может быть потомком в любом числе связей. – Может существовать любое число связей с одним и тем же типом записи предка и одним и тем же типом записи потомка. – Типы записи X и Y могут быть предком и потомком в одной связи и потомком и предком - в другой. – Предок и потомок могут быть одного типа записи. – Между двумя типами записей может быть любое количество наборов (преподаватель может не только преподавать, и быть куратором этой группы). Простой пример сетевой схемы БД: Таким образом, сетевая база данных – поименованная совокупность записей различного типа и наборов, содержащих связи между ними. Управляющая часть Примерный набор операций может быть следующим: – Найти конкретную запись в наборе однотипных записей (инженера Сидорова); – Перейти от предка к первому потомку по некоторой связи (к первому сотруднику отдела 310); – Перейти к следующему потомку в некоторой связи (от Сидорова к Иванову); – Перейти от потомка к предку по некоторой связи (найти отдел Сидорова); – Создать новую запись; – Уничтожить запись; – Модифицировать запись; – Включить в связь; – Исключить из связи; – Переставить в другую связь и т.д. Ограничения целостности Достоинством сетевой модели данных является возможность эффективной реализации по показателям затрат памяти и оперативности. В сравнении с иерархической моделью сетевая модель предоставляет большие возможности по созданию и моделированию различных связей между сущностями реального мира (предметной области). Недостатком сетевой модели является высокая сложность и жесткость схемы данных, сложность для понимания и выполнения обработки информации обычным пользователем. Реляционная модель данных Сложность практического использования иерархических и сетевых СУБД, желание пользователей оперировать более крупными объектами, чем элементы данных заставили искать иные способы представления данных и послужило причиной возникновения новой структуры данных – реляционной (табличной). Работа с таблицами понятна и привычна каждому пользователю. Создателем реляционной модели является математик, сотрудник фирмы IBM Э.Ф. Кодд (1970 г.). Он же ввел два языка манипулирования данными SQL и QBE. Э.Кодд предложил использовать для обработки данных аппарат теории множеств (объединение, пересечение, разность). Он показал, что любое представление данных сводится к совокупности двумерных таблиц. Структурная часть Реляционная база данных представляет собой набор таблиц (которые Кодд назвал отношениями), каждая из которых имеет уникальное имя и состоит из строк – записей (кортежей) и столбцов – полей (атрибутов). Каждая запись представляет объект реального мира. Свойства объекта, его характеристики определяются значениями полей. Каждое поле имеет имя, тип и размер данных, хранимых в нем. Имена полей вынесены в шапку таблицы. Тип данных Понятие тип данных в реляционной модели данных полностью адекватно понятию типа данных в языках программирования. Обычно в современных реляционных БД допускается хранение символьных, числовых данных, битовых строк, специализированных числовых данных (таких как "деньги"), а также специальных "темпоральных" данных (дата, время, временной интервал). Наименьшая единица данных реляционной модели – это отдельное атомарное (неразложимое) для данной модели значение данных . Так, в одной предметной области фамилия, имя и отчество могут рассматриваться как единое значение, а в другой – как три различных значения. Доменом называется множество значений данного типа (например, множество названий населенных пунктов). Домены весьма важные компоненты реляционной модели. Смысл доменов состоит в следующем. Если значения двух атрибутов берутся из одного и того же домена, то, вероятно, имеют смысл сравнения, использующие эти два атрибута (например, для организации транзитного рейса можно дать запрос "Выдать рейсы, в которых время вылета из Москвы в Сочи больше времени прибытия из Архангельска в Москву"). Если же значения двух атрибутов берутся из различных доменов, то их сравнение, вероятно, лишено смысла: стоит ли сравнивать номер рейса со стоимостью билета? Кортеж, отношение Отношением является таблица, заголовком которой является схема отношения, а строками - кортежи ; имена атрибутов именуют столбцы этой таблицы. Отношения используются для представления объектов окружающего мира и представления связей между объектами. Реляционная база данных - это конечный набор отношений. Каждое отношение обладает хотя бы одним потенциальным ключом, поскольку по меньшей мере комбинация всех его атрибутов удовлетворяет условию уникальности. Один из потенциальных ключей (выбранный произвольным образом) принимается за его первичный ключ. Остальные возможные ключи, если они есть, называются альтернативными ключами . Отношения, схема базы данных Схема отношения - это именованное множество пар {имя атрибута, имя домена (или типа)}. Схемой реляционной базы данных называется набор заголовков отношений, входящих в базу данных. Ограничение целостности В целостной части реляционной модели данных фиксируются два базовых требования целостности, которые должны поддерживаться в любой реляционной СУБД. Первое требование называется требованием целостности сущностей . Объекту или сущности реального мира в реляционных БД соответствуют кортежи отношений. Конкретно требование состоит в том, что любой кортеж любого отношения отличим от любого другого кортежа этого отношения, т.е. другими словами, любое отношение должно обладать первичным ключом. Второе требование называется требованием целостности по ссылкам и является несколько более сложным. Очевидно, сложные сущности реального мира представляются в реляционной БД в виде нескольких кортежей нескольких отношений. Например, представим, что нам требуется представить в реляционной базе данных сущность ОТДЕЛ с атрибутами ОТД_НОМЕР (номер отдела), ОТД_КОЛ (количество сотрудников) и ОТД_СОТР (набор сотрудников отдела). Для каждого сотрудника нужно хранить СОТР_НОМЕР (номер сотрудника), СОТР_ИМЯ (имя сотрудника) и СОТР_ЗАРП (заработная плата сотрудника). Как мы вскоре увидим, при правильном проектировании соответствующей БД в ней появятся два отношения: ОТДЕЛЫ ( ОТД_НОМЕР, ОТД_КОЛ ) (первичный ключ - ОТД_НОМЕР) и СОТРУДНИКИ ( СОТР_НОМЕР, СОТР_ИМЯ, СОТР_ЗАРП, СОТР_ОТД_НОМ ) (первичный ключ - СОТР_НОМЕР). Как видно, атрибут СОТР_ОТД_НОМ появляется в отношении СОТРУДНИКИ не потому, что номер отдела является собственным свойством сотрудника, а лишь для того, чтобы иметь возможность восстановить при необходимости полную сущность ОТДЕЛ. Значение атрибута СОТР_ОТД_НОМ в любом кортеже отношения СОТРУДНИКИ должно соответствовать значению атрибута ОТД_НОМ в некотором кортеже отношения ОТДЕЛЫ. Атрибут такого рода называется внешним ключом , поскольку его значения однозначно характеризуют сущности, представленные кортежами некоторого другого отношения (т.е. задают значения их первичного ключа). Говорят, что отношение, в котором определен внешний ключ, ссылается на соответствующее отношение, в котором такой же атрибут является первичным ключом. Требование целостности по ссылкам, или требование внешнего ключа состоит в том, что для каждого значения внешнего ключа, должен найтись кортеж с таким же значением первичного ключа, либо значение внешнего ключа должно быть неопределенным (т.е. ни на что не указывать). Для нашего примера это означает, что если для сотрудника указан номер отдела, то этот отдел должен существовать. Ограничения целостности сущности и по ссылкам должны поддерживаться СУБД. Для соблюдения целостности сущности достаточно гарантировать отсутствие в любом отношении кортежей с одним и тем же значением первичного ключа. С целостностью по ссылкам дела обстоят несколько более сложно. Понятно, что при обновлении ссылающегося отношения (вставке новых кортежей или модификации значения внешнего ключа в существующих кортежах) достаточно следить за тем, чтобы не появлялись некорректные значения внешнего ключа. Но как быть при удалении кортежа из отношения, на которое ведет ссылка? Здесь существуют три подхода, каждый из которых поддерживает целостность по ссылкам. Первый подход заключается в том, что запрещается производить удаление кортежа, на который существуют ссылки (т.е. сначала нужно либо удалить ссылающиеся кортежи, либо соответствующим образом изменить значения их внешнего ключа). При втором подходе при удалении кортежа, на который имеются ссылки, во всех ссылающихся кортежах значение внешнего ключа автоматически становится неопределенным. Наконец, третий подход (каскадное удаление) состоит в том, что при удалении кортежа из отношения, на которое ведет ссылка, из ссылающегося отношения автоматически удаляются все ссылающиеся кортежи. В развитых реляционных СУБД обычно можно выбрать способ поддержания целостности по ссылкам для каждой отдельной ситуации определения внешнего ключа. Конечно, для принятия такого решения необходимо анализировать требования конкретной прикладной области. Управляющая часть Для управления реляционной базой данных Э.Ф.Кодд ввел реляционные языки обработки данных – реляционную алгебру и реляционное исчисление. Реляционная алгебра – это процедурный язык обработки реляционных таблиц. Здесь используется пошаговый подход к созданию реляционных таблиц. Реляционное исчисление – непроцедурный язык, в котором таблица, содержащая ответы на запросы, определяется за один шаг. Реляционная алгебра Основная идея реляционной алгебры состоит в том, что коль скоро отношения являются множествами, то средства манипулирования отношениями могут базироваться на традиционных множественных операциях, дополненных некоторыми специальными операциями, специфичными для баз данных. Набор основных алгебраических операций состоит из восьми операций, которые делятся на основные и дополнительные. Основные – это объединение, разность, декартово произведение, проекция, выбор. К дополнительным относят пересечение, естественное соединение, соединение и деление. Объединение Объединением двух совместимых по типу отношений и называется отношение с тем же заголовком, что и у отношений и , и телом, состоящим из кортежей, принадлежащих или , или , или обоим отношениям. Синтаксис операции объединения: Замечание . если некоторый кортеж входит и в отношение , и отношение , то в объединение он входит один раз. Пример . Пусть даны два отношения и с информацией о сотрудниках: Таблица 1 - Отношение A Табельный номер Фамилия Зарплата 1 Иванов 1000 2 Пушников 2500 4 Сидоров 3000 Таблица 2 - Отношение B Табельный номер Фамилия Зарплата 1 Иванов 1000 2 Петров 2000 3 Сидоров 3000 2 Пушников 2500 Замечание . Как видно из приведенного примера, потенциальные ключи, которые были в отношениях и не наследуются объединением этих отношений. Поэтому, в объединении отношений и атрибут "Табельный номер" может содержать дубликаты значений. Если бы это было не так, и ключи наследовались бы, то это противоречило бы понятию объединения как "объединение множеств". Конечно, объединение отношений и имеет, как и любое отношение, потенциальный ключ, например, состоящий из всех атрибутов. Пересечение Определение 3 . Пересечением двух совместимых по типу отношений и называется отношение с тем же заголовком, что и у отношений и , и телом, состоящим из кортежей, принадлежащих одновременно обоим отношениям и . Пример 3 . Для тех же отношений и , что и в предыдущем примере пересечение имеет вид: Таблица 4 - Отношение A INTERSECT B Табельный номер Фамилия Зарплата 1 Иванов 1000 Замечание . Казалось бы, что в отличие от операции объединения, потенциальные ключи могли бы наследоваться пересечением отношений. Однако это не так. Вообще, никакие реляционные операторы не передают результатирующему отношению никаких данных о потенциальных ключах . В качестве причины этого можно было бы привести тривиальное соображение, что так получается более просто и симметрично - все операторы устроены одинаково. На самом деле причина более глубока, и заключается в том, что потенциальный ключ - семантическое понятие, отражающее различимость объектов предметной области. Наличие потенциальных ключей не выводится из структуры отношения, а явно задается для каждого отношения, исходя из его смысла. Реляционные же операторы являются формальными операциями над отношениями и выполняются одинаково, независимо от смысла данных, содержащихся в отношениях. Поэтому, реляционные операторы ничего не могут "знать" о смысле данных. Трактовка результата реляционных операций - дело пользователя. Примеры использования реляционных операторов Пример 12 . Получить имена поставщиков, поставляющих деталь номер 2. Решение: Пример 13 . Получить имена поставщиков, поставляющих по крайней мере одну гайку. Решение: Ответ на этот запрос можно получить и иначе: Пример 14 . Получить имена поставщиков, поставляющих все детали. Решение: Пример 15 . Получить имена поставщиков, не поставляющих деталь номер 2. Решение: Ответ на этот запрос можно получить и пошагово: - получить список номеров всех поставщиков - соединить данные о поставщиках и поставках - в данных о поставщиках и поставках оставить только данные о поставках детали номер 2. - получить список номеров поставщиков, поставляющих деталь номер 2. - получить список номеров поставщиков, не поставляющих деталь номер 2. - соединить список номеров поставщиков, не поставляющих деталь номер 2 с данными о поставщиках (получатся полные данные о поставщиках, не поставляющих деталь номер 2). - искомый ответ (имена поставщиков, не поставляющих деталь номер 2). Специальные реляционные операции В этом подразделе мы несколько подробнее рассмотрим специальные реляционные операции реляционной алгебры: ограничение, проекция, соединение и деление. Операция ограничения Операция ограничения требует наличия двух операндов: ограничиваемого отношения и простого условия ограничения. Простое условие ограничения может иметь либо вид (a comp-op b), где а и b - имена атрибутов ограничиваемого отношения, для которых осмысленна операция сравнения comp-op, либо вид (a comp-op const), где a - имя атрибута ограничиваемого отношения, а const - литерально заданная константа. В результате выполнения операции ограничения производится отношение, заголовок которого совпадает с заголовком отношения-операнда, а в тело входят те кортежи отношения-операнда, для которых значением условия ограничения является true. Пусть UNION обозначает операцию объединения, INTERSECT - операцию пересечения, а MINUS - операцию взятия разности. Для обозначения операции ограничения будем использовать конструкцию A WHERE comp, где A - ограничиваемое отношение, а comp - простое условие сравнения. Пусть comp1 и comp2 - два простых условия ограничения. Тогда по определению: · A WHERE comp1 AND comp2 обозначаеттожесамое, чтои (A WHERE comp1) INTERSECT (A WHERE comp2) · A WHERE comp1 OR comp2 обозначаеттожесамое, чтои (A WHERE comp1) UNION (A WHERE comp2) · A WHERE NOT comp1 обозначаеттожесамое, чтои A MINUS (A WHERE comp1) С использованием этих определений можно использовать операции ограничения, в которых условием ограничения является произвольное булевское выражение, составленное из простых условий с использованием логических связок AND, OR, NOT и скобок. На интуитивном уровне операцию ограничения лучше всего представлять как взятие некоторой "горизонтальной" вырезки из отношения-операнда. Операция взятия проекции Операция взятия проекции также требует наличия двух операндов - проецируемого отношения A и списка имен атрибутов, входящих в заголовок отношения A. Результатом проекции отношения A по списку атрибутов a1 , a2 , ..., an является отношение, с заголовком, определяемым множеством атрибутов a1 , a2 , ..., an , и с телом, состоящим из кортежей вида <a1 :v1 , a2 :v2 , ..., an :vn > таких, что в отношении A имеется кортеж, атрибут a1 которого имеет значение v1 , атрибут a2 имеет значение v2 , ..., атрибут an имеет значение vn . Тем самым, при выполнении операции проекции выделяется "вертикальная" вырезка отношения-операнда с естественным уничтожением потенциально возникающих кортежей-дубликатов. Операция соединения отношений Общая операция соединения (называемая также соединением по условию) требует наличия двух операндов - соединяемых отношений и третьего операнда - простого условия. Пусть соединяются отношения A и B. Как и в случае операции ограничения, условие соединения comp имеет вид либо (a comp-op b), либо (a comp-op const), где a и b - имена атрибутов отношений A и B, const - литерально заданная константа, а comp-op - допустимая в данном контексте операция сравнения. Тогда по определению результатом операции сравнения является отношение, получаемое путем выполнения операции ограничения по условию comp прямого произведения отношений A и B. Если внимательно осмыслить это определение, то станет ясно, что в общем случае применение условия соединения существенно уменьшит мощность результата промежуточного прямого произведения отношений-операндов только в том случае, когда условие соединения имеет вид (a comp-op b), где a и b - имена атрибутов разных отношений-операндов. Поэтому на практике обычно считают реальными операциями соединения именно те операции, которые основываются на условии соединения приведенного вида. Хотя операция соединение в нашей интерпретации не является примитивной (поскольку она определяется с использованием прямого произведения и проекции), в силу особой практической важности она включается в базовый набор операций реляционной алгебры. Заметим также, что в практических реализациях соединение обычно не выполняется именно как ограничение прямого произведения. Имеются более эффективные алгоритмы, гарантирующие получение такого же результата. Имеется важный частный случай соединения - эквисоединение и простое, но важное расширение операции эквисоединения - естественное соединение. Операция соединения называется операцией эквисоединения , если условие соединения имеет вид (a = b), где a и b - атрибуты разных операндов соединения. Этот случай важен потому, что (a) он часто встречается на практике, и (b) для него существуют эффективные алгоритмы реализации. Операция естественного соединения применяется к паре отношений A и B, обладающих (возможно составным) общим атрибутом c (т.е. атрибутом с одним и тем же именем и определенным на одном и том же домене). Пусть ab обозначает объединение заголовков отношений A и B. Тогда естественное соединение A и B - это спроектированный на ab результат эквисоединения A и B по A/c и BBC. Если вспомнить введенное нами в конце предыдущей главы определение внешнего ключа отношения, то должно стать понятно, что основной смысл операции естественного соединения - возможность восстановления сложной сущности, декомпозированной по причине требования первой нормальной формы. Операция естественного соединения не включается прямо в состав набора операций реляционной алгебры, но она имеет очень важное практическое значение. Операция деления отношений Эта операция наименее очевидна из всех операций реляционной алгебры и поэтому нуждается в более подробном объяснении. Пусть заданы два отношения - A с заголовком {a1 , a2 , ..., an , b1 , b2 , ..., bm } и B с заголовком {b1 , b2 , ..., bm }. Будем считать, что атрибут bi отношения A и атрибут bi отношения B не только обладают одним и тем же именем, но и определены на одном и том же домене. Назовем множество атрибутов {aj } составным атрибутом a, а множество атрибутов {bj } - составным атрибутом b. После этого будем говорить о реляционном делении бинарного отношения A(a,b) на унарное отношение B(b). Результатом деления A на B является унарное отношение C(a), состоящее из кортежей v таких, что в отношении A имеются кортежи <v, w> такие, что множество значений {w} включает множество значений атрибута b в отношении B. Предположим, что в базе данных сотрудников поддерживаются два отношения: СОТРУДНИКИ ( ИМЯ, ОТД_НОМЕР ) и ИМЕНА ( ИМЯ ), причем унарное отношение ИМЕНА содержит все фамилии, которыми обладают сотрудники организации. Тогда после выполнения операции реляционного деления отношения СОТРУДНИКИ на отношение ИМЕНА будет получено унарное отношение, содержащее номера отделов, сотрудники которых обладают всеми возможными в этой организации именами. Лекция 3. Реляционная алгебра и реляционное исчисление Для управления реляционной базой данных Э.Ф. Кодд ввел реляционные языки обработки данных – реляционную алгебру и реляционное исчисление. Реляционная алгебра – это язык обработки реляционных таблиц, при котором используется пошаговый подход к построению ответа на запрос. Реляционное исчисление – язык, при котором поиск ответа на запрос осуществляется за один шаг. Кодд показал логическую эквивалентность реляционной алгебры и реляционного исчисления, что означает следующее: запрос, сформулированный при помощи реляционного исчисления можно сформулировать, пользуясь реляционной алгеброй и наоборот. В реализациях конкретных реляционных СУБД сейчас не используется в чистом виде ни реляционная алгебра, ни реляционное исчисление. Фактическим стандартом доступа к реляционным данным стал язык SQL (Structured Query Language). Однако язык SQL представляет собой смесь операторов реляционной алгебры и выражений реляционного исчисления, использующий синтаксис, близкий к фразам английского языка. Рассмотрим основы реляционной алгебры. Основная идея реляционной алгебры состоит в том, что коль скоро отношения являются множествами, то средства манипулирования отношениями могут базироваться на традиционных теоретико-множественных операциях, рассматриваемых в алгебре. Реляционная алгебра представляет собой набор операторов, использующих отношения в качестве аргументов, и возвращающие отношения в качестве результата. Традиционно, вслед за Коддом, определяют восемь реляционных операторов, объединенных в две группы. Основные: · Объединение – при выполнении операции объединения двух отношений производится отношение, включающее все кортежи, входящие хотя бы в одно из отношений-операндов. · Пересечение – операция пересечения двух отношений производит отношение, включающее все кортежи, входящие в оба отношения-операнда. · Вычитание – отношение, являющееся разностью двух отношений включает все кортежи, входящие в отношение - первый операнд, такие, что ни один из них не входит в отношение, являющееся вторым операндом. · Декартово (прямое) произведение – при выполнении прямого произведения двух отношений производится отношение, кортежи которого являются конкатенацией (сцеплением) кортежей первого и второго операндов. Дополнительные: · Выборка – результатом ограничения отношения по некоторому условию является отношение, включающее кортежи отношения-операнда, удовлетворяющее этому условию. · Проекция – при выполнении проекции отношения на заданный набор его атрибутов производится отношение, кортежи которого производятся путем взятия соответствующих значений из кортежей отношения-операнда. · Соединение – при соединении двух отношений по некоторому условию образуется результирующее отношение, кортежи которого являются конкатенацией кортежей первого и второго отношений и удовлетворяют этому условию. · Деление – у операции реляционного деления два операнда - бинарное и унарное отношения. Результирующее отношение состоит из одноатрибутных кортежей, включающих значения первого атрибута кортежей первого операнда таких, что множество значений второго атрибута (при фиксированном значении первого атрибута) совпадает со множеством значений второго операнда. В отдельную группу относят операции переименования и присваивания: · Операция переименования производит отношение, тело которого совпадает с телом операнда, но имена атрибутов изменены. · Операция присваивания позволяет сохранить результат вычисления реляционного выражения в существующем отношении БД. Прежде всего условимся, что каждое отношение имеет заголовок (список имен атрибутов) и тело, состоящее из кортежей. Кроме того, каждое отношение имеет имя. Введем следующие обозначения: А – имя отношения, А(А1, А2, …, Аn) – заголовок отношения. Оператор переименования атрибутов Оператор переименования атрибутов имеет следующий синтаксис: где - отношение, - исходные имена атрибутов, - новые имена атрибутов. В результате применения оператора переименования атрибутов получаем новое отношение, с измененными именами атрибутов. Пример 1 . Следующий оператор возвращает неименованное отношение, в котором атрибут переименован в : Объединение Объединением двух совместимых по типу отношений и называется отношение с тем же заголовком, что и у отношений и , и телом, состоящим из кортежей, принадлежащих или , или , или обоим отношениям. Замечание . Объединение не может содержать одинаковых кортежей, поэтому, если некоторый кортеж входит и в отношение , и отношение , то в объединение он входит один раз. Пример 2 . Пусть даны два отношения и с информацией о сотрудниках: Таблица 1 - Отношение A Табельный номер Фамилия Зарплата 1 Иванов 1000 2 Петров 2000 3 Сидоров 3000 Таблица 2 - Отношение B Табельный номер Фамилия Зарплата 1 Иванов 1000 2 Пушников 2500 4 Сидоров 3000 Таблица 3 - Отношение A UNION B Табельный номер Фамилия Зарплата 1 Иванов 1000 2 Петров 2000 3 Сидоров 3000 Замечание . Как видно из приведенного примера, потенциальные ключи, которые были в отношениях и не наследуются объединением этих отношений. Поэтому, в объединении отношений и атрибут "Табельный номер" может содержать дубликаты значений. Естественное соединение Определение 10 . Пусть даны отношения то называть клиентом локальной сети, запрашивающий услуги у некоторого сервера и сервером - компонент локальной сети, оказывающий услуги некоторым клиентам. По отношению к базам данных сервером является программа, выполняющая функции управления и защиты данных в базе. В случае, когда вызов функций сервера выполняется на языке SQL, его называют SQL-сервером (MSSQLServer, Informix). Тогда клиентом является программа, отвечающая за интерфейс с пользователем, для чего используются запросы к серверной части и при получении результатов выполняется отображение информации для пользователя. В роли клиента чаще выступает разрабатываемая для решения конкретной задачи программа или СУБД, имеющая интерфейс с серверной программой (MSAccess, MSFoxPro, Paradox). Архитектура "клиент-сервер" Легко заметить, что в общем случае, чтобы прикладная программа, выполняющаяся на рабочей станции, могла запросить услугу у некоторого сервера, как минимум требуется некоторый интерфейсный программный слой, поддерживающий такого рода взаимодействие. Из этого, собственно, и вытекают основные принципы архитектуры "клиент-сервер". Система разбивается на две части, которые могут выполняться в разных узлах сети, - клиентскую и серверную части. Конечный пользователь взаимодействуют с клиентской частью системы. Клиентская часть при потребности обращается по сети к серверной части. Интерфейс серверной части определен и фиксирован. Архитектура клиент-сервер обладает рядом преимуществ: · обеспечивается более широкий доступ к существующим базам данных; · повышается общая производительность системы: поскольку клиенты и сервер находятся на разных компьютерах, их процессоры способны выполнять приложения параллельно.; · снижается стоимость аппаратного обеспечения; достаточно мощный компьютер с большим устройством хранения нужен только серверу – для хранения и управления базой данных; · сокращаются коммуникационные расходы. Приложения выполняют часть операций на клиентских компьютерах и посылают через сеть только запросы к базам данных, что позволяет значительно сократить объем пересылаемых по сети данных; · повышается уровень непротиворечивости данных. Сервер может самостоятельно управлять проверкой целостности данных, поскольку лишь на нем определяются и проверяются все ограничения. При этом каждому приложению не придется выполнять собственную проверку. Технология клиент-сервер разделяет работу с базой данных на две части: – клиентская часть обеспечивает интерактивный, легкий в использовании, обычно графический интерфейс работы с базой – заполнение, ведение, поиск и выборку информации, формирование отчетов. Обычно в клиентской части выделяют следующие группы функций: – функции ввода и отображения данных; – функции обработки данных внутри приложения, при этом результаты обработки хранятся на локальной машине, на которой установлена клиентская часть; – сервер обеспечивает управление данными, разделение информации, администрирование и безопасность. Находится на специально выделенных компьютерах, хранящих базы данных. При технологии клиент-сервер клиентское приложение формирует запрос к серверу БД, на котором выполняются все команды. Результаты команд посылаются затем клиенту для использования и просмотра. Все результаты запросов хранятся на компьютере клиентской части. Модели технологии «клиент-сервер» Если все функции распределяются только между клиентом и сервером, говорят, что речь идет о двухуровневой модели «клиент-серверной» технологии . Существует несколько разновидностей такой модели. Файловый сервер При такой организации сервера предполагается следующее распределение функций: на клиенте располагаются почти все части приложения: функции ввода и отображения, функции управления информационными ресурсами. Файловый сервер содержит файлы, необходимые для обработки запросов клиентской части и самой СУБД и поддерживает доступ к файлам данных. СУБД посылает запросы файловому серверу по всем необходимым ей данным. Запрос клиента формируется в командах языка манипулирования данными. СУБД переводит этот запрос в последовательность файловых команд, осуществляющих пересылку информации на клиента, которая затем анализируется клиентом. Передача файлов представляет собой длительную процедуру, поэтому в результате возникают ряд проблем: низкая производительность, усложнение определения целостности базы данных и т.д. Сервер баз данных Термин "сервер баз данных" обычно используют для обозначения СУБД, основанной на архитектуре "клиент-сервер", включая и серверную, и клиентскую части. В этом случае база данных также хранится удаленно на сервере. Здесь же находится ядро СУБД. На клиенте располагаются части приложения, поддерживающие функции ввода и отображения данных. Такой подход имеет ряд преимуществ. Сервер принимает и обрабатывает запросы со стороны клиентов, проверяет полномочия пользователей, гарантирует соблюдение ограничений целостности, выполняет обновление данных, выполняет запросы и возвращает результаты клиенту, обеспечивает одновременный доступ к базе пользователей и ее целостность. В результате клиент получает только ответ на запрос, а не блоки информации, среди которой надо отыскивать необходимую. 1. Принципы взаимодействия между клиентскими и серверными частями. Доступ к базе данных от прикладной программы или пользователя производится путем обращения к клиентской части системы. В качестве основного интерфейса между клиентской и серверной частями выступает язык баз данных SQL. Серверы баз данных, интерфейс которых основан исключительно на языке SQL, обладают своими преимуществами и своими недостатками. Очевидное преимущество - стандартность интерфейса. Клиентские части любой SQL-ориентированной СУБД могли бы работать с любым SQL-сервером вне зависимости от того, кто его произвел. Недостаток тоже довольно очевиден. При таком высоком уровне интерфейса между клиентской и серверной частями системы на стороне клиента работает слишком мало программ СУБД. Это нормально, если на стороне клиента используется маломощная рабочая станция. Но если клиентский компьютер обладает достаточной мощностью, то часто возникает желание возложить на него больше функций управления базами данных, разгрузив сервер, который является узким местом всей системы. 2. Типичное разделение функций между клиентами и серверами В типичном на сегодняшний день случае на стороне клиента СУБД работает только такое программное обеспечение, которое не имеет непосредственного доступа к базам данных, а обращается для этого к серверу с использованием языка SQL. Из предыдущих рассуждений видно, что требования к аппаратуре и программному обеспечению клиентских и серверных компьютеров различаются в зависимости от вида использования системы. Если разделение между клиентом и сервером достаточно жесткое (как в большинстве современных СУБД), то пользователям, работающим на рабочих станциях или персональных компьютерах, абсолютно все равно, какая аппаратура и операционная система работают на сервере, лишь бы он справлялся с возникающим потоком запросов. Но если могут возникнуть потребности перераспределения функций между клиентом и сервером, то уже совсем не все равно, какие операционные системы используются. Трехуровневая модель технологии «клиент-сервер» Она является расширением двухуровневой модели и в нее вводится дополнительный элемент – посредник между клиентом и сервером. Таким посредником является сервер приложений . В такой модели клиенту отводятся те же функции. Сервер базы данных занимается исключительно функциями создания и ведения базы данных, поддержания ее целостности, восстановления базы после сбоев и т.д. Сервер приложений выполняет общие функции клиентов, работа с каталогами, обмен сообщениями и т.д. Основные объекты структуры базы данных SQL-сервера К основным объектам базы данных SQL Server относятся объекты, представленные в таблице: Tables Таблицы базы данных, в которых хранятся собственно данные Views Просмотры (виртуальные таблицы) для отображения данных из таблиц Indexes Индексы – дополнительные структуры, призванные повысить производительность работы с данными Keys Ключи – один из видов ограничений целостности данных Constraints Ограничение целостности – объекты для обеспечения логической целостности данных Roles Роли, позволяющие объединять пользователей в группы Приведем краткий обзор основных объектов баз данных. Таблицы Все данные в SQL содержатся в объектах, называемых таблицами. Таблицы представляют собой совокупность каких-либо сведений об объектах, явлениях, процессах реального мира. Никакие другие объекты не хранят данные, но они могут обращаться к данным в таблице. Представления. Представлениями (просмотрами) называют виртуальные таблицы, содержимое которых определяется запросом. Подобно реальным таблицам, представления содержат именованные столбцы и строки с данными. Для конечных пользователей представление выглядит как таблица, но в действительности оно не содержит данных, а лишь представляет данные, расположенные в одной или нескольких таблицах. Информация, которую видит пользователь через представление, не сохраняется в базе данных как самостоятельный объект. Индексы Индекс – структура, связанная с таблицей или представлением и предназначенная для ускорения поиска информации в них. Индекс определяется для одного или нескольких столбцов, называемых индексированными столбцами. Он содержит отсортированные значения индексированного столбца или столбцов со ссылками на соответствующую строку исходной таблицы или представления. Повышение производительности достигается за счет сортировки данных. Использование индексов может существенно повысить производительность поиска, однако для хранения индексов необходимо дополнительное пространство в базе данных. Индексы – это наборы уникальных значений для некоторой таблицы с соответствующими ссылками на данные. Расположенные в самой таблице, они являются удобным внутренним механизмом системы SQL-сервера, с помощью которого осуществляется доступ к данным наиболее оптимальным способом. В среде SQL Server реализованы эффективные алгоритмы поиска нужного значения в строго определенной последовательности данных. Ускорение поиска достигается именно за счет того, что данные представляются упорядоченными (хотя физически, в зависимости от типа индекса, они могут храниться в соответствии с очередностью их добавления в таблицу). К настоящему времени разработаны эффективные математические алгоритмы поиска данных в упорядоченной последовательности. Создание индекса. Если выборка данных из таблицы требует значительного времени, это означает, что для нее необходимо создать индекс. Индексы могут существенно повысить производительность выполнения операций поиска и выборки данных. При выборе столбца для индекса следует проанализировать, какие типы запросов чаще всего выполняются пользователями и какие столбцы являются ключевыми, т.е. задающими критерии выборки данных, например, порядок сортировки. В среде SQL Server реализовано несколько типов индексов: · кластерные индексы; · некластерные индексы; · уникальные индексы. Некластерный индекс Некластерные индексы – наиболее типичные представители семейства индексов. В отличие от кластерных, они не перестраивают физическую структуру таблицы, а лишь организуют ссылки на соответствующие строки. Для идентификации нужной строки в таблиценекластерный индекс организует специальные указатели, включающие в себя: · информацию об идентификационном номере файла, в котором хранится строка; · идентификационный номер страницы соответствующих данных; · номер искомой строки на соответствующей странице; · содержимое столбца. В большинстве случаев следует ограничиваться 4-5 индексами. Кластерный индекс Принципиальным отличием кластерного индекса от индексов других типов является то, что при его определении в таблице физическое расположение данных перестраивается в соответствии со структурой индекса. Логическая структура таблицы в этом случае представляет собой скорее словарь, чем индекс. Данные в словаре физически упорядочены, например по алфавиту. Кластерные индексы могут дать существенное увеличение производительности поиска данных даже по сравнению с обычными индексами. Увеличение производительности особенно заметно при работе с последовательными данными. Если в таблице определен некластерный индекс, то сервер должен сначала обратиться к индексу, а затем найти нужную строку в таблице. При использовании кластерных индексов следующая порция данных располагается сразу после найденных ранее данных. Благодаря этому отпадают лишние операции, связанные с обращением к индексу и новым поиском нужной строки в таблице. Естественно, в таблице может быть определен только один кластерный индекс. В качестве такового следует выбирать наиболее часто используемые столбцы. При этом стоит следовать общим рекомендациям создания индексов и не индексировать слишком длинные столбцы. Кластерный индекс может включать несколько столбцов. Однако количество таких столбцов рекомендуется по возможности свести к минимуму. Необходимо избегать созданиякластерного индекса для часто изменяемых столбцов, поскольку сервер должен будет выполнять физическое перемещение всех данных в таблице, чтобы они находились в упорядоченном состоянии, как того требует кластерный индекс. Для интенсивно изменяемых столбцов лучше подходит некластерный индекс. При создании в таблице первичного ключа сервер автоматически создает для него кластерный индекс, если его не существовало ранее или если при определении ключа не был явно указан другой тип индекса. Когда же в таблице определен еще и некластерный индекс, то его указатель ссылается не на физическое положение строки в базе данных, а на соответствующий элемент кластерного индекса, описывающего эту строку, что позволяет не перестраивать структуру некластерных индексов всякий раз, когда кластерный индекс меняет физический порядок строк в таблице. Уникальный индекс Уникальность значений в индексируемом столбце гарантируют уникальные индексы. При их наличии сервер не разрешит вставить новое или изменить существующее значение таким образом, чтобы в результате этой операции в столбце появились два одинаковых значения. Уникальный индекс является своеобразной надстройкой и может быть реализован как для кластерного, так и для некластерного индекса. В одной таблице может существовать один уникальный кластерный и множество уникальных некластерных индексов. Уникальные индексы следует определять только тогда, когда это действительно необходимо. Для обеспечения целостности данных в столбце можно определить ограничение целостности, а не прибегать к уникальным индексам. Их использование только для обеспечения целостности данных является неоправданной тратой пространства в базе данных. Кроме того, на их поддержание тратится и процессорное время. Средства языка SQL предлагают несколько способов определения индекса: · автоматическое создание индекса при создании первичного ключа; · автоматическое создание индекса при определении ограничения целостности; · создание индекса с помощью команды. Имя индекса должно быть уникальным в пределах таблицы, а сам индекс создается исключительно для таблицы текущей базы данных. Ограничения целостности Ограничения целостности – механизм, обеспечивающий автоматический контроль соответствия данных установленным условиям (или ограничениям). К ограничениям целостности относятся: ограничение на значение NULL, ограничение первичного ключа и ограничение внешнего ключа. 2. Типы данных языка SQL, с помощью которых можно определять данные в таблице В языке SQL имеется шесть скалярных типов данных, определенных стандартом. Их краткое описание представлено в таблице. Символьные данные Символьные данные состоят из последовательности символов, входящих в определенный создателями набор символов. При определении столбца с символьным типом данных параметр длина применяется для указания максимального количества символов, которые могут быть помещены в данный столбец (по умолчанию принимается значение 1). Для хранения символьной информации используются символьные типы данных, к которым относятся CHAR (длина) и VARCHAR (длина).Хранение символьных данных большого объема (до 2 Гб) осуществляется при помощи текстовых типов данных TEXT. Битовые данные Битовый тип данных используется для определения битовых строк, т.е. последовательности двоичных цифр (битов). Тип данных BIT позволяет хранить один бит, который принимает значения 0 или 1. Точные числа Тип точных числовых данных применяется для определения чисел, которые имеют точное представление, т.е. числа состоят из цифр, необязательной десятичной точки и необязательного символа знака. Данные точного числового типа определяются точностью и длиной дробной части. Точность задает общее количество значащих десятичных цифр числа, в которое входит длина как целой части, так и дробной, но без учета самой десятичной точки. Масштаб указывает количество дробных десятичных разрядов числа. К целочисленным типам данных относятся INT (INTEGER), SMALLINT, TININT, BIGINT. Для хранения данных целочисленного типа используется, соответственно, 4 байта (диапазон от -231 до 231 -1), 2 байта (диапазон от -215 до 215 -1), 1 байт (диапазон от 0 до 255) или 8 байт (диапазон от -263 до 263 -1). Объекты и выражения целочисленного типа могут применяться в любых математических операциях. Типы NUMERIC и DECIMAL предназначены для хранения чисел в десятичном формате. По умолчанию длина дробной части равна нулю, а принимаемая по умолчанию точность зависит от реализации. Тип INTEGER (INT) используется для хранения больших положительных или отрицательных целых чисел. Тип SMALLINT – для хранения небольших положительных или отрицательных целых чисел; в этом случае расход внешней памяти существенно сокращается. Округленные числа Тип округленных чисел применяется для описания данных, которые нельзя точно представить в компьютере, в частности действительных чисел. Округленные числа или числа с плавающей точкой представляются в научной нотации, при которой число записывается с помощью мантиссы, умноженной на определенную степень десяти (порядок), например: 10Е3, +5.2Е6, -0.2Е-4. Точность типов REAL и FLOAT зависит от конкретной реализации. Числа, в составе которых есть десятичная точка, называются нецелочисленными. Нецелочисленные данные разделяются на два типа – десятичные и приблизительные. К десятичным типам данных относятся типы DECIMAL [(точность[,масштаб])] или DEC и NUMERIC [(точность[,масштаб])]. Типы данных DECIMAL и NUMERIC позволяют самостоятельно определить формат точности числа с плавающей запятой. Параметр точность указывает максимальное количество цифр вводимых данных этого типа (до и после десятичной точки в сумме), а параметр масштаб – максимальное количество цифр, расположенных после десятичной точки. В обычном режиме сервер позволяет вводить не более 28 цифр, используемых в типах DECIMAL и NUMERIC (от 2 до 17 байт). К приблизительным типам данных относятся FLOAT (точность до 15 цифр, 8 байт) и REAL (точность до 7 цифр, 4 байта). Эти типы представляют данные в формате с плавающей запятой, т.е. для представления чисел используется мантисса и порядок, что обеспечивает одинаковую точность вычислений независимо от того, насколько мало или велико значение. Дата и время Тип данных «дата/время» используется для определения моментов времени с некоторой установленной точностью. Для хранения информации о дате и времени предназначены такие типы данных, как DATETIME и SMALLDATETIME, использующие для представления даты и времени 8 и 4 байта соответственно. Тип данных DATETIME используется для совместного хранения даты и времени: хранения календарных дат, включающих поля YEAR (год), MONTH (месяц) и DAY (день) и хранения отметок времени, включающих поля HOUR (часы), MINUTE (минуты) и SECOND (секунды). Данные типа INTERVAL используются для представления периодов времени. Финансовые типы данных Типы данных MONEY и SMALLMONEY делают возможным хранение информации денежного типа; они обеспечивают точность значений до 4 знаков после запятой и используют 8 и 4 байта соответственно. Работа с внешними данными с помощью технологии ODBC Важнейшим этапом в построении приложения клиент-сервер является установка связи клиентского приложения с источником данных, находящимся на сервере БД. В настоящий момент различные средства разработки используют несколько технологий обеспечения доступа к данным. Общепризнанным стандартом является технология ODBC. ODBC – Open Database Connectivity – о ткрытый доступ к данным – это общее определение языка и набор протоколов. ODBC позволяет клиентскому приложению, например, Access или Visual FoxPro, работать с командами и функциями, поддерживаемыми сервером. ODBC находится как бы посредине между приложением, использующем данные, и самими данными, хранящимися на сервере, которые мы не можем обработать напрямую в приложении, и используется как средство коммуникации между двумя сторонами технологии – клиентом и сервером. Для использования ODBC с целью получения данных в сети вам необходимы средства коммуникации между машиной, на которой находятся данные, и машиной, где они будут просматриваться, модифицироваться и обрабатываться. Канал связи между машинами устанавливается один раз и может быть использован много раз для разработки различных приложений по работе с одной и той же базой. При создании соединения возможны следующие варианты: создание файлового соединения (все настройки канала связи сохраняются в виде отдельного файла и могут переноситься с одной машины на другую); создание машинного соединения (все настройки канала связи записываются в реестр операционной системы). Создание канала связи состоит из нескольких этапов: – выбор драйвера СУБД, с которой будет выполняться связь (MSSQLServer), – выбор сервера, с которым осуществляется связь с указанием имени этой машины (имя сервера в сети, если речь идет о локальной сети, и IP-адрес, если речь идет об удаленном доступе к серверу); – выбор базы данных, с которой устанавливается связь, так как на сервере может храниться большое количество баз. Для определения связи используется специальная программа – Администратор ODBC, и драйверы, которые могут работать как с приложением, так и с данными на сервере. Для MSSQLServer используются ODBC драйверы, разработанные Microsoft. Одна из главных целей создания ODBC - скрыть сложность соединения с сервером и по мере возможности автоматизировать выполнение многочисленных процедур, связанных с получением данных. Лекция 4. Фрактальные методы сжатия больших объемов данных 1. Фракталы и история возникновения метода фрактального сжатия В декабре 1992 года, перед самым Рождеством, компания Microsoft выпустила свой новый компакт-диск Microsoft Encarta. С тех пор эта мультимедиа-энциклопедия, содержащая информацию о животных, цветах, деревьях и живописных местах, не покидает списки наиболее популярных энциклопедий на компакт-дисках. В недавнем опросе Microsoft Encarta опять заняла первое место, опередив ближайшего конкурента - Комптоновскую мультимедиа-энциклопедию. Причина подобной популярности кроется в удобстве использования, высоком качестве статей и, главное, в большом количестве материалов. На диск записано 7 часов звука, 100 анимационных роликов, примерно 800 масштабируемых карт, а также 7000.качественных фотографий. И все это - на одном диске! Напомним, что обычный компакт-диск в 650 Мбайт без использования компрессии может содержать либо 56 минут качественного звука, либо 1 час видео разрешения с разрешением 320х200 в формате MPEG-1, либо 700 полноцветных изображений размером 640х480. Чтобы разместить больше информации, необходимы достаточно эффективные алгоритмы архивации. Мы не будем останавливаться на методах архивации для видео и звука. Речь пойдет о новом перспективном алгоритме - фрактальном сжатии графической информации. Понятия «фрактал» и «фрактальная геометрия» (fractus – состоящий из фрагментов, лат.) были предложены математиком Б. Мандельбротом в 1975 г. для обозначения нерегулярных, но самоподобных структур. Рождение фрактальной геометрии обычно связывают с выходом в 1977 году книги Б. Мандельброта "Фрактальная геометрия природы". Одна из основных идей книги заключалась в том, что средствами традиционной геометрии (то есть используя линии и поверхности), чрезвычайно сложно представить природные объекты. Фрактальная геометрия задает их очень просто. Определение фрактала, данное Мандельбротом, звучит так: "Фракталом называется структура, состоящая из частей, которые в каком-то смысле подобны целому" Одним из основных свойств фракталов является самоподобие. В самом простом случае небольшая часть фрактала содержит информацию о всём фрактале. Фракталы, эти красивые образы динамических систем, ранее использовались в машинной графике в основном для построения изображений неба, листьев, гор, травы. Красивое и, что важнее, достоверно имитирующее природный объект изображение могло быть задано всего несколькими коэффициентами. Существует большое разнообразие фракталов. Потенциально наиболее полезным видом фракталов являются фракталы на основе системы итеративных функций (Iterated Function System – IFS) . Метод IFS применительно к построению фрактальных изображений, изобретённый большим их знатоком Майклом Барнсли (Michael Barnsley) и его коллегами из Технологического института шт. Джорджия (Georgia Institute of Technology) , базируется на самоподобии элементов изображения и заключается в моделировании рисунка несколькими меньшими фрагментами его самого. Специальные уравнения позволяют переносить, поворачивать и изменять масштаб участков изображения; таким образом, эти участки служат компоновочными блоками остальной части картины. Одним из наиболее поразительных (и знаменитых) IFS -изображений является чёрный папоротник, в котором каждый лист в действительности представляет собой миниатюрный вариант самого папоротника (см. рис.). Несмотря на то, что картинка создана компьютером методом аффинных преобразований, папоротник выглядит совершенно как настоящий. Выдвинуто предположение, что природа при кодировании генетической структуры растений и деревьев пользуется чем-то близким к методу IFS -фракталов. IFS -фракталы имеют одно вполне реальное и полезное применение: с их помощью можно сжимать большие растровые изображения до долей их нормальных размеров. Этот утверждение следует из теоремы Банаха о сжимающих преобразованиях (также известной как Collage Theorem ) и является результатом работы исследователя Технологического института шт. Джорджия Майкла Барнсли в области IFS . Вооружившись этим выводом, он ушёл из института, запатентовал свое открытие и основал компанию Iterated Systems Incorporated . О своём достижении он рассказал миру в журнале Byte за январь 1988 г. Однако там отсутствовали какие-либо сведения о решении обратной задачи: как по заданному изображению найти аффинные преобразования. К тому моменту у этой задачи не было даже намёка на решение. В статье Барнсли было показано несколько реалистичных фрактальных изображений, но все они были созданы вручную. В идеале хотелось бы уметь находить для любого изображения систему аффинных преобразований (IFSM) , воспроизводящую изображение с заданной точностью. Однако решение находилось немного в стороне. Первым нашёл его именно студент Барнсли, Арно Жакан (Arnaud Jacquin) . Предложенный метод получил название «Система итерируемых кусочно-определённых функций» (Partitioned Iterated Function System – PIFS) . Согласно этой схеме, отдельные части изображения подобны не всему изображению, а только его частям. 2. Математические основы фрактального сжатия Фрактальные методы сжатия позволяют сжать информацию в 10 000 раз. Все известные программы фрактальной компрессии базируются на алгоритме Джеквина – сотрудника Барнсли, который в 1992 году при защите диссертации описал практический алгоритм фрактального сжатия. Несомненным достоинством работы было то, что вмешательство человека в процесс сжатия удалось полностью исключить. Рассмотрим механизм фрактального сжатия данных. Фрактальная архивация основана на том, что с помощью коэффициентов системы итерируемых функций изображение представляется в более компактной форме. Прежде чем рассматривать процесс архивации, разберем, как IFS строит изображение. Строго говоря, IFS - это набор трехмерных аффинных преобразований, переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (x координата, у координата, яркость). Наиболее наглядно этот процесс продемонстрировал сам Барнсли в своей книге "Фрактальное сжатие изображения". В ней введено понятие Фотокопировальной Машины, состоящей из экрана, на котором изображена исходная картинка, и системы линз, проецирующих изображение на другой экран. Каждая линза проецирует часть исходного изображения. Расставляя линзы и меняя их характеристики, можно управлять получаемым изображением. На линзы накладывается требование они должны уменьшать в размерах проектируемую часть изображения. Кроме того, они могут менять яркость фрагмента и проецируют не круги, а области с произвольной границей. Одна шаг Машины состоит в построении с помощью проецирования по исходному изображению нового. Утверждается, что на некотором шаге изображение перестанет изменяться. Оно будет зависеть только от расположения и характеристик линз и не будет зависеть от исходной картинки. Это изображение называется неподвижной точкой или аттрактором данной IFS. Collage Theorem гарантирует наличие ровно одной неподвижной точки для каждой IFS. Поскольку отображение линз является сжимающим, каждая линза в явном виде задает самоподобные области в нашем изображении. Благодаря самоподобию мы получаем сложную структуру изображения при любом увеличении. Наиболее известны два изображения, полученных с помощью IFS треугольник Серпинского и папоротник Барнсли Первое задается тремя, а второе - питью аффинными преобразованиями (или, в нашей терминологии, линзами). Каждое преобразование задается буквально считанными байтами, в то время, как изображение, построенное с их помощью, может занимать и несколько мегабайт. Становится понятно, как работает архиватор, и почему ему требуется так много времени. Фактически, фрактальная компрессия - это поиск самоподобных областей в изображении и определение для них параметров аффинных преобразований. В худшем случае, если не будет применяться оптимизирующий алгоритм, потребуется перебор и сравнение всех возможных фрагментов изображения разного размера. Даже для небольших изображений при учете дискретности мы получим астрономическое число перебираемых вариантов. Даже резкое сужение классов преобразований, например, за счет масштабирования только в определенное число раз, не позволит добиться приемлемого времени. Кроме того, при этом теряется качество изображения. Подавляющее большинство исследований в области фрактальной компрессии сейчас направлены на уменьшение времени архивации, необходимого для получения качественного изображения. Итак, рассмотрим математическое обоснование возможности фрактального сжатия. Есть отображение , где – множество всех возможных изображений. W является объединением отображений wi : (1) где R – изображение, а di – какие-то (возможно, перекрывающиеся) области изображения D . Каждое преобразование wi переводит di в ri . Таким образом: (2) Такие отображения называются сжимающими , и для них справедливо следующее утверждение: Если к какому-то изображению F0 мы начнём многократно применять отображение W таким образом, что (5) то в пределе, при i , стремящемся к бесконечности, мы получим одно и то же изображение вне зависимости от того, какое изображение мы взяли в качестве F0 : (6) Это конечное изображение F называют аттрактором , или неподвижной точкой отображения W . Также известно, что если преобразования wi являются сжимающими, то их объединение W тоже является сжимающим. 3. Типовая схема фрактального сжатия С учётом вышесказанного, схема компрессии выглядит так: изображение R разбивают на кусочки ri , называемые ранговыми областями . Далее для каждой области ri находят область di и преобразование wi такие, что выполняются следующие условия: 1. di по размерам больше ri . 2. wi (ri ) имеет ту же форму, размеры и положение, что и ri . 3. Коэффициент u преобразования wi должен быть меньше единицы. 4. Значение должно быть как можно меньше. Первые три условия означают, что отображение wi будет сжимающим. А в силу четвёртого условия кодируемое изображение R и его образ W (R) будут похожи друг на друга. В идеале R = W (R) . А это означает, что наше изображение R и будет являться неподвижной точкой W . Именно здесь используется подобие различных частей изображения (отсюда и название – «фрактальная компрессия» ). Как оказалось, практически все реальные изображения содержат такие похожие друг на друга, с точностью до аффинного преобразования, части. Таким образом, для компрессии изображения W нужно: 1. Разбить изображение на ранговые области ri (непересекающиеся области, покрывающие все изображение). 2. Для каждой ранговой области ri найти область di (называемую доменной ), и отображение wi , с указанными выше свойствами. 3. Запомнить коэффициенты аффинных преобразований W , положения доменных областей di , а также разбиение изображения на домены. Соответственно, для декомпрессии изображения нужно будет: 1. Создать какое-то (любое) начальное изображение R0 . 2. Многократно применить к нему отображение W (объединение wi ). 3. Так как отображение W сжимающее, то в результате, после достаточного количества итераций, изображение придёт к аттрактору и перестанет меняться. Аттрактор и является нашим исходным изображением. Декомпрессия завершена. Именно это и позволяет при развертывании увеличивать его в несколько раз. Особенно впечатляют примеры, в которых при увеличении изображений природных объектов проявляются новые детали, действительно этим объектам присущие (например, когда при увеличении фотографии скалы она приобретает новые, более мелкие неровности). 4. Оценка коэффициента сжатия и вычислительных затрат Размер данных для полного определения ранговой области рассчитывается по формуле: (10) где X – количество бит, необходимых для хранения координат нижнего левого угла домена, T – количество бит, необходимых для хранения типа аффинного преобразования, U и V – для хранения коэффициентов контраста и яркости. (11) где Nb и Mb – количество бит, необходимых для хранения каждой из координат, рассчитываются по следующим формулам: (12) Здесь CEIL – функция округления до максимального целого, Md и Nd – количество доменов, умещающихся по горизонтали и вертикали, которые рассчитываются по формулам: (13) где V и H – вертикальный и горизонтальный размеры изображения, Size – размер доменного блока, Step – шаг поиска доменной области. Для хранения преобразования T необходимо 3 бита. Для хранения U и V необходимо 9 и 7 бит соответственно. Для примера возьмём изображение размером 256x256 пикселей, и будем исследовать доменную область с шагом 4 пикселя. Nd = Md = (256 - 8 + 1) / 4 = 62 Nb = Mb = CEIL (log2 62) = 6 Х = 12 Z = 12 + 3 + 6 + 6 = 27 Коэффициент сжатия S составляет S = (8 * 8 * 8) / 27 = 19 Коэффициент сжатия не так велик, как хотелось бы, но и параметры сжатия далеко не оптимальны, и коэффициент может увеличиваться в разы. А теперь оценим вычислительную сложность данного алгоритма. На этапе компрессии мы должны перебрать все доменные области – 1'024 штуки, для каждой – все ранговые – 58'081 штука (при шаге 1), а для каждой из них, в свою очередь, – все 8 преобразований. Итого получается 1'024 х 58'081 х 8 = 475'799'552 действия. При этом эти действия не тривиальны и включают несколько матричных операций, которые, в свою очередь, включают операции умножения и деления чисел с плавающей точкой. К сожалению, даже на современном ПК (а именно для таких машин хотелось реализовать алгоритм) понадобится недопустимо много времени для того, чтобы сжать изображение размером всего 256 х 256 пикселов. Очевидно, что рассмотренный алгоритм нуждается в оптимизации. Лекция 5. Нормальные формы отношений В процессе проектирования базы данных возникают вопросы: хорошо ли спроектированы отношения между сущностями? Правильно ли они отражают предметную область? На стадии физической реализации базы данных отношения преобразуются в таблицы, атрибуты становятся столбцами таблиц, для ключевых атрибутов создаются уникальные индексы, домены преображаются в типы данных, принятые в конкретной СУБД. При этом также возникают вопросы: хорошо ли спроектированы таблицы? Правильно ли выбраны индексы? Для ответа на этот вопрос необходимо рассмотреть понятие нормальной формы. Рассмотрим в качестве примера предметной области некоторую организацию, выполняющую проекты. Модель предметной области опишем следующим неформальным текстом: 1. Сотрудники организации выполняют проекты. 2. Проекты состоят из нескольких заданий. 3. Каждый сотрудник может участвовать в одном или нескольких проектах, или временно не участвовать ни в каких проектах. 4. Над каждым проектом может работать несколько сотрудников, или временно проект может быть приостановлен, тогда над ним не работает ни один сотрудник. 5. Над каждым заданием в проекте работает ровно один сотрудник. 6. Каждый сотрудник числится в одном отделе. 7. Каждый сотрудник имеет телефон, находящийся в отделе сотрудника. 8. О каждом сотруднике необходимо хранить табельный номер и фамилию. Табельный номер является уникальным для каждого сотрудника. 9. Каждый отдел имеет уникальный номер. 10. Каждый проект имеет номер и наименование. Номер проекта является уникальным. 11. Каждая работа из проекта имеет номер, уникальный в пределах проекта. Работы в разных проектах могут иметь одинаковые номера. Начинающий проектировщик будет использовать отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ (Номер сотрудника , ФИО, номер отдела, телефон, номер проекта , название проекта, номер задания), имеющее сложный ключ). Действительно, зачем разбивать данное отношение на несколько более мелких отношений, если оно заключает в себе все данные? А разбивать надо потому, что при использовании универсального отношения возникает несколько проблем: 1. Проблема избыточности . Даже одного взгляда на отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ достаточно, чтобы увидеть, что данные хранятся в ней с большой избыточностью . Во многих строках повторяются фамилии сотрудников, номера телефонов, наименования проектов. Кроме того, в данном отношении хранятся вместе независимые друг от друга данные - и данные о сотрудниках, и об отделах, и о проектах, и о работах по проектам. Пока никаких действий с отношением не производится, это не страшно. Но как только состояние предметной области изменяется, то, при попытках соответствующим образом изменить состояние базы данных, возникает большое количество проблем. 2. Аномалии обновления . Вследствие избыточности можно обновить телефон отдела для одного сотрудника, оставляя его неизменным в других строках. Следовательно, при обновлениях необходимо просматривать всю таблицу для нахождения и изменения всех подходящих строк. Причина аномалии - избыточность данных, также порожденная тем, что в одном отношении хранится разнородная информация. Вывод - увеличивается сложность разработки базы данных. База данных, основанная на такой модели, будет работать правильно только при наличии дополнительного программного кода в виде триггеров. 3. Аномалии включения . В отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ нельзя вставить данные о сотруднике, который пока не участвует ни в одном проекте. Действительно, если, например, во втором отделе появляется новый сотрудник, скажем, Пушников, и он пока не участвует ни в одном проекте, то мы должны вставить в отношение кортеж (4, Пушников, 2, 33-22-11, null, null, null). Это сделать невозможно, т.к. атрибут Н_ПРО (номер проекта) входит в состав сложного ключа, и, следовательно, не может содержать null-значений. Точно также нельзя вставить данные о проекте, над которым пока не работает ни один сотрудник. Причина аномалии - хранение в одном отношении разнородной информации (и о сотрудниках, и о проектах, и о работах по проекту). Вывод - логическая модель данных неадекватна модели предметной области. База данных, основанная на такой модели, будет работать неправильно. 4. Аномалии удаления . При удалении некоторых данных может произойти потеря другой информации. Например, если закрыть проект "СУЭД" и удалить все строки, в которых он встречается, то будут потеряны все данные о сотруднике Петрове П.П.. Кроме того будет потеряна информация о том, что в отделе номер 2 имеется телефон под номером 25-54-54. Причина аномалии - хранение в одном отношении разнородной информации (и о сотрудниках, и о проектах, и о работах по проекту). Вывод - логическая модель данных неадекватна модели предметной области. База данных, основанная на такой модели, будет работать неправильно. 1НФ (Первая Нормальная Форма) Говорят, что отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ находится в 1НФ. Первая нормальная форма (1НФ ) - это обычное отношение. Любое отношение автоматически уже находится в 1НФ. Свойства 1НФ: · В отношении нет одинаковых кортежей. · Кортежи не упорядочены. · Все значения атрибутов атомарны. В 1 НФ модель данных не адекватна модели предметной области. Следовательно, первой нормальной формы недостаточно для правильного моделирования данных. Для устранения указанных аномалий (а на самом деле для правильного проектирования модели данных !) применяется метод нормализации отношений . Нормализация основана на понятии функциональной зависимости атрибутов отношения. Функциональная зависимость - семантическое понятие, она возникает, когда по значениям одних данных в предметной области можно определить значения других данных. Например, зная табельный номер сотрудника, можно определить его фамилию, по номеру отдела можно определить телефона. В отношении СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ можно привести следующие примеры функциональных зависимостей: от ключа {Н_СОТР , Н_ПРО } зависят следующие атрибуты ФИО, номер отдела, телефон, название проекта, номер задания; от номера сотрудника зависят следующие атрибуты ФИО, номер отдела, телефон; от номера проекта зависит наименование проекта; от номера отдела зависит номер телефона; Замечание . Эти зависимости отражают взаимосвязи, обнаруженные между объектами предметной области. 2НФ (Вторая Нормальная Форма) Отношение находится во второй нормальной форме (2НФ ) тогда и только тогда, когда оно находится в 1НФ и нет неключевых атрибутов, зависящих от части сложного ключа . (Неключевой атрибут - это атрибут, не входящий в состав никакого потенциального ключа). Замечание . Если ключ отношения является простым, то отношение автоматически находится в 2НФ. Отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ не находится в 2НФ, т.к. есть атрибуты, зависящие от части сложного ключа: зависимость атрибутов, характеризующих сотрудника от табельного номера сотрудника является зависимостью от части сложного ключа, зависимость наименования проекта от номера проекта является зависимостью от части сложного ключа. Для того, чтобы устранить зависимость атрибутов от части сложного ключа, нужно произвести декомпозицию отношения на несколько отношений. При этом те атрибуты, которые зависят от части сложного ключа, выносятся в отдельное отношение. Отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ декомпозируем на три отношения - СОТРУДНИКИ_ОТДЕЛЫ , ПРОЕКТЫ , ЗАДАНИЯ . Отношение СОТРУДНИКИ_ОТДЕЛЫ (Н_СОТР , ФИО , Н_ОТД , ТЕЛ ): Функциональные зависимости: Зависимость атрибутов, характеризующих сотрудника от табельного номера сотрудника: Н_СОТР ФАМ, Н_ОТД, ТЕЛ Зависимость номера телефона от номера отдела: Н_ОТД ТЕЛ Н_СОТР ФАМ Н_ОТД ТЕЛ 1 Иванов 1 25-45-45 2 Сидоров 1 25-45-45 3 Петров 2 25-54-54 Отношение ПРОЕКТЫ (Н_ПРО , ПРОЕКТ ): Функциональные зависимости: Н_ПРО ПРОЕКТ Н_ПРО ПРОЕКТ 1 СУЭД 2 Разработка ИС «Архив» Отношение ЗАДАНИЯ (Н_СОТР , Н_ПРО , Н_ЗАДАН ): Функциональные зависимости: {Н_СОТР , Н_ПРО } Н_ЗАДАН Н_СОТР Н_ПРО Н_ЗАДАН 1 1 1 2 1 2 3 1 3 1 2 1 2 2 2 Отношения, полученные в результате декомпозиции, находятся в 2НФ. Действительно, отношения СОТРУДНИКИ_ОТДЕЛЫ и ПРОЕКТЫ имеют простые ключи, следовательно автоматически находятся в 2НФ, отношение ЗАДАНИЯ имеет сложный ключ, но единственный неключевой атрибут Н_ЗАДАН функционально зависит от всего ключа {Н_СОТР , Н_ПРО } . Часть аномалий обновления устранена. Так, данные о сотрудниках и проектах теперь хранятся в различных отношениях, поэтому при появлении сотрудников, не участвующих ни в одном проекте просто добавляются кортежи в отношение СОТРУДНИКИ_ОТДЕЛЫ . Точно также, при появлении проекта, над которым не работает ни один сотрудник, просто вставляется кортеж в отношение ПРОЕКТЫ . Фамилии сотрудников и наименования проектов теперь хранятся без избыточности. Если сотрудник сменит фамилию или проект сменит наименование, то такое обновление будет произведено единожды. Тем не менее, часть аномалий разрешить не удалось. 1. В отношение СОТРУДНИКИ_ОТДЕЛЫ нельзя вставить кортеж (4, Пушников П.П., 1, 33-22-11), т.к. при этом получится, что два сотрудника из 1-го отдела (Иванов и Пушников) имеют разные номера телефонов, а это противоречит модели предметной области. В этой ситуации можно предложить два решения, в зависимости от того, что реально произошло в предметной области. Другой номер телефона может быть введен по двум причинам - по ошибке человека, вводящего данные о новом сотруднике, или потому что номер в отделе действительно изменился. Причина аномалии - избыточность данных, порожденная тем, что в одном отношении хранится разнородная информация (о сотрудниках и об отделах). Вывод - увеличивается сложность разработки базы данных. База данных, основанная на такой модели, будет работать правильно только при наличии дополнительного программного кода в виде триггеров. 2. Одни и те же номера телефонов повторяются во многих кортежах отношения. Поэтому если в отделе меняется номер телефона, то такие изменения необходимо одновременно выполнить во всех местах, где этот номер телефона встречаются, иначе отношение станет некорректным. Таким образом, обновление базы данных одним действием реализовать невозможно. Необходимо написать триггер, который при обновлении одной записи корректно исправляет номера телефонов в других местах. Причина аномалии - избыточность данных, также порожденная тем, что в одном отношении хранится разнородная информация. Вывод - увеличивается сложность разработки базы данных. База данных, основанная на такой модели, будет работать правильно только при наличии дополнительного программного кода в виде триггеров. 3. При удалении некоторых данных по-прежнему может произойти потеря другой информации. Например, если удалить сотрудника Петрова П.П., то будет потеряна информация о том, что в отделе номер 2 находится телефон 25-54-54. Причина аномалии - хранение в одном отношении разнородной информации (и о сотрудниках, и об отделах). Вывод - логическая модель данных неадекватна модели предметной области. База данных, основанная на такой модели, будет работать неправильно. Заметим, что при переходе ко второй нормальной форме отношения стали почти адекватными предметной области. 3НФ (Третья Нормальная Форма) Атрибуты называются взаимно независимыми , если ни один из них не является функционально зависимым от другого. Отношение находится в третьей нормальной форме (3НФ ) тогда и только тогда, когда отношение находится в 2НФ и все неключевые атрибуты взаимно независимы . Отношение СОТРУДНИКИ_ОТДЕЛЫ не находится в 3НФ, т.к. имеется функциональная зависимость неключевых атрибутов (зависимость номера телефона от номера отдела): Для того, чтобы устранить зависимость неключевых атрибутов, нужно вновь произвести декомпозицию отношения на несколько отношений. При этом те неключевые атрибуты, которые являются зависимыми, выносятся в отдельное отношение. Отношение СОТРУДНИКИ_ОТДЕЛЫ декомпозируем на два отношения - СОТРУДНИКИ , ОТДЕЛЫ . Отношение СОТРУДНИКИ (Н_СОТР , ФИО , Н_ОТД ): Функциональные зависимости: Зависимость атрибутов, характеризующих сотрудника от табельного номера сотрудника: Н_СОТР ФАМ, Н_ОТД, ТЕЛ Н_СОТР ФАМ Н_ОТД 1 Иванов 1 2 Сидоров 1 3 Петров 2 Отношение ОТДЕЛЫ (Н_ОТД , ТЕЛ ): Функциональные зависимости: зависимость номера телефона от номера отдела. Н_ОТД ТЕЛ 1 25-45-45 2 25-54-54 Обратим внимание на то, что атрибут Н_ОТД , не являвшийся ключевым в отношении СОТРУДНИКИ_ОТДЕЛЫ , становится ключом в отношении ОТДЕЛЫ . Именно за счет этого устраняется избыточность, связанная с многократным хранением одних и тех же номеров телефонов. Вывод . Таким образом, все обнаруженные аномалии обновления устранены. Реляционная модель, состоящая из четырех отношений СОТРУДНИКИ , ОТДЕЛЫ , ПРОЕКТЫ , ЗАДАНИЯ , находящихся в третьей нормальной форме, является адекватной описанной модели предметной области. Алгоритм нормализации (приведение к 3НФ) Итак, алгоритм нормализации (т.е. алгоритм приведения отношений к 3НФ) описывается следующим образом. Шаг 1 (Приведение к 1НФ) . На первом шаге задается одно или несколько отношений, отображающих понятия предметной области. По модели предметной области выписываются обнаруженные функциональные зависимости. Все отношения автоматически находятся в 1НФ. Шаг 2 (Приведение к 2НФ) . Если в некоторых отношениях обнаружена зависимость атрибутов от части сложного ключа, то проводим декомпозицию этих отношений на несколько отношений следующим образом: те атрибуты, которые зависят от части сложного ключа выносятся в отдельное отношение вместе с этой частью ключа. В исходном отношении остаются все ключевые атрибуты: Шаг 3 (Приведение к 3НФ) . Если в некоторых отношениях обнаружена зависимость некоторых неключевых атрибутов других неключевых атрибутов, то проводим декомпозицию этих отношений следующим образом: те неключевые атрибуты, которые зависят других неключевых атрибутов выносятся в отдельное отношение. В новом отношении ключом становится детерминант функциональной зависимости: Замечание . На практике, при создании логической модели данных, как правило, не следуют прямо приведенному алгоритму нормализации. Опытные разработчики обычно сразу строят отношения в 3НФ. Кроме того, основным средством разработки логических моделей данных являются различные варианты ER-диаграмм. Особенность этих диаграмм в том, что они сразу позволяют создавать отношения в 3НФ. Тем не менее, приведенный алгоритм важен по двум причинам. Во-первых , этот алгоритм показывает, какие проблемы возникают при разработке слабо нормализованных отношений. Во-вторых , как правило, модель предметной области никогда не бывает правильно разработана с первого шага. Эксперты предметной области могут забыть о чем-либо упомянуть, разработчик может неправильно понять эксперта, во время разработки могут измениться правила, принятые в предметной области, и т.д. Все это может привести к появлению новых зависимостей, которые отсутствовали в первоначальной модели предметной области. Тут как раз и необходимо использовать алгоритм нормализации хотя бы для того, чтобы убедиться, что отношения остались в 3НФ и логическая модель не ухудшилась. В большинстве случаев 3НФ достаточно, чтобы разрабатывать вполне работоспособные базы данных. Однако существуют нормальные формы более высоких порядков, а именно, нормальная форма Бойса-Кодда (НФБК), четвертая нормальная форма (4НФ), пятая нормальная форма (5НФ). НФБК (Нормальная Форма Бойса-Кодда) При приведении отношений при помощи алгоритма нормализации к отношениям в 3НФ неявно предполагалось, что все отношения содержат один потенциальный ключ. Это не всегда верно. Рассмотрим следующий пример отношения, содержащего два ключа. Пример 1 . Пусть требуется хранить данные о поставках товаров некоторыми поставщиками. Предположим, что наименования поставщиков являются уникальными. Кроме того, каждый поставщик имеет свой уникальный номер. Данные о поставках можно хранить в следующем отношении: Номер поставщика 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 } . Видно, что данные хранятся в отношении с избыточностью - при изменении наименования поставщика, это наименование нужно изменить во всех кортежах, где оно встречается. Можно ли эту аномалию устранить при помощи алгоритма нормализации, описанного в предыдущей главе? Для этого нужно выявить имеющиеся функциональные зависимости: – наименование поставщика зависит от номера поставщика. - номер поставщика зависит от наименования поставщика. - поставляемое количество зависит от первого ключа отношения. - наименование поставщика зависит от первого ключа отношения. - поставляемое количество зависит от второго ключа отношения. - номер поставщика зависит от второго ключа отношения. Данное отношение не содержит неключевых атрибутов, зависящих от части сложного ключа. Действительно, от части сложного ключа зависят атрибуты PNAME и PNUM , но они сами являются ключевыми. Таким образом, отношение находится в 2НФ. Кроме того, отношение не содержит зависимых друг от друга неключевых атрибутов, т.к. неключевой атрибут всего один - VOLUME . Таким образом, показано, что отношение "Поставки" находится в 3НФ. Таким образом, описанный ранее алгоритм нормализации неприменим к данному отношению. Очевидно, однако, что аномалия данного отношения устраняется путем декомпозиции его на два следующих отношения: Таблица 2 - Отношение "Поставщики" Номер поставщика PNUM Наименование поставщика PNAME 1 Фирма 1 2 Фирма 2 3 Фирма 3 Таблица 3 - Отношение "Поставки-2" Номер поставщика PNUM Номер детали DNUM Поставляемое количество VOLUME 1 1 100 1 2 200 1 3 300 2 1 150 2 2 250 3 1 1000 Определение 1 . Отношение находится в нормальной форме Бойса-Кодда (НФБК ) тогда и только тогда, когда детерминанты всех функциональных зависимостей являются потенциальными ключами . Замечание . Если отношение находится в НФБК, то оно автоматически находится и в 3НФ. Действительно, это сразу следует из определения 3НФ. Отношение "Поставки" не находится в НФБК, т.к. имеются зависимости (PNUM PNAME и PNAME PNUM ), детерминанты которых не являются потенциальными ключами. Для того чтобы устранить зависимость от детерминантов, не являющихся потенциальными ключами, необходимо провести декомпозицию, вынося эти детерминанты и зависимые от них части в отдельное отношение. Отношения "Поставщики" и "Поставки-2", полученные в результате декомпозиции находятся в НФБК. Замечание . Приведенная декомпозиция отношения "Поставки" на отношения "Поставщики" и "Поставки-2" не является единственно возможной. Альтернативной декомпозицией является декомпозиция на следующие отношения: Таблица 4 - Отношение "Поставщики" Номер поставщика PNUM Наименование поставщика PNAME 1 Фирма 1 2 Фирма 2 3 Фирма 3 На первый взгляд, такая декомпозиция хуже, чем первая. Действительно, наименования поставщиков по-прежнему повторяются, и при изменении наименования поставщика, это наименование придется менять одновременно в нескольких местах (тем более сразу в двух отношениях!). Кажется, что ситуация стала еще хуже, чем была до декомпозиции. Однако такое ощущение возникает от того, что мы интуитивно считаем, что наименования поставщиков могут меняться, а номера - нет. Если же предположить, что номера поставщиков тоже могут меняться (почему бы нет - директор приказал перенумеровать поставщиков!), то первая декомпозиция получается такой же "плохой" как и вторая - повторяющиеся номера придется менять одновременно в нескольких местах и также сразу в двух отношениях. На самом деле никакого противоречия тут нет. В отношении "Поставки-3" атрибут "Наименование поставщика" (PNAME) является внешним ключом , служащим для связи с отношением "Поставщики". Поэтому, при изменении наименования поставщика, это изменение производится в отношении "Поставщики" и каскадно (см. стратегии поддержания ссылочной целостности в гл. 3) распространяется на отношение "Поставки-3" совершенно так, как изменение номера поставщика каскадно распространяется на отношение "Поставки-2". Поэтому, формально обе декомпозиции совершенно равноправны. В реальной работе разработчик выберет, конечно, первую декомпозицию, но тут важно подчеркнуть, что его выбор основан совсем на других соображениях, не имеющих отношения к формальной теории нормальных форм. Замечание . Отношение "Поставки-2", полученное в результате декомпозиции имеет всего один потенциальный ключ . Поэтому, для анализа отношения "Поставки-2" не требуется привлекать определение НФБК, достаточно определения 3НФ. Хотя отношение "Поставщики" имеет два потенциальных ключа, но, т.к. других атрибутов в нем нет, оно уже так просто устроено, что упростить его дальше нельзя. Возникает вопрос, имеются ли нетривиальные примеры отношений в НФБК, не находящиеся в 3НФ и не такие простые, как отношение "Поставщики"? Пример 2 . Предположим, что нам по-прежнему необходимо учитывать поставки, но каждый акт поставки должен иметь некоторый уникальный номер (назовем его "сквозной номер поставки"). Отношение может иметь следующий вид: Таблица 6 - Отношение "Поставки-с-номером" Номер поставщика PNUM Номер детали DNUM Поставляемое количество VOLUME Сквозной номер поставки NN 1 1 100 1 1 2 200 2 1 3 300 3 2 1 150 4 2 2 250 5 3 1 1000 6 Одним потенциальным ключом данного отношения является, как и раньше, пара атрибутов {PNUM , DNUM } . Другим ключом, в силу уникальности сквозного номера, является атрибут NN . В данном отношении имеются следующие функциональные зависимости: Зависимость атрибутов от первого ключа отношения: {PNUM , DNUM } VOLUME , {PNUM , DNUM } NN , Зависимость атрибутов от второго ключа отношения: NN PNUM , NN DNUM , NN VOLUME , Зависимости, являющиеся следствием зависимостей от ключей отношения: { PNUM , DNUM } {VOLUME , NN } , NN { PNUM , DNUM } , NN {PNUM , VOLUME} , NN {DNUM , VOLUME} , NN { PNUM , DNUM , VOLUME } . Как можно заметить, детерминанты всех зависимостей являются потенциальными ключами, поэтому данное отношение находится в НФБК. Особенностью данного отношения является то, что оно имеет два совершенно независимых потенциальных ключа. 4НФ (Четвертая Нормальная Форма) Рассмотрим следующий пример. Пусть требуется учитывать данные об абитуриентах, поступающих в ВУЗ. При анализе предметной области были выделены следующие требования: · Каждый абитуриент имеет право сдавать экзамены на несколько факультетов одновременно. · Каждый факультет имеет свой список сдаваемых предметов. · Один и тот же предмет может сдаваться на нескольких факультетах. · Абитуриент обязан сдавать все предметы, указанные для факультета, на который он поступает, несмотря на то, что он, может быть, уже сдавал такие же предметы на другом факультете. Предположим, что нам требуется хранить данные о том, какие предметы должен сдавать каждый абитуриент. Попытаемся хранить данные в одном отношении "Абитуриенты-Факультеты-Предметы": Таблица 7 - Отношение "Абитуриенты-Факультеты-Предметы" Абитуриент Факультет Предмет Иванов Математический Математика Иванов Математический Информатика Иванов Физический Математика Иванов Физический Физика Петров Математический Математика Петров Математический Информатика В данный момент в отношении хранится информация о том, что абитуриент Иванов поступает на два факультета (математически и физический), а абитуриент Петров - только на математический. Кроме того, можно сделать вывод, что на математическом факультете нужно сдавать математику и информатику, а на физическом - математику и физику. Кажется, что в отношении имеется аномалия обновления, связанная с тем, что дублируются фамилии абитуриентов, наименования факультетов и наименования предметов. Однако эта аномалия легко устраняется стандартным способом - вынесением всех наименований в отдельные отношения, оставляя в исходном отношении только соответствующие номера: Таблица 8 - Модифицированное отношение "Абитуриенты-Факультеты-Предметы" Номер Абитуриента Номер Факультета Номер Предмета 1 1 1 1 1 2 1 2 1 1 2 3 2 1 1 2 1 2 Теперь каждое наименование встречается только в одном месте. И все-таки как в исходном, так и в модифицированном отношении имеются аномалии обновления, возникающие при попытке вставить или удалить кортежи. Аномалия вставки . При попытке добавить в отношение "Абитуриенты-Факультеты-Предметы" новый кортеж, например (Сидоров, Математический, Математика), мы обязаны добавить также и кортеж (Сидоров, Математический, Информатика), т.к. все абитуриенты математического факультета обязаны иметь один и тот же список сдаваемых предметов. Соответственно, при попытке вставить в модифицированное отношении кортеж (3, 1, 1), мы обязаны вставить в него также и кортеж (3, 1, 2). Аномалия удаления. При попытке удалить кортеж (Иванов, Математический, Математика), мы обязаны удалить также и кортеж (Иванов, Математический, Информатика) по той же самой причине. Таким образом, вставка и удаление кортежей не может быть выполнена независимо от других кортежей отношения. Кроме того, если мы удалим кортеж (Иванов, Физический, Математика), а вместе с ним и кортеж (Иванов, Физический, Физика), то будет потеряна информация о предметах, которые должны сдаваться на физическом факультете. Декомпозиция отношения "Абитуриенты-Факультеты-Предметы" для устранения указанных аномалий не может быть выполнена на основе функциональных зависимостей, т.к. это отношение не содержит никаких функциональных зависимостей . Это отношение является полностью ключевым, т.е. ключом отношения является все множество атрибутов. Но ясно, что какая-то взаимосвязь между атрибутами имеется. Эта взаимосвязь описывается понятием многозначной зависимости . Определение 2 . Пусть - отношение, и , , - некоторые из его атрибутов (или непересекающиеся множества атрибутов). Тогда атрибуты (множества атрибутов) и многозначно зависят от (обозначается ), тогда и только тогда, когда из того, что в отношении содержатся кортежи и следует, что в отношении содержится также и кортеж к. Замечание . Меняя местами кортежи и в определении многозначной зависимости, получим, что в отношении должен содержаться также и кортеж . Таким образом, атрибуты и , многозначно зависящие от , ведут себя "симметрично" по отношению к атрибуту . В отношении "Абитуриенты-Факультеты-Предметы" имеется многозначная зависимость Факультет Абитуриент|Предмет. Словами это можно выразить так - для каждого факультета (для каждого значения из ) каждый поступающий на него абитуриент (значение из ) сдает один и тот же список предметов (набор значений из ), и для каждого факультета (для каждого значения из ) каждый сдаваемый на факультете экзамен (значение из ) сдается одним и тем же списком абитуриентов (набор значений из ). Именно наличие этой зависимости не позволяет независимо вставлять и удалять кортежи. Кортежи обязаны вставляться и удаляться одновременно целыми наборами . Замечание . Если в отношении имеется не менее трех атрибутов , , и есть функциональная зависимость , то есть и многозначная зависимость . Действительно, действуя формально в соответствии с определением многозначной зависимости, предположим, что в отношении содержатся кортежи и . В силу функциональной зависимости отсюда следует, что . Но тогда кортеж в точности совпадает с кортежем и, следовательно, содержится в отношении . Таким образом, имеется многозначная зависимость . Таким образом, понятие многозначной зависимости является обобщением понятия функциональной зависимости . Определение 3 . Многозначная зависимость называется нетривиальной многозначной зависимостью , если не существует функциональных зависимостей и . В отношении "Абитуриенты-Факультеты-Предметы" имеется именно нетривиальная многозначная зависимость Факультет Абитуриент|Предмет. В силу нетривиальности этой зависимости мы не можем воспользоваться теоремой Хеза для декомпозиции отношения. Однако Фейджином Р. [52] доказана следующая теорема: Теорема (Фейджина) . Пусть , , - непересекающиеся множества атрибутов отношения. Декомпозиция отношения на проекции и будет декомпозицией без потерь тогда и только тогда, когда имеется многозначная зависимость . Замечание . Если зависимость является тривиальной, т.е. существует одна из функциональных зависимостей или , то получаем теорему Хеза. Доказательство теоремы . Необходимость . Пусть декомпозиция отношения на проекции и является декомпозицией без потерь. Докажем что . Предположим, что отношение содержит кортежи и . Необходимо доказать, что кортеж также содержится в . По определению проекций, кортеж содержится в , а кортеж содержится в . Тогда кортеж содержится в естественном соединении , а в силу того, что декомпозиция является декомпозицией без потерь, этот кортеж содержится и в . Необходимость доказана . Достаточность . Пусть имеется многозначная зависимость . Докажем, что декомпозиция отношения на проекции и является декомпозицией без потерь. Как и в доказательстве теоремы Хеза, нужно доказать, что для любого состояния отношения . Включение доказывается как в теореме Хеза. Такое включение выполняется всегда для любой декомпозиции отношения . Докажем включение . Пусть кортеж . Это означает, что в проекции содержится кортеж , а в проекции содержится кортеж . По определению проекции, найдется такое значение атрибута , что отношение содержит кортеж . Аналогично, найдется такое значение атрибута , что отношение содержит кортеж . Тогда по определению многозначной зависимости кортеж . Включение доказано. Достаточность доказана . Теорема доказана . Определение 4 . Отношение находится в четвертой нормальной форме (4НФ ) тогда и только тогда, когда отношение находится в НФБК и не содержит нетривиальных многозначных зависимостей . Отношение "Абитуриенты-Факультеты-Предметы" находится в НФБК, но не в 4НФ. Согласно теореме Фейджина, это отношение можно без потерь декомпозировать на отношения: Таблица 12 - Отношение "Факультеты-Абитуриенты" Факультет Абитуриент Математический Иванов Физический Иванов Математический Петров В полученных отношениях устранены аномалии вставки и удаления, характерные для отношения "Абитуриенты-Факультеты-Предметы". Заметим, что полученные отношения остались полностью ключевыми, и в них по-прежнему нет функциональных зависимостей. Отношения с нетривиальными многозначными зависимостями возникают, как правило, в результате естественного соединения двух отношений по общему полю, которое не является ключевым ни в одном из отношений . Фактически это приводит к попытке хранить в одном отношении информацию о двух независимых сущностях. В качестве еще одного примера можно привести ситуацию, когда сотрудник может иметь много работ и много детей. Хранение информации о работах и детях в одном отношении приводит к возникновению нетривиальной многозначной зависимости Работник Работа|Дети. 5НФ (Пятая Нормальная Форма) Функциональные и многозначные зависимости позволяют произвести декомпозицию исходного отношения без потерь на две проекции. Можно, однако, привести примеры отношений, которые нельзя декомпозировать без потерь ни на какие две проекции. Теорема Фейджина (другая формулировка) . Отношение удовлетворяет зависимости соединения тогда и только тогда, когда имеется многозначная зависимость . Т.к. теорема Фейджина является взаимно обратной, то ее можно взять в качестве определения многозначной зависимости. Таким образом, многозначная зависимость является частным случаем зависимости соединения, т.е., если в отношении имеется многозначная зависимость, то имеется и зависимость соединения. Обратное, конечно, неверно. Определение 6 . Зависимость соединения называется нетривиальной зависимостью соединения , если выполняется два условия: · Одно из множеств атрибутов не содержит потенциального ключа отношения . · Ни одно из множеств атрибутов не совпадает со всем множеством атрибутов отношения . Для удобства работы сформулируем это определение так же и в отрицательной форме: Определение 7 . Зависимость соединения называется тривиальной зависимостью соединения , если выполняется одно из условий: · Либо все множества атрибутов содержат потенциальный ключ отношения . · Либо одно из множеств атрибутов совпадает со всем множеством атрибутов отношения . Определение 8 . Отношение находится в пятой нормальной форме (5НФ ) тогда и только тогда, когда любая имеющаяся зависимость соединения является тривиальной . Определения 5НФ может стать более понятным, если сформулировать его в отрицательной форме: Определение 9 . Отношение не находится в 5НФ , если в отношении найдется нетривиальная зависимость соединения . Возвращаясь к примеру 3, становится понятно, что не зная ничего о том, какие потенциальные ключи имеются в отношении и как взаимосвязаны атрибуты, нельзя делать выводы о том, находится ли данное отношение в 5НФ (как, впрочем, и в других нормальных формах). По данному конкретному примеру можно только предположить, что отношение в примере 3 не находится в 5НФ. Предположим, что анализ предметной области позволил выявить следующие зависимости атрибутов в отношении : (i) Отношение