Языковые средства для работы с БД

 

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

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

Способы организации ЯОД и ЯМД:

1. Языки задаются как расширение классического языка программирования: а) работа с БД осуществляется посредством вызова процедур на традиционном языке программирования (ЯМД СУБД VISTA); б) классический язык дополняется синтаксически правильными конструкциями для описания и манипулирования данными; необходима разработка расширенного транслятора, понимающего семантику новых операторов(СУБД ADABAS для IBM-360/370); в) внутри текста программы оформляются независимые блоки на специализированном языке (ЯОД СУБД VISTA), программа должна быть предварительно обработана специализированным транслятором, который специализированные блоки преобразует в конструкции классического языка; далее текст обрабатывается традиционным транслятором.

2. Функции ЯОД и ЯМД реализуются средствами СУБД. Имеется встроенный язык, реализующий не только ЯОД и ЯМД, но и классические операции традиционных языков и операторы пользовательского интерфейса (СУБД dBase, FoxPro и т.д.).

3. Разработка независимых ЯОД и ЯМД. Такой подход наиболее полно реализует принцип независимости данных. Требуется стандартизация языков. Пример: SQL.

 

Логическое описание и проектирование БД

 

Элементы данных и связи

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

Ошибки в определении элемента данных:

1) «Цех» – этот элемент данных может содержать в себе другие элементы: начальник цеха, выпускаемая продукция и др., то есть отсутствует семантическая однозначная интерпретация этого элемента (наверно, имелось в виду название цеха или номер цеха).

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

3) «Возраст сотрудника» – этот элемент имеет изменяемое значение (в системе отсутствует событие, приводящее к необходимости изменения этого значения), нужно использовать элемент «Дата рождения», а возраст вычислять в приложении. Элемент данных «Номер курса студента» не является изменяемым, поскольку для изменения его значения в системе должно произойти событие: приказ по деканату.

 

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

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

Типы связей:

1) 1:1 – "один к одному". Одному значению первого объекта соответствует не более одного значения второго объекта (номер студента à номер читательского билета);

2) М:1 – "многие к одному". Множеству значений первого объекта соответствует не более одного значения второго объекта (табельный номер сотрудника à должность сотрудника);

3) 1:М – "один ко многим". Одному значению первого объекта соответствует множество значений второго объекта, где МÎ{0,1,2...} (должность сотрудника ®® табельный номер сотрудника);

4) М:М – "многие ко многим". Множеству значений первого объекта соответствует множество значений второго объекта (должность сотрудника ®® разряд ЕТС сотрудника).

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

 

Правило склейки записей. Если между элементами данных A и B установлена связь типа 1:1 или М:1, то элемент данных B присоединяется к элементу данных A, образуя логическую запись (тип записи). Элемент данных A в этом типе записи будет ключевым.

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

 

Древовидные модели данных

 

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

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

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

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

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

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

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

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

 

Сетевые модели данных

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

Свойство. Если схема данных содержит связь типа М:М, то она является сетевой.

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

Правило преобразования сложной сетевой схемы к простой сетевой. Допустим, что схема данных содержит две схемы отношений (типов записей) со связью М:М. A и B ‑ ключи этих записей. Создается новое отношение с ключом A+B. Со схемы удаляется связь типа М:М, а от нового отношения устанавливается связь М:1 к исходным отношениям.

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

 

Общие данные, данные пересечения, изолированные данные:

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

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

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

 

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

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

1. Запись (строка) таблицы с одинаковым содержанием не может быть представлена более одного раза (отсутствие дублирующих кортежей).

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

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

4. Каждая таблица в описании данных должна иметь уникальное имя.

5. Каждый элемент таблицы должен быть элементом данных.

6. Связи между таблицами на схеме БД устанавливается по одноименным атрибутам данных.

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

 

Операции реляционной алгебры

 

Теоретической основой языков запросов к реляционным БД является реляционная алгебра. Операндами в реляционной алгебре являются отношения R_i и их реализации – таблицы r_i, k_i – арность отношения R_i (количество столбцов); n_i – количество строк в R_i.

Базисный набор операций:

1. Объединение: R=R₁ È R₂. Результат операции R содержит кортежи из R₁ и R₂. Ограничения на операнды: а) k₁=k₂; б) схемы R₁ и R₂ также должны совпадать; в) дублирующие кортежи в результат включаются только один раз. Пример:

 

R1

=

A

B

C

R2

=

A

B

C

R

=

A

B

C

a1

b1

c1

a2

b1

c2

a1

b1

c1

a2

b1

c2

a3

b2

c2

a2

b1

c2

a3

b2

c1

a3

b2

c1

a3

b2

c2

 

SQL: R₁ UNION R₂;

2. Разность: R=R₁ \ R₂. Результат операции R включает в себя кортежи из R₁, которых нет в R₂. Ограничения на операнды: а) k₁=k₂; б) схемы R₁ и R₂ также должны совпадать. Пример:

 

R	=	A	B	C
		a1	b1	c1
		a3	b2	c1

 

SQL: к сожалению в стандарте SQL нет соответствующего оператора, например, как в ORACLE: R₁ MINUS R₂;, поэтому можно воспользоваться другими конструкциями, например: DELETE * FROM R₁ WHERE ID IN (SELECT ID FROM R₂);, где ID – одиночное значение некоторого выражения, например первичного ключа в R₁ и R₂.

3. Декартово произведение. R=R₁ ´ R₂. Результат операции R: каждый кортеж из R₁ дополняется кортежем из R₂; арность результата – k = k₁+k₂; n = n₁*n₂. Результат декартова произведения не может содержать дублирующие кортежи.

Пример: пусть

 

R2	=	B	C	D
		b1	c1	d1
		b2	c2	d1

 

тогда

 

R	=	A	R1.B	R1.C	R2.B	R2.C	D
		a1	b1	c1	b1	c1	d1
		a2	b1	c2	b2	c2	d1
		a3	b2	c1	b1	c1	d1
		a1	b1	c1	b2	c2	d1
		a2	b1	c2	b1	c1	d1
		a3	b2	c1	b2	c2	d1

 

SQL: SELECT * FROM R₁, R₂;

4. Селекция: R = s_F(R_i), где F - логическая формула над атрибутами из R_i. Результатом операции является таблица R, содержащая те же столбцы, что и R_i и строки из R_i, подстановка которых в F дает значение "истина". Пример: R = s_C=c1 (R₁):

 

R	=	A	B	C
		a1	b1	c1
		a3	b2	c1

 

SQL: S ELECT * FROM R₁ WHERE F;

5. Проекция: R = p_X(R_i), где X - подмножество атрибутов их схемы R_i. Результат операции - таблица со схемой (заголовком) X; строки таблицы формируются из таблицы R_i, но только для атрибутов из X (вырезка по столбцам); дублирующие кортежи из результата удаляются. Пример: R = p_BC(R₁)

 

R1	=	B	C
		b1	c1
		b1	c2
		b2	c1

 

SQL: S ELECT DISTINCTROW B,C FROM R₁;

 

Дополнительные операции реляционной алгебры:

1. Пересечение: R=R₁ Ç R₂. Выражение через базисный набор: R=R₁ \ (R₁ \ R₂).

2. Соединение: R=R₁ ^►_F^◄ R₂, где F - логическое выражение над атрибутами из R₁ и R₂. Выражение через базисный набор: R=s_F(R₁ ´ R₂)

3. Эквисоединение. Частный случай соединения, когда F≡R₁.A_i=R₂.A_j.

4. Естественное соединение: R=R₁ ►◄ R₂. Каждый кортеж из R₁ сопоставляется с каждым кортежем из R₂. Два кортежа соединяются, если все одноименные атрибуты в них имеют одинаковое значение, результат соединения помещаются в R. Столбцы для одноименных атрибутов не дублируются, так как значение в этих столбцах совпадают. Пример:

 

R1	=	A	B	C		R2	=	B	C	D
		a1	b1	c1				b1	c1	d1
		a2	b1	c2				b2	c2	d1
		a3	b2	c2

 

Результат:

 

R	=	A	B	C	D
		a1	b1	c1	d1
		a3	b2	c2	d1

 

Выражение через базисный набор: R=p_X(s_F(R₁ ´ R₂)), где F=Ù_i=1,…,k(R₁.A_i=R₂.A_i) – конъюнкция по всем одноименным атрибутам, X= R₁ È R₂ – объединение атрибутов из R₁ и R₂.

 

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

Определение. Пусть задана схема отношения R на совокупности атрибутов U = {A₁, A₂,..., An}, (возможно R – тип записи для структурированной модели данных). Пусть X и Y – некоторые подмножества из множества атрибутов U. Будем говорить, что X функционально определяет Y(X ® Y), если в любой реализации r схемы R не могут присутствовать два кортежа t,u Î r, такие что t[X]=u[X] и t[Y]¹u[Y].

Свойства функциональных зависимостей.

Дано: схема отношения R на совокупности атрибутов U = {A₁, A₂,..., An}, F – множество функциональных зависимостей в R:

Рефлексивность. Если Y Í X Í U, то X ® Y.

Пополнение. Если X ® Y и Z Í U, то XZ ® YZ.

Транзитивность. Если X ® Y и Y ® Z, то X ® Z.

 

Определение. Пусть F – множество функциональных зависимостей, определенных на множестве атрибутов U = {A₁, A₂,..., An}. Тогда через F⁺ обозначим замыкание множества F, полученное из F за счет применения правила логического следствия.

 

Формальное определение первичного ключа

Дано: схема отношения R на совокупности атрибутов U = {A₁, A₂,..., An}, F – множество функциональных зависимостей в R. Множество X Í U, является первичным ключом для R, если выполнено:

1. X ® A₁,A₂,...,An Î F⁺;

2. Для любого Y Ì X (Y -истинное подмножество X) выполнено Y ® A₁,A₂,...,An Ï F⁺.

Замечание. Отношение R может содержать несколько первичных ключей.