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

МОДЕЛИ ДАННЫХ

КЛАССИФИКАЦИЯ И ОСНОВНЫЕ СВОЙСТВА ЕДИНИЦ ИНФОРМАЦИИ

Существуют две основные единицы информации - атрибут и составная единица информации. Определение атрибута было дано в п. 1.2. Атрибут соответствует понятию переменной в языках программирования и понятию реквизита в бухгалтерском учете. Атрибут характеризуется именем и значением. Именем атрибута называется его условное обозначение в процессах обработки данных. Значением атрибута называется величина, характеризующая некоторое свойство объекта, явления, процесса в конкретных обстоятельствах. Все допустимые значениями атрибута образуют множество, называемое доменом этого атрибута. Формально атрибут с именем Х представляет собой пару (X, z), где z – элемент Z. Множество Z называется доменом значений (областью определения атрибута Х), величина z является значением атрибута Х в заданный момент времени. Определение домена предполагает указание его имени и списка значений. Если число значений в домене невелико, то их список можно указать при объявлении данных в программе. Например, в языке программирования Паскаль это выглядит как

type day = 1..31; month = (январь, февраль, март, апрель, май, июнь, июль, август, сентябрь, октябрь, ноябрь, декабрь); Year = 1900..1999; {в описании типа атрибутов перечисляются допустимые значения атрибутов День, Месяц и Год соответственно}

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

Пример Домен фамилий - FAM. Перечислить фамилии невозможно, поэтому ограничим FАМ значениями текстового типа длиной до 20 символов. Для языка Паскаль получим var FАМ: string(20];

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

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

1. Объекты для технологии баз данных - отношения и веерные отношения

2. Объекты для технологии искусственного интеллекта - предикаты, фреймы и семантические сети.

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

• информационной конструкцией - отношением с двухуровневой структурой,

• Допустимыми операциями - проекцией, выборкой, соединением и некоторыми другими,

• Ограничениями – функциональными зависимостями между атрибутами отношения. Каждому классу объектов Р материального мира ставится в соответствие некоторое множество атрибутов, например Al, A2,...,An. Отдельный объект класса P описывается строкой величин (al, а2..., an), где ai - значение атрибута Ai. ' Строка (а1, а2,..., an) называется кортежем. Всему классу объектов соответствует множество кортежей, называемое отношением. Обозначим отношение, описывающее класс объектов Р, также через Р. Выражение Р(Ai, A2,...,An) называется схемой отношения Р. Для каждого компонента кортежа должна быть указана ее связь с соответствующим атрибутом. В реляционной модели данных для обеспечения этой связи порядок компонентов кортежа совпадает с порядком следования атрибутов в схеме отношения. Каждое отношение представляет состояние, класса объектов в некоторый момент времени. Следовательно, одной схеме отношения в разные моменты времени могут соответствовать разные отношения. Множество значений отношения можно представить в виде таблицы, в которой соблюдаются следующие соответствия:

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

•.строке таблицы соответствует кортеж отношения,

• все строки таблицы (и соответственно все кортежи) различны,

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

D = { Оl, О2, DЗ,..., Dk }

и создадим декартово произведение доменов

U= Dl. D2. DЗ..... Dk.

Каждый элемент U имеет вид (d1, d2, d3,...,dk), где d1 - элемент домена Dl, d2 - элемент D2 и т.д. В множестве U представлены всевозможные сочетания значений доменов, полученные по названному принципу. Среди элементов из U содержатся такие, которые не соответствуют реально имеющимся сообщениям и не могут храниться в БД. Отношение R, включающее истинные сообщения, является подмножеством U. Атрибуты отношения R используют домены из D в качестве своих областей определения. Реляционная база данных представляет собой множество отношении. Схема реляционной БД содержит следующие компоненты S(rel) < A,R,Dom,Rel,V(s)>, где А - множество имен атрибутов, R - множество имен отношении, Dom - вхождение атрибутов в домены, Rel - вхождение атрибутов в отношения, V(s) - множество ограничений (в том числе функциональных зависимостей).

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

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

• описанием свойств, которым должно удовлетворять результирующие отношение (декларативный подход). Приводимые далее операции над отношениями ориентированы на процедурное описание процессов обработки данных. Множество отношений и операций над ними образуют реляционную алгебру. При рассмотрении операций над отношениями будет использоваться как алгебраическая форма записи операций, так, и запись на языке реляционных СУБД семейства dBASE (для определенности - dBASE 3). Далее будут рассмотрены аналогичные конструкции языка SQL. Как правило, список операций содержит проекцию, выборку, объединение, пересечение. вычитание, соединение и деление. Проекцией называется операция, которая переносит в результирующее отношение те столбцы исходного отношения, которые указаны в условии операции. Алгебраическая запись проекции имеет вид: Т = R[X],

где R- Исходное Отношение, Т - результирующее отношение,_ Х - список атрибутов в структуре отношения Т (условие проекции).

Пример Рассмотрим два отношения: Wl, содержащее сведения о продаже продукции в 1998 г., и W2, в котором указаны цены на продукцию и комплектующие изделия для соответствующих видов продукции. Если требуется отношение Х1, содержащее сведения только о фактическом выпуске продукции, то оно получается в результате выполнения проекции. Х1 = W1[Магазин, Продукция, Факт] и имеет вид:

Столбцы результирующего отношения указываться в любом порядке: Х2 = W1[Магазин, Продукция, Факт]. В СУБД DBASE проекции реализуются двумя командами и этот же пример выглядит как

Use W1 && открыть отношение W1 Copy to X1 field Магазин, Продукция, Факт && проекция Знак && означает комментарий. Следующий пример проекции - это получение справочника Х3 цен на продукцию: use W2 сору to Х3 field Продукция. Цена Значения отношения Х3 показаны ниже:

Значительными неудобством в Х3 является наличие одинаковых строк. В реляционной алгебре требуется. чтобы результат проекции не содержал одинаковых строк. однако практически такие СУБД. как dBASE. не обеспечивают этого. Правильным результатом проекции Х4 = W2[Продукция. Цена) является отношение Отношение с заданной структурой зачастую можно получить из различных исходных отношений БД. В этом случае, естественно. не гарантируются одинаковые результаты. Пусть нам необходим список отделов учреждения. В базе данных имеются отношения Служащий (Фамилия, Отдел…) и Технолог (Фамилия, Отдел,...). Проекция Служащий[Отдел] формирует полный список отделов, а Технолог[Отдел] может содержать меньше значений, если в некоторых отделах не работают технологи. Выборкой называется операция, которая переносит в результирующее отношение те строки из исходного отношения, которые удовлетворяют условию выборки. Условие выборки проверяется в каждой строке отношения по отдельности и не может охватывать информацию из нескольких строк. Существуют две простейшие разновидности условия выборки:

1. Условие вида Имя _атрибута <знак сравнения> Значение, где допускаются знаки сравнения =, #, >, =>, <, <=. Например, Цена> 100.

2. Условие вида Имя _атрибута l <знак сравнения> Имя_атрибута_2. Например, Факт > План. Имена атрибутов должны содержаться в структуре исходного отношения. Алгебраическая запись выборки имеет вид: Т= R[p] где R - исходное отношение; ¬ т - результирующее отношение; р - условие выборки.

В качестве примера получим значения Х5.= Wl [Продукция = "Эдв-12"]

в СУБД dBASE выборка реализуется командой сору с опцией for, например, use Wl сору to Х6 for Факт => План

В команде сору условия выборки и проекции могут присутствовать одновременно, но атрибуты условия выборки должны включаться в условие проекции. Операции объединения, пересечения и вычитания, производятся над двумя исходными отношениями с одинаковой структурой. Точных аналогов этих операций в dBASЕ нет. Обозначим исходные отношения через, R1 и R2, а результирующее – Т. Объединение Т =Д(R1, R2) содержит строки присутствующие либо в отношении R1, либо в R2. Пересечение Т = I(R1, R2) содержит строки, присутствующие в отношениях R1 и R2 одновременно. Вычитание Т= M(R 1, R2) содержит те строки из R1, которые отсутствуют в R2. Если справочник цен на продукцию Х4 необходимо дополнить новыми сведениями из отношения W3, то надо выполнить объединение

Х7 = U (Х4, W3). В dBASE предусмотрена операция добавления append, которая для нашего примера реализуется командами use Х4 append [гот W3, что приводит к добавлению в отношение Х4 всех строк из отношения W3. Отличия добавления от объединения – создание результирующего отношения на месте исходного отношения и возможность появления одинаковых строк в результирующем отношении. Операция соединения отношения выполняется над двумя исходными отношениями и создаёт одно результирующие. Каждая строка первого исходного отношения сопоставляется по очереди со всеми строками второго отношения, и если для этой пары строк соблюдается условие соединения, то они сцепляются и образуют очередную строку в результирующем отношении. Условие соединения имеет вид: Имя _атрибута l <знак сравнения> Имя_атрибута_2, где Имя _атрибута l находится в одном исходном отношении, а Имя_атрибута_2 - в другом. Будем использовать следующее обозначение операции соединения:
Т = R1[р]R2, где R1 и R2 - исходные отношения, т - результирующее отношение, р – условие соединения. Практически наиболее важный частный случай соединения называется натуральным соединением и имеет следующие особенности:

• знаком сравнения в условии соединения является "=",

• Имя _атрибута l и Имя_атрибута_2 должны совпадать, а точнее, содержать пересечение списков атрибутов исходных отношений,

• список атрибутов результирующего отношения образуется в результате объединения списков атрибутов исходных отношении. Обозначение натурального соединения не содержит условия соединения и имеет вид Т = R1 * R2. Если требуется сведения о продаже продукции из отношения Wl дополнить данными о ценах на продукцию.из отношения Х7, то задача решается с помощью соединения. Х8 = WI[ Продукция = Продукция ]Х7

Первая строка из WI и первая строка из Х7 удовлетворяют условию Продукция =Продукция, поэтому сцепляются. Остальные строки из Х7 не будут сцепляться с первой строкой из WI (условие не соблюдается). Вторая строка из WI при сравнении со всеми строками из Х7 сцепится только с третьей строкой и т. д. Если применять операцию натурального соединения, то в отношении Х8 бу¬дет отсутствовать второй столбец с именем Продукция. В СУБД DBASE для проведения соединения необходимо использовать две области для исходных отношений: SELECT 1. USE WI && открытие отношения W1 SELECТ 2 USE Х7 && открытие отношения Х7 SELECТ 1 JOIN WIТH Х7 Т0 Х9 P'OR Продукция=Х7- >Продукция FIELDS Магазин, Продукция, Х7- >Цена, План, Факт Опция with называет второе исходное отношение, опция for содержит условие соединения, опция fields перечисляет имена атрибутов результирующего отношения. В приведенном примере выполнено натуральное соединение и передвинут столбец Цена. В ряде случаев соединение дает некорректные результаты, например:

X10 = W1 * W2 содержит неоднократно одинаковые сообщения о.выпуске продукции только потому, что эти виды продукции используют несколько комплектующих изделий. Вообще говоря, ограничения, которые присутствуют в исходных отношениях, определенным образом трансформируются в ограничения для отношений, полученных в результате применения операций реляционной алгебры. Соответствующие закономерности будут рассмотрены в п. 2.2 в связи с анализом ограничений, присущих реляционной модели данных. Натуральное соединение определено и в тех случаях, когда соединяемые отношения совпадают по структуре или не содержат общих атрибутов. Если структура отношений R и S одинакова, то R • S выполняет фактически пересечение I(R,S). Когда отношения R и S не содержат общих атрибутов, считается, что условие соединения выполнено для любой пары сопоставляемых строк отношений, и R * S сцепляет каждую строку из R со всеми строками из S. Операция натурального соединения имеет ряд свойств, например коммутативность и ассоциативность. Свойство коммутативности означает, что операции X1=R * S и X2=S * R

порождают, в сущности, одно и то же отношение, Свойство ассоциативности означает, что операция Y1 =(R *S)*T и операция Y2=R *(s*Т)L дают одинаковый результат. Различия, безусловно, состоят в неодинаковом порядке строк Х1 и Х2 (Y1 и Y2 соответственно. Кроме того, промежуточные отношения при вычислении Y1 и Y2 могут иметь резко различающиеся размеры (число строк), хотя Y1 и Y2 содержат равное число строк. Описание операции деления отношений начнем с примера. Пусть существует отношение Y(ФИО, ЯП), где для каждого программиста с фамилией, ФИО указываются языки программирования ЯП, которые он знает.

Необходимо выделить фамилии программистов, знающих языки Си и Фортран одновременно. Попытка воспользоваться операцией выборки X11 = Y [ ЯП = "Си" AND ЯП= "Фортран"] (через АND обозначена логическая операция "и") будет безуспешной, так как в одной строке отношения нет информации о двух языках программирования сразу и отношение. Х11 будет пустое. Определим операцию, называемую '''образ''. В отношении Т(А,В) образом значения а атрибута А является множество значений атрибута В, и каждый элемент b этого множества образует вместе с а некоторую строку (или часть строки) отношения Т. im В(а) = {b1,b2..., bk}, где im - знак операции "образ", а - значение, образ которого вычисляется, В - имя атрибута для образа значения а, b1,b2..., bk - значения атрибута В.

Стоящая перед нами задача решается путем вычисления образов значений "Си" и "Фортран" и последующего пересечения найденных образов. im ФИО("Си") = {"Иванов''',''Петров'',''Семин''} im ФИО("Фортран") = {"Иванов", "Семин"," Яшин"} iJIl ФИО("Си") im ФИО("Фортран") = "Иванов","Семин" Такая связка операций взятия образа и пересечения полученных множеств (количество значений, для которых вычисляется образ, может быть произвольным, а не 2, как в нашем примере) требуется достаточно часто, поэтому вводится специальная операция - деление. Условимся, что существует отношение - делимое W(A,B) (в нашем примере это Y) и отношение-делитель V(А). для необходимого нам запроса отношение-делитель имеет вид:

Z ЯП Си Фортран

Результатом операции деления является отношение Q(B), содержащее пересечение образов всех строк отношения-делителя У(А), вычисленных на основе отношения - делимого W(A,B), Q = D (W,V), где D - знак операции деления. Результат деления Х12 = D (Y,Z) содержит следующие значения: Х12 ФИО Иванов Семин

Дата добавления: 2014-01-11