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

Основы баз данных.

Введение.

Автоматизированная информационная система (АИС)- это система для сбора, накопления больших объемов информации и выдачи ее на запросы пользователя.

Запрос – это вопрос к базе данных(БД).

АИС длятся на:

· ИПС – информационно поисковые системы;

· БнД – банки данных;

· БЗ – базы знаний.

ИПС

Хранит большие объемы информации, которая является медленно меняющейся.

Классический пример – библиотека.

ИПС строятся как двухконтурные:

В первом контуре хранятся книги, а во втором контуре - документы, представляющие книгу – поисковые образцы документов (ПОД).

Требования, заполняемые на книгу, называются поисковыми образцами запроса (ПОЗ). По ПОЗ находим ПОД и обращаемся в первый контур.

Поиск можно делать вручную или воспользоваться электронными каталогами. Еще одним примером ИПС является телефонный справочник.

ПОД строится на основе тезауруса – обратного словаря (такие слова нужно включить в картотеку, чтобы понять к какой области относится книга).

УДК - Универсальная десятичная классификация (комбинация цифр указывает на область).

ББК- для классификации книг из гуманитарной области. Индекс начинается с буквы.

БнД. (фактографические информационные системы)

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

БнД является информационной моделью некоторой предметной области (ПО).

ПО – часть реального мира, информация о которой хранится в БнД.

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

Атрибуты – это характеристики, позволяющие отделить один объект от другого.

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

Ключ + дополнительные атрибуты=супер-ключ.

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

Вся эта информация формализуется в виде предметной области. Эта модель реализуется в виде БнД.

БЗ Хранятся не только данные, но и знания о применении этих данных. Реализуются они в виде процедур и алгоритмов. Выборки обрабатывают данные.

Пример. Иван является сыном Петрова.

История БнД.

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

Преимущества:

· К новой системе нужен только комплекс технологических программ;

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

· Устранены аномалии технологических операций;

· Целостность хранимой информации – соответствие информации, хранящейся в банке, реальному положению в предметной области.

Проблемы БД:

· Администратор БнД (АБД) - человек или группа людей- должны поддерживать БД в актуальном состоянии;

· Восстановление данных при сбоях оборудования;

· Нарушение физической целостности при сбоях оборудования.

Меры преодоления проблем нарушения физической целостности:

1. введение копии базы данных

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

 

 

 

Рис.1

В 4 контрольной точке затирается дед, отец становится дедом, сын – отцом и появляется новый сын.

 

Рис.2

 

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

2. Второй вариант решения проблемы нарушения физической целостности6

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

3. Третий вариант предполагает наличие двух баз одновременно, с одной мы работаем, а изменения происходят в двух базах одновременно, если одна из баз данных выходит из строя, то мы работаем с другой.

· Логическая целостность – нарушается, если база некорректно обновлена

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

Меры защиты:

1. Ограничивается доступ к информации по обновлению;

2. Устанавливаются специальные фильтры или маски, которые проверяют формат введенной информации;

3. Используются специальные активные процедуры (триггеры), которые могут проверить соответствие формата.

· Семантическая целостность – соответствие данных в разных полях.

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

Например, дата окончания школы не может быть на 16 лет раньше рождения.

Механизмы поддержания семантической целостности:

1. Механизм триггеров - активная процедура, автоматически вызывается, когда это необходимо.

2. Существуют специальные процедуры, которые осуществляют контроль за внесенной информацией..

· Защита от несанкционированного доступа.

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

· Коллективный доступ к данным

1. Совместное обновление.

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

 

 

Первый пользователь, который первым предъявил права, блокирует поле для других,

вносит в это поле 7, снимает блокировку, право переходит ко второму пользователю, который вносит 3, это значение поля не верно для пользователя первого. Чтобы такого не было, уровни изоляции могут распространяться на всю базу, на отдельную таблицу, на запись, на поле. Изоляция идет на все время, пока первый пользователь не закончит работать с базой, с отдельной таблицей, записью…

2. Представление – часть базы данных, отобранная из реального хранилища предоставленная для работы пользователя – виртуальная база.

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

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

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

Состав БнД.

БнД= БД+СУБД+с/с+АБД, где

БнД – банк данных;

БЗ – база данных – это главная часть;

СУБД – система управления базой данных;

с/с – словарь-справочник;

АБД – администратор.

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

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

Существуют разные модели:

1. Реляционная модель (Кодд,1970г.).

Вся информация в реляционной модели хранится в виде таблиц. Базы данных в Oracle, Paradox, Informix, SQL-Server построены на основе реляционной модели.

2. Иерархическая модель (Фирма IBM, 60-ые гг.).

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

3. Сетевая модель (конец 60-х).

Эта модель была получена обобщением опыта и устранением ошибок иерархической модели. Самая известная сетевая модель - это IDS. Эта модель, переведенная на русский язык, получила название Сиод.

В сетевой модели сейчас популярен банк db_Vista.

4. Модель данных на основе инвертированных структур.

Первый банк на основе инвертированных структур –это Adabas. В нашей стране этот банк появился в русской интерпретации под названием Дисод. Недостаток такой модели в том, что все списки нужно хранить в памяти.

СУБД кроме модели имеет 2 языка:

ЯОД – язык описания данных (DDL – в английской интерпретации), предназначен для описания структуры хранимой информации и для описания ограничений целостности.

ЯМД – язык манипулирования данными, позволяет выдавать запросы и получать ответы.

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

С/с - метаданные, которые описывают структуру хранимой информации, содержит также систему помощи.

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

Виды связи

Оно показывает, сколько экземпляров одного объекта вступает в связь со сколькими экземплярами другого объекта.

Вид связи это не абсолютная характеристика и меняется в зависимости от предметной области, в которой и работает.

Виды связи бывают:

1:1

1:n (один ко многим)

n:1 (многие к одному)

n:n (многие ко многим)

Класс принадлежности указывает все ли объекты вступают в связь или есть такие, которые не связаны. Бывает:

- обязательный класс принадлежности (все объекты обязательно вступают в связь) в диаграмме типов обозначается

 

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

 

Пример видов связей. (16 – вариантов)

Предметная область – преподаватель читает некоторые лекции.

Пример: тип связи один ко одному.

Существует ПО такая, что один преподаватель читает не больше одной дисциплины, каждая дисциплина читается не больше чем одним преподавателем.

ER-диаграмма экземпляров

преподаватель предмет

1 1

2 2

3 3

4 4

 

тогда диаграмм типов следующая

1 1

 

Другой вариант

- дисциплина читается обязательно одним преподавателем.

 

1 1

 

 

Третий вариант

- преподаватели все должны читать лекции, но есть предметы, которые не читаются.

1

2

4

5

1 1

 

 

Четвертый вариант

- преподаватель читает одну дисциплину, предмет читается один раз.

 

4

1 1

 

 

пример: тип связи один ко многим

- преподаватель читает несколько дисциплин, предмет читается не больше чем одним преподавателем.

 

1 n

 

 

- преподаватель читает несколько дисциплин, предмет читается не больше чем одним преподавателем, дисциплины должна быть прочитаны все.

 

 

 

1 n

 

 

-преподаватели читают несколько дисциплин, дисциплины и преподаватели все заняты, дисциплина читается одним преподавателем.

 

1 n

 

- все преподаватели заняты, могут читать несколько предметов.

 

 

5

7

 

1 n

 

 

Пример многие к одному

- одна дисциплина может читаться несколькими преподавателями. Преподаватель не может читать несколько дисциплин.

 

 

n 1

 

 

- одна дисциплина может читаться несколькими преподавателями, все преподаватели заняты.

 

n 1

 

- одна дисциплина может читаться несколькими преподавателями, все предметы заняты.

 

 

n 1

 

 

- одна дисциплина может читаться несколькими преподавателями, все преподаватели и предметы заняты.

 

 

n 1

 

 

Пример многие ко многим

- преподаватель может читать несколько дисциплин, дисциплины могут читаться несколькими преподавателями.

 

n n

 

 

- преподаватель может читать несколько дисциплин, дисциплины могут читаться несколькими преподавателями, все предметы и преподаватели заняты.

 

 

n n

 

- преподаватель может читать несколько дисциплин, дисциплины могут читаться несколькими преподавателями, заняты все преподаватели.

 

 

n n

 

 

- преподаватель может читать несколько дисциплин, дисциплины могут читаться несколькими преподавателями, заняты все дисциплины.

 

 

n n

 

 

Рекурсивные связи

-возникают внутри одного и того же объекта.

Существует два типа рекурсивных связей:

-1:n;

-n:n;

1. 1:n – например, отношение сотрудник- подчиненный на множестве подчиненных (но начальник тоже сотрудник).

		Сотрудник в данном случае имеет роль начальника
	n

 

Вводится понятие роль – это таблица, соединенная сама с собой. Для того чтобы различать объекты даем им разные роли.

2. n:n

Пример:

Описание структуры изделие, изделие состоит из сборочных единиц.

Изобразим граф изделия:

 

В данном графе 2,3,4 – это узлы, а 5,6,7 – это детали. Числа рядом с линиями показывают в каком количестве детали входят в узлы, например, в узел 2 входят 3 детали 5, 2 детали 6 и 1 деталь 3.

Роль деталь имеют те сборочные единицы, которые где-то применяются: 2-7.

Узел собирается из нескольких сборочных единиц: 1-4.между ними существует связь:

 

 

В реальном проектировании связь М:М представляется в виде трех отношений, причем между 1 3 – 1:М, между 2 и 3 – 1:М.

Таблица 1:

Сборочная единица

Таблица 2 (сборка):

Роль- узел (1)	Роль- деталь (2)	Количество (3)

Из этих таблиц:

№изделий = 1\2;

№деталей = 2\1;

№узла = 1 2.

Избыточное дублирование.

Дублирование – повторение значений некоторого атрибута.

Иногда от дублирования невозможно избавиться, так как при этом может произойти потеря информации.

Пример.

№служащего	Фамилия начальника	№телефона начальника
	Иванов
	Петров
	Петров
	Иванов

Чтобы избавиться от избыточного дублирования нужно данную таблицу разбить на 2:

№служащего	Фамилия начальника
	Иванов
	Петров
	Петров
	Иванов

 

Фамилия начальника	телефон
Иванов
Петров

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

Автор этой модели Тед Кодд, год рождения этой модели 1970. Основа этой модели – математическая теория отношений.

Отношение – это множество кортежей, среди которых нет повторений. Каждый объект описывает отдельный объект предметной области или связь между ними. Отношения в реляционной модели данных представлены в виде таблиц.

Например:

номер	название	вес
	Гайка
	Болт
	Винт

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

Домен = dom содержит множество возможных значений данного атрибута.

Любая таблица есть подмножество деккартового произведения доменов

table

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

Целый 1-1000;

Вес 1-1000 гр.

А ограничения цвета можно записать в виде списка.

Атрибуты в модели Кодда должны быть атомарными, т.е. неделимыми, из стандартного набора доменов.

При этом возможны следующие ситуации:

1. Не всегда в предметной области атрибуты бывают атомарными (скалярными)

{13.03.2000}

2. Атрибуты бывают повторяющимися – множество значений одного типа, которые вместе характеризуют какое-то свойство

Песни, исполняемые в концерте.
номер	автор
	Державин
	Пахмутова
	Добронравов
	Добрынин

3. Группа состоит из нескольких атрибутов разного типа:

....	адрес
....	Москва, ул. Ленина 17-18

Чтобы избавиться от групп, нужно разбить эту колонку на разные составляющие: город, улица, дом, квартира.

4. Наличие повторяющейся группы – нескольких групповых атрибутов:

Например,

Ф.И.О.	адрес
Иванов...	Постоянной прописки
	Временной прописки

Два адреса нельзя повторить, нужно снова ввести Ф.И.О. и новый адрес.

При этом могут возникнуть следующие аномалии:

1. аномалия добавления

мы не сможем записать новое лицо, пока не будем знать о нем все, так как пустых значений быть не должно.

2. Аномалия удаления

При удалении удаляется вся строка, при этом могут удалиться нужные сведения.

3. Аномалия изменения

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

При составлении таблиц нужно помнить, что атрибуты могут следовать в любом порядке, т.е.

Название, вес, цвет, номер номер, название, цвет, вес.

Состав базу данных о поставщиках, деталях и поставках:

Создадим таблицу Поставщики (№поставщика, фамилия)

№ поставщика	фамилия
	Иванов
	Петров
	Сидоров

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

Таблица Детали (№, название, цвет, вес) имеет вид:

№детали	Название детали	вес	цвет
	Гайка		серый
	Болт		черный
	винт		красный

Таблица Поставка (№детали, №поставщика, количество):

№детали	№поставщика	количество

В таблице Поставки комбинация №поставщика и №детали является первичным ключом, а по отдельности они являются внешними ключами.

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

Правил Кодда,

Операции над данными.

Существует три класса операций:

1. Реляционная алгебра – процедурный язык, операндами выступают таблицы, и в ответе мы тоже получаем таблицы.

2. Исчисление кортежей (SQL) – декларативный язык. В качестве переменных выступают кортежи.

3. Исчисление доменов (QBE). В качестве переменных выступают столбцы.

Реляционная алгебра.

Договоримся, что малыми латинскими буквами мы будем обозначать таблицы, большими латинскими буквами – атрибуты и множества атрибутов. Например, r(R) – это таблица r со множеством атрибутов R.

R(A,B,C.D) – ключевые атрибуты подчеркиваются - R={A,B,C,D}.

Операции:

1. Операция объединения.

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

Пример:

r(A,B,C) s(A,B,C) = q(A,B,C)

a1bc1 a2bc a1bc1

abc1 a1bc1 abc1

ab1c ab1c ab1c

a2bc

2. Операция разность.

Эта операция определена над двумя таблицами с одинаковой схемой, результатом является третья таблица с такой же схемой, в которой есть кортежи, которые есть в первой таблице, но нет во второй.

Пример:

r(A,B,C) \ s(A,B,C) = q(A,B,C)

a1bc1 a2bc abc1

abc1 a1bc1

ab1c ab1c

3. Декартово произведение.

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

r(A,B) s(C,D) = q(A,B,C,D)

ab cd abcd

a1b cd1 abcd1

a1bcd

a1bcd1

4. Операция пересечения.

Эта операция не является основной, ее можно выразить через операцию разности: r s=r\(r\s).

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

Пример:

r(A,B) s(A,B) = q(A,B)

ab ab ab

a1b1 a1b a1b

a1b a2b2

a2b1

5. Операция селекции ().

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

Пример:

R(A,B,C) = g(A,B,C)

123 123

245 138

При этом дублирование не допускается.

= q’(A,B,C)

6. Операция проекции ().

В качестве исходных данных имеем одну таблицу и в ответе одну таблицу, которая содержит только указанные столбцы. X R – X является подмножеством R.

Пример:

R(A,B,C) =q(A) = q’(B,A)=q’(A,B) порядок столбцов

112 1 11 11 не фиксируется

123 2 21 12

145 41 14

223 22 22

7. Операция соединения (основная).

Обозначение: Join или .

Существует внутренняя операция соединения и внешняя, при этом внешняя делится на правую и левую.

· Внутренняя

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

r(A,B,C) s(A,B,D) = q(A,B,C,D)

112 11a 112a

113 11b 112b

123 42c 113a

145 113b

421 421c

операция соединения для таблиц с одинаковыми схемами равносильна операции пересечения:

r(A,B) s(A,B) = q(A,B)

11 11 11

12 42 42

Операция соединения для таблиц с разными схемами равносильна декартовому произведению:

r(A,B) s(C,D) = q(A,B,C,D)

11 cd 11cd

12 c1d 11c1d

14 12cd

42 12c1d

14cd

14c1d

42cd

42c1d

б) Тета-соединение ().

Это соединение не обязательно по равенству, операция соединения происходит по любой операции сравнения( =(эквивалентное соединение),<>, <,>).

Тета-соединение осуществляется не обязательно по одноименным столбцам, а по разным тоже, но столбцы должны быть определены на одних и тех же доменах.

r(A,B,C) s(D,E) = q (A,B,C,D,E)

B=D

a1c 1e a1c1e

a12c 1e1 a1c1e1

a11c2 2e a2c2e

a13c 2e1 a12c2e1

a11c21e

a11c21e1

r(A,B,C) s(D,E) = q (A,B,C,D,E)

B>D

a1c 1e a12c1e

a12c 1e1 a12c1e1

a11c2 2e a13c1e1

a13c 2e1 a13c1e

a13c2e

a13c2e

· внешнее соединение. Рассмотрим на примере естественного соединения. тогда внешнее соединение выполняется по тем же правилам, что и естественное, но в ответ выписываются строки из левой таблицы, если соединение левое (из правой таблицы, если соединение правое).

Пример:

r(A,B,C) s(A,D) = q(A,B,C,D)

left

1ac 1d 1acd

2a1c 2d 1acd1

1ac1 1d1 2a1cd

3ac 1ac1d

4a1c 1ac1d1

3ac null

4a1c null

8. операция деления. (операция обратная декартовому произведению).

Пусть нам дано: r(R), s(S), тогда =R\S,

а r’()=r s={t| S }, где r’- частное.

То есть нужно найти такое отношение r’, что оно будучи декартово перемножено с s дает приблизительно r.

Пример:

r(A,B,C,D) s(C,D) r[CD CD]s = r’(A,B)

abef ef ab

abcd dc ef

abdf

efdc

efef

afdc

Проверка:

r’ s = A,B,C,D

abef

efef

abdc

efdc

операция деления равносильна квантору общности в математической логике.

Эту операцию можно выразить через другие операции:

Убедимся, что операция деления равносильна квантору общности:

Пусть у нас есть данные о том, какой пилот каким типом самолета может управлять –

Право (пилот, тип самолета)

Иванов ТУ 154

Иванов ИЛ 62

Иванов ЯК 42

Петров ТУ 154

Петров ИЛ 62

Смирнов ТУ 154

Смирнов ИЛ 62

Смирнов ЯК 42

Смирнов АН 24

Панин ИЛ 62

Запрос: найти пилотов, которые могут управлять всеми типами самолетов из следующего списка: ТУ 154;

Ил 62;

ЯК 42;

То есть q(тип самолета)

ТУ 154

Ил 62

ЯК 42

право q

Иванов

Смирнов

Запрос: нужно найти пилотов, которые умеют управлять самолетом ТУ 154

q’(тип самолета)

ТУ 154

Право q’

Иванов

Петров

Смирнов

Методы проектирования.

1. Метод нормализации.

Метод начинается с универсального отношения и основан на постепенном переходе к пятой нормальной форме.

Пример:

Фамилия автора	произведение
Пушкин	Евгений Онегин, Капитанская дочка,...
Лермонтов	Герой нашего времени, Кавказский пленник,...

В этой таблице атрибут Произведение является повторяющейся группой, таблица не является нормализованной. Для перехода к первой нормальной форме дублируем: