Файл: информатика.doc

2.3. Иерархическая модель данных (имд)

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

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

• имеется единственная особая вершина, называемая корнем, в которую не заходит ни одно ребро;

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

• граф не содержит циклов.

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

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

Элементы отношения называют кортежами. Элементы кортежа принято называть атрибутами. Количество атрибутов кортежа определяет арность отношения. Отношения арности I называют унарными, арности 2 - бинарными, арности п - п-арными.

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

Объектно-реляционные модели

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

Объектно-ориентированные модели данных

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

12. Нормализация отношений. Нормальные формы. Запросы и операторы манипулирования данными. Язык запросов sql.

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

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

Первая нормальная форма (1НФ).

Отношение приведено к 1НФ, если все его атрибуты простые.

Введём понятие функциональной зависимости. Пусть X и У - атрибуты (группы атрибутов) некоторого отношения. Говорят, что У функционально зависит от X, если в любой момент времени каждому значению Х=х соответствует единственное значение У=у (X— >У). (При этом любому значению У=у может соответствовать несколько значений Х=(х], х^,...)).

Атрибут X в функциональной зависимости X— »У называется детерминантом отношения.

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

Вторая нормальная форма (2НФ).

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

Для того чтобы привести отношение ко 2НФ. нужно:

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

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

Рассмотрим понятие транзитивной зависимости. Пусть X, V, 2 - атрибуты некоторого отношения. При этом Х-> V и V-» 2, но обратное соответствие отсутствует, т.е. 2 не зависит от У или V не зависит от X. Тогда говорят, что 2 транзитивно зависит от X (X—»—» 2).

Третья нормальная форма (ЗНФ).

Отношение находится в ЗНФ, если оно находится во 2НФ и в нем отсутствуют нетранзитивные зависимости.

Введём понятие многозначной зависимости. Многозначная зависимость существует, если заданным значениям атрибута X соответствует множество, состоящее из нуля (или более) значений атрибута V (Х-»У). Если в отношении присутствуют многозначные зависимости, то схема отношения должна находиться в 4НФ.

Различают тривиальные и нетривиальные многозначные зависимости. Тривиальной называется такая многозначная зависимость Х-»У, для которой V I X или X У V = К, где К - рассматриваемое отношение. Тривиальная многозначная зависимость не нарушает 4НФ. Если хотя бы одно из двух этих условий не выполняется (т.е. V не является подмножеством X или X II V состоит не из всех атрибутов К.), то такая многозначная зависимость называется нетривиальной.

Четвертая нормальная форма (4НФ).

Отношение находится в 4НФ, если оно находится в ЗНФ и в нем отсутствуют нетривиальные многозначные зависимости.

Запросы и операторы манипулирования данными

Как известно, двумя фундаментальными языками запросов к реляционным БД являются языки реляционной алгебры и реляционного исчисления. При всей своей строгости и теоретической обоснованности эти языки редко используются в современных реляционных СУБД в качестве средств пользовательского интерфейса. Запросы на этих языках трудно формулировать и понимать. SQL представляет собой некоторую комбинацию реляционного исчисления кортежей и реляционной алгебры, причем до сих пор нет общего согласия, к какому из классических языков он ближе. При этом возможности SQL шире, чем у этих базовых реляционных языков, в частности, в общем случае невозможна трансляция запроса, сформулированного на SQL, в выражение реляционной алгебры, требуется некоторое ее расширение. Существенными свойствами подъязыка запросов SQL являются возможность простого формулирования запросов с соединениями нескольких отношений и использование вложенных подзапросов в предикатах выборки. Вообще говоря, одновременное наличие обоих средств избыточно, но это дает пользователю при формулировании запроса возможность выбора более понятного ему варианта. В предикатах со вложенными подзапросами в SQL System R можно употреблять теретико-множественные операторы сравнения, что позволяет формулировать квантифицированные запросы (эти возможности обычно труднее всего понимаются пользователями и поэтому в дальнейшем в SQL появились явно квантифицируемые предикаты). Существенной особенностью SQL является возможность указания в запросе потребности группирования отношения-результата по указанным полям с поддержкой условий выборки на всю группу целиком. Такие условия выборки могут содержать агрегатные функции, вычисляемые на группе. Эта возможность SQL главным образом отличает этот язык от языков реляционной алгебры и реляционного исчисления, не содержащих аналогичных средств. Еще одним отличием SQL является необязательное удаление кортежей-дубликатов в окончательном или промежуточных отношениях-результатах. Строго говоря, результатом оператора выборки в языке SQL является не отношение, а мультимножество кортежей. В тех случаях, когда семантика запроса требует наличия отношения, уничтожение дубликатов производится неявно. Самый общий вид запроса на языке SQL представляет теоретико-множественное алгебраическое выражение, составленное из элементарных запросов. В SQL System R допускались все базовые теретико-множественные операции (UNION, INTERSECT и MINUS). Работа с неопределенными значениями в SQL System R до конца продумана не была, хотя неявно предполагалось использование трехзначной логики при вычислении логических выражений. Операторы манипулирования данными UPDATE и DELETE построены на тех же принципах, что и оператор выборки данных SELECT. Набор кортежей указанного отношения, подлежащих модификации или удалению, определяется входящим в соответствующий оператор логическим выражением, которое может включать сложные предикаты, в том числе и с вложенными подзапросами. В операторе вставки кортежа(ей) в указанное отношение заносимый кортеж может задаваться как в литеральной форме, так и с помощью внутреннего подоператора выборки.

Запросы SQL

Язык допускает три типа синтаксических конструкций, начинающихся с ключевого слова SELECT: спецификация курсора (cursor specification), оператор выборки (select statement) и подзапрос (subquery). Основой всех них является синтаксическая конструкция "табличное выражение (table expression)". Семантика табличного выражения состоит в том, что на основе последовательного применения разделов from, where, group by и having из заданных в разделе from таблиц строится некоторая новая результирующая таблица, порядок следования строк которой не определен и среди строк которой могут находиться дубликаты (т.е. в общем случае таблица-результат табличного выражения является мультимножеством строк). На самом деле именно структура табличного выражения наибольшим образом характеризует структуру запросов языка SQL/89. Мы рассмотрим ниже структуру и смысл разделов табличного выражения ниже, но до этого немного подробнее обсудим три упомянутые конструкции, включающие табличные выражения. В спецификации запроса задается список выборки (список арифметических выражений над значениями столбцов результата табличного выражения и констант). В результате применения списка выборки к результату табличного выражения производится построение новой таблицы, содержащей то же число строк, но вообще говоря другое число столбцов, содержащих результаты вычисления соответствующих арифметических выражений из списка выборки. Кроме того, в спецификации запроса могут содержаться ключевые слова ALL или DISTINCT. При наличии ключевого слова DISTINCT из таблицы, полученной применением списка выборки к результату табличного выражения, удаляются строки-дубликаты; при указании ALL (или просто при отсутствии DISTINCT) удаление строк-дубликатов не производится.