Вопросы для госэкзамена по курсу "Базы данных и знаний"

Вопросы для госэкзамена по курсу “Базы данных и знаний”

Реляционная модель данных. Основные понятия: отношение, кортеж, домен. Реляционная алгебра (РА).

Реляционная модель данных – самая распространенная из существующих сейчас моделей данных, основана на понятии таблицы или отношения (relation), эту модель предложил в 1970 г. Э.Ф.Кодд.
Отношение (таблица) – это подмножество декартова произведения списка доменов. Пример: пусть у нас есть три домена:

D1 ={1,2,5}, D2={a,b}, D3={C,D,E}. Их декартово произведение:

D1D2D3={(1, a, C), (1, a, D), (1, a, E), (1, b, C), (1, b, D), (1, b, E),

(2, a, C), (2, a, D), (2, a, E), (2, b, C), (2, b, D), (2, b, E),

(5, a, C), (5, a, D), (5, a, E), (5, b, C), (5, b, D), (5, b, E)}. Любое подмножество этого множества представляет собой отношение.

Домен – это область определения атрибута объекта (столбца таблицы).

Кортеж, или запись – это строка таблицы.
РА представляет собой математический аппарат для работы с объектами-отношениями (таблицами). Кроме РА, существуют также теории реляционного исчисления на доменах и реляционного исчисления на кортежах, эквивалентные теории РА.
Операндами и результатами операций в РА являются отношения (таблицы).

Схема отношения – список столбцов таблицы с их именами и

типами.
Пример реляционной модели “Поставка деталей” (подчеркнуты ключевые поля):

ДЕТАЛЬ (ДИмя, ДНомер, ДМодель, ДЦена)

ПОСТАВЩИК (ПИмя, ПНомер, Город)

КЛИЕНТ (КИмя, КНомер, Город)

ПОСТАВКА (ДНомер, ПНомер, КНомер, Дата, Колво)

Унарные операции:
Проекция

proj список_полей (Таблица) – выполняется в два этапа:

сначала выбираются нужные столбцы,

затем вычеркиваются повторяющиеся строки.

Пример: найти все названия поставщиков и города, в которых они находятся

proj ПИмя, Город (ПОСТАВЩИК)

Выбор

sel условие (Таблица)

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

AND, OR, NOT. Строки-константы задаются в кавычках.

Схема таблицы-результата совпадает со схемой исходной таблицы.

Пример: найти все детали модели МС550:

sel ДМодель=”МС550”(ДЕТАЛЬ)

Бинарные операции:

приоритет унарных операций выше, чем бинарных.
Соединение

Таблица1 join Таблица2

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

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

Пример: напечатать всевозможные пары Поставщик-Клиент, находящиеся в одном городе.

proj ПИмя, КИмя (ПОСТАВЩИК join КЛИЕНТ)

Следующие три операции аналогичны операциям над множествами.

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

Таблица1 union Таблица2

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

Пример: напечатать названия городов, в которых есть либо Поставщик, либо Клиент (хотя бы один).

proj Город (ПОСТАВЩИК) union proj Город (КЛИЕНТ)

Пересечение

Таблица1 intersection Таблица2

Строка попадает в результирующую таблицу, если она присутствует как в первом, так и во втором операнде.

Пример: напечатать названия городов, в которых есть и Поставщик, и Клиент.

proj Город (ПОСТАВЩИК) intersection proj Город (КЛИЕНТ)

Вычитание

Таблица1 difference Таблица2

Строка попадает в результирующую таблицу, если она присутствует в первом, но не присутствует во втором операнде.

Пример: напечатать названия городов, в которых есть Поставщики, но нет Клиентов.

proj Город (ПОСТАВЩИК) difference proj Город (КЛИЕНТ)

Умножение (декартово произведение)

Таблица1 product Таблица2

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

Результат формируется следующим образом: каждая строка первой таблицы сцепляется с каждой строкой второй таблицы.

Пример: получить всевозможные пары Поставщик-Клиент.

proj ПИмя, КИмя (ПОСТАВЩИК product КЛИЕНТ)

Деление

Таблица1 division Таблица2

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

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

Таблица1

F1 F2 F3

A 1 z

B 1 z

C 1 z

A 2 d

B 2 d

A 5 q

C 5 q

Таблица 2
F1

Таблица1 division Таблица2
F2 F3

1 z

Пример: получить номера Поставщиков, которые выполняли поставки всем Клиентам из Москвы.

proj ПНомер, КНомер (ПОСТАВКА)

division

proj КНомер (sel Город= “Москва”(КЛИЕНТ))

Примечание: операции proj, sel, product, union и difference являются основными, intersection, join и division – производными, их можно вывести с помощью основных операций.
2. Реляционная модель данных. Теория нормализации. Нормальные формы: первая, вторая, третья, Бойса-Кодда, четвертая, пятая.
Реляционная модель данных – самая распространенная из существующих сейчас моделей данных, основана на понятии таблицы или отношения (relation), эту модель предложил в 1970 г. Э.Ф.Кодд.

Цели теории нормализации:

устранение дублирования информации;
решение проблемы “присоединенных записей” (см. ниже).

Ключ-кандидат таблицы – поле или набор полей, однозначно идентифицирующий кортеж. Обычно один из ключей-кандидатов выбирается в качестве первичного ключа.
Функциональная зависимость. Пусть X и Y – списки полей таблицы. Говорят, что Y функционально зависит от X, если каждому значению X соответствует единственное значение Y.

Полная функциональная зависимость. Пусть X и Y – списки полей таблицы. Говорят, что Y находится в полной функциональной зависимости от X, если:

Y функционально зависит от X;
Y функционально не зависит ни от какого подмножества X’ X, X’ X.

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

Пусть схема таблицы разбита на 3 непересекающиеся части: H, J, K. Если K функционально зависит от J, то выполняется утверждение:

Таблица = proj H,J (Таблица) join proj J,K (Таблица)
Процесс нормализации заключается в переходе от исходной таблицы к ее полной декомпозиции вплоть до получения таблиц в пятой нормальной форме.
Первая нормальная форма – таблица находится в 1НФ тогда и только тогда, когда в каждом ее поле (на пересечении строки и столбца) находится ровно одно значение (не более одного и не ноль значений, специально для выполнения этого требования придумано значение NULL).

Пример нарушения 1НФ: в поле Номер_телефона указано несколько номеров через запятую.
Вторая нормальная форма - таблица находится в 2НФ тогда и только тогда,

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

Пример нарушения 2НФ: рассмотрим таблицу:

Заказы (Номер_заказа, Код_товара, Описание_товара, Количество)

Описание_товара функционально зависит от Код_товара, т.е, от части ключа. Применяя теорему Хита, разобьем эту таблицу на 2 проекции:

Заказы2 (Номер_заказа, Код_товара, Количество)

Товары (Код_товара, Описание_товара)

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

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

Пример нарушения 3НФ: рассмотрим таблицу:

Сотрудники (Табельный_номер, ФИО, Номер_отдела, Название_отдела)

Название_отдела функционально зависит от Номер_отдела т.е, от неключевого поля. Применяя теорему Хита, разобьем эту таблицу на 2 проекции:

Сотрудники2 (Табельный_номер, ФИО, Номер_отдела)

Отделы (Номер_отдела, Название_отдела)

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

Пример нарушения НФБК: рассмотрим таблицу (предполагается, что нет одинаковых городов):

Адреса (Индекс, Город, Улица)

Город функционально зависит от Индекс.

Разбивать такую таблицу на 2 проекции не стоит. Лучше смириться с таким нарушением.

Четвертая нормальная форма - таблица находится в 4НФ тогда и только тогда, когда в каждой полной декомпозиции, состоящей из двух проекций, каждая проекция содержит ключ-кандидат исходной таблицы.

Пример нарушения 4НФ: рассмотрим таблицу

Сотрудник

Фамилия	Знание_языка	Имя_ребенка
Смит	Английский	Джон
Смит	Английский	Мери
Смит	Немецкий	Джон
Смит	Немецкий	Мери

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

Фамилия	Знание_языка	Фамилия	Имя_ребенка
Смит	Английский	Смит	Джон
Смит	Немецкий	Смит	Мери

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

3. Язык SQL (произносится “эс ку эль”, англоязычные программисты и русскоязычные снобы от программирования называют его “сиквэл”)

Structured Query Language – стандартный язык управления реляционными базами данных с архитектурой клиент-сервер.
Основные вехи развития языка:

1970 г. – д-р Э.Ф.Кодд публикует статью “Реляционная модель больших банков совместно используемых данных”;

1974 г. – публикация статей о SEQUEL;

1979 г. – выпущена реляционная СУБД компании ORACLE;

1981 г. – Relational Technology выпускает СУБД Ingres;

1983 г. – IBM выпускает СУБД DB2;

1986 г. – предложен стандарт ANSI-SQL, выпущена СУБД Sybase;

1987 г. – ISO принимает стандарт SQL;

1988 г. – Microsoft и Ashton-Tate выпускают SQL Server под OS/2;

1989 г. – создается консорциум SQL Access Group;

1992 г. – принят стандарт SQL-92;

1993 г. – внедрение протокола ODBC.

Правило №5 д-ра Кодда (из правил-требований к реляционной модели) гласит: язык доступа к данным должен быть единственным способом доступа к данным в реляционной СУБД.
Составные части SQL:
DDL – data definition language (язык определения данных)

включает всевозможные команды создания (CREATE), удаления (DROP) и изменения структуры (ALTER) объектов, таких, как таблицы (TABLE), представления (VIEW), триггеры (TRIGGER), пользователи (USER) и т.п.

Пример создания таблицы “Организации”:

CREATE TABLE k_firm

(firm_num NUMERIC(6) IDENTITY PRIMARY KEY,

firm_name VARCHAR(100) NOT NULL,

firm_addr VARCHAR(100)

);

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

Пример создания таблицы “Договоры”:

CREATE TABLE k_contract

(contract_num NUMERIC(6) IDENTITY PRIMARY KEY,

contract_date DATETIME DEFAULT GETDATE(),

contract_type CHAR(1)

CHECK (contract_type IN ('A','B','C')),

firm_num NUMERIC(6) NOT NULL,

CONSTRAINT fk_contract_firm_num FOREIGN KEY (firm_num)

REFERENCES k_firm (firm_num)

);

DML - data manipulation language (язык манипулирования данными)

включает команды INSERT, DELETE, UPDATE.

Команда добавления строк в таблицу:

INSERT [INTO] имя_таблицы [(список_полей)]

VALUES (список_значений)

Команда обновления строк таблицы:

UPDATE имя_таблицы

SET поле1=выражение1 [,... , полеN=ВыражениеN]

[WHERE условие]

Команда удаления строк таблицы:

DELETE [FROM] имя_таблицы [WHERE условие]

DQL – data query language (язык запросов к данным)

содержит огромную команду SELECT, имеющую возможности:

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

Примеры приведите самостоятельно.
CCL – cursor control language (язык управления курсорами )

Cursor – current set of record - временный набор записей, позволяющий обрабатывать каждую запись по отдельности. . Необходимость использования курсоров возникла потому, что команды изменения данных (UPDATE, DELETE) применяются к таблице целиком и поэтому являются достаточно “грубыми” для разнообразной “тонкой” работы.
Стандартные операции по работе с курсором:

объявление курсора

DECLARE имя_курсора CURSOR FOR SELECT команда

открытие курсора

OPEN имя_курсора

получение значений из текущей строки и передвижение указателя на следующую строку:

FETCH имя_курсора INTO переменные

закрытие курсора

CLOSE имя_курсора
TPL – transaction processing language (язык проведения транзакций)

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

BEGIN TRAN – начало транзакции,

ROLLBACK TRAN – откат, отмена транзакции; все изменения, сделанные с начала транзакции, будут отменены,

COMMIT TRAN – завершение, подтверждение транзакции; все изменения, сделанные с начала транзакции, будут зафиксированы.

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

Уровни изолированности транзакций:

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

Read commited – допускается читать только данные завершенных транзакций.

Read uncommited - допускается читать “грязные данные”, т.е., данные незавершенных транзакций.

Repeatable read – при повторном чтении данных результат будет точно таким же, как и при первом чтении, даже если данные были изменены.
DCL – data control language (язык управления данными)

содержит команды предоставления (GRANT) и отнимания (REVOKE) прав доступа, а также запрета доступа (DENY).

Примеры:

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

GRANT SELECT, UPDATE ON k_contract TO public

запрет удаления данных из таблицы k_contract пользователю public:

DENY DELETE ON k_contract FROM public
Каждая СУБД имеет свой собственный “диалект” SQL, включающий, кроме основ SQL, команды управления (циклы, условия), функции и пр. средства:

ORACLE – PL/SQL,

MS SQL Server – Transact SQL,

и т.п.

4. Физическая организация баз данных

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

Блок данных

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

В-деревья

У сбалансированного (balanced) дерева каждый лист имеет одинаковое количество предков, иными словами, все листья расположены на одном уровне.
B-деревья относятся к индексно-последовательным структурам.

Они не имеют областей переполнения.

Блоки данных хранятся в листьях дерева. Записи в блоках данных всегда упорядочены.

Остальные вершины содержат индексные блоки

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

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

Первоначально дерево имеет вид

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

Количество блоков, которое необходимо просмотреть при поиске =

max уровень дерева –1.
Добавление записей.

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

Пусть мы помещаем в дерево запись с ключом BA. Блок D2 имеет вид: AW | BA| BG.

Теперь добавляем запись AY. Она должна быть помещена в D2, но в нем нет места. Формируем новый блок D8 и переносим туда часть записей из D2, чтобы оба блока были заполнены более чем наполовину. Добавляем индексную запись в индексный блок I11.

Теперь включим записи CE и DT. CE добавляется в D3. DT также должна быть добавлена в D3, но там нет места. Создаем блок D9, перераспределяем записи данных.

В блоке I12 нет места для указателя на D9, поэтому создаем индексный блок I14, перераспределяем записи. Теперь в блоке I21 нет места для указателя на блок I14, создаем блок I22. У дерева не может быть 2 корня, создаем новый корневой блок I31. Дерево существенно изменило свой вид.

Удаление записей. Сначала проводим поиск, удаляем запись из блока данных, остальные записи сдвигаем к началу блока. Если теперь блок более чем наполовину пуст, то ищем соседний с ним блок, имеющий ту же родительскую вершину и содержащий более чем минимально необходимое количество записей. Если такой блок существует, то переносим часть записей из него, чтобы в оба блока были более чем наполовину заполнены. Если такого блока нет, то сливаем два блока и соответственным образом изменяем индексные блоки, т.е удаляем индексную запись, ссылающуюся на удаленный блок данных. Если теперь индексный блок заполнен менее чем наполовину, то производим те же действия, что и с блоками данных. Этот процесс может привести к уменьшению уровней дерева.
1)Удалим запись AW. Блок D2 более чем наполовину пуст. Сливаем его с D1 или D8.
2)Удалим запись BH. Блок D3 сливаем с D9. Уничтожаем ссылку на D9. I12 более чем наполовину пуст. В блоке I11 более минимума записей, передаем одну в блок I12.
3)Удалим запись JB. Объединяем D6 и D7. Объединяем I14 и I13. Объединяем I21 и I22. Уничтожаем I31.