Понятие базы данных

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

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

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

     Тип связи определяется для двух типов  записи: предка и потомка. Экземпляр  типа связи состоит из одного экземпляра типа записи предка и упорядоченного набора экземпляров типа записи потомка. Для данного типа связи L с типом записи предка P и типом записи потомка C должны выполняться следующие два условия:

• каждый экземпляр типа записи P является предком только в одном экземпляре типа связи L;
• каждый экземпляр типа записи C является потомком не более чем в одном экземпляре типа связи L.

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

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

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

     3 Отношения на множествах 

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

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

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

     Множества обычно обозначаются заглавными латинскими буквами. Если элемент принадлежит множеству , то это обозначается:

      - Если каждый элемент множества  является также и элементом  множества , то говорят, что  множество является подмножеством множества :

     - Подмножество множества называется  собственным подмножеством, если

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

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

     Объединением  двух множеств называется новое множество

     Пересечением двух множеств называется новое множество

     Разностью (дополнением) двух множеств называется новое множество

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

     Пусть и - множества. Выражение вида , где и , называется упорядоченной парой. Равенство вида означает, что и . В общем случае, можно рассматривать упорядоченную n-ку из элементов . Упорядоченные n-ки иначе называют наборы или кортежи.

     Декартовым (прямым) произведением множеств называется множество упорядоченных n-ок (наборов, кортежей) вида

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

     Подмножество  декартового произведения множеств называется отношением степени n (n-арным отношением). Мощность множества кортежей, входящих в отношение , называют мощностью отношения .

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

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

     Во-первых, все элементы отношения есть однотипные кортежи. Однотипность кортежей позволяет считать их аналогами строк в простой таблице, т.е. в такой таблице, в которой все строки состоят из одинакового числа ячеек и в соответствующих ячейках содержатся одинаковые типы данных. Например, отношение, состоящее из трех следующих кортежей {(1, "Иванов", 1000), (2, "Петров", 2000), (3, "Сидоров", 3000)} можно считать таблицей, содержащей данные о сотрудниках и их зарплатах. Такая таблица будет иметь три строки и три колонки, причем в каждой колонке содержатся данные одного типа.

     В противоположность этому рассмотрим множество {(1), (1, 2), (1, 2, 3)}, состоящее из разнотипных числовых кортежей. Это множество не является отношением ни в , ни в , ни в . Из кортежей, входящих в это множество нельзя составить простую таблицу. Правда, можно считать это множество отношением степени 1 на множестве всех возможных числовых кортежей всех возможных степеней, но такая трактовка ничего нового, по сравнению с понятием подмножества, не дает.

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

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

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

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

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

     Обычно  отношение эквивалентности обозначают знаком или и говорят, что оно (отношение) задано на множестве (а не на ). Условия 1-3 в таких обозначениях выглядят более естественно: для  всех (рефлексивность); если, то (симметричность); если и, то (транзитивность).

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

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

     Обычно  отношение порядка обозначают знаком. Если для двух элементов и выполняется, то говорят, что "предшествует" . Как и для отношения эквивалентности, условия 1-3 в таких обозначениях выглядят более естественно: для всех (рефлексивность); если и , то (антисимметричность); если и , то (транзитивность).

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

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

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

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

     Введем  понятие транзитивного замыкания, связанное с бинарными отношениями,

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

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

     4 Реляционные и объектно-ориентированные базы данных  

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

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

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