Skip to content

Latest commit

 

History

History
129 lines (118 loc) · 10.7 KB

db.org

File metadata and controls

129 lines (118 loc) · 10.7 KB

Базы данных

Введение

Требования к СУБД:

  1. Эффективный доступ и хранение данных
  2. Поддержка языка запросов
  3. Поддержка целостности данных
  4. Поддержка транзакций и многопользовательского режима
  5. Поддержка журналирования и архивирования данных Необходимость СУБД как отдельного компонента:
  6. Журналирование и другие метаданные.
  7. Нормализация и более тонкое управление внешней памятью
  8. Управление оперативной(основной) памятью, доступ к физической основной памяти для кэшей и буферов

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

Алгебра Кодда

Операции:

  • UNION – объединение таблиц с совпадающими заголовками
  • INTERSECT – пересечение таблиц с совпадающими заголовками
  • MINUS – разность таблиц с совпадающими заголовками
  • TIMES – декартово произведение таблиц с непересекающимися заголовками, кортежи результата – попарное объединение исходных кортежей
  • WHERE – ограничение таблицы по условию
  • PROJECT – проекция таблицы на множество атрибутов
  • JOIN – соединение кортежей по условию
  • DIVIDE BY – операция, обратная декартову произведению
  • RENAME – переименование атрибутов
  • Присваивание

Приоритеты:

Алгебра A*

  • Реляционное дополнение – дополнение тела операнда до всей таблицы
  • Операция удаления атрибута
  • Операция переименования
  • Реляционная конъюкция – множество кортежей, представляющих попарное объединение кортежей-операндов
  • Реляционная дизъюнкция – множество кортежей, представляющее объединение пар кортежей, хотя бы одна из которых содержится в одном из операндов

Операция дизъюнкции выражается через операцию конъюкции и дополнения по закону де Моргана

Нормализация

  • Теорема Хита Пусть задано отношение $r = \{A, B, C\}$ и выполняется FD $A → B$. Тогда
r = (r PROJECT {A, B}) NATURAL JOIN (r PROJECT {A, C})
  • Первая нормальная форма Значения всех атрибутов атомарны, т. е. их внутренняя структура не видна. Несоблюдение этого требования усложняет структуру тублицы и работу со значениями в ней.
  • Вторая нормальная форма Выполняются требования первой нормальной формы, и каждый неключевой атрибут минимально функционально зависит от первичного ключа. Несоблюдение этого требования усложняет работу с БД, так как первичный ключ содержит избыточную информацию.
  • Третья нормальная форма Отношение находится во второй нормальной форме, и каждый неключевой атрибут нетранзитивно функционально зависит от первичного ключа. При несоблюдении этого требования возникают проблемы с обновлением сущности, входящей в транзитивную зависимость.
  • Теорема Риссанена Проекции $r_1$ и $r_2$ отношения $r$ являются независимыми тогда и только тогда, когда:
    1. каждая FD в $r$ логически следует из FD в $r_1$ и $r_2$.
    2. общие атрибуты $r_1$ и $r_2$ образуют возможный ключ хотя бы одного из этих отношений
  • Нормальная форма Бойса-Кодда Отношение находится в BCNF тогда и только тогда, когда любая выполняемая для него нетривиальная и минимальная FD имеет в качестве детерминанта некоторый возможный ключ этого отношения.
  • Теорема Фейджина

Пусть имеется переменная отношения $R\{A, B, C\}$. Отношение $R$ декомпозируется без потерь на проекции $\{A, B\}$ и $\{A, C\}$ тогда и только тогда, когда для него выполняется MVD $A →\to B | C$.

  • Четвёртая нормальная форма Переменная отношения $r$ находится в четвёртой нормальной форме тогда и только тогда, когда она находится в BCNF, и все MVD $r$ являются FD, детерминантами которых являются возможные ключи $r$.
  • Пятая нормальная форма Переменная отношения $r$ находится в пятой нормальной форме тогда и только тогда, когда любая её зависимость проекции-соединения подразумевается возможными ключами отношения $R$.

Синхронизация

  • Atomicy(атомарность) – результаты транзакции после фиксации либо отражены в состоянии БД полностью, либо не отображены вообще.
  • Consistency(согласованность, целостность) – транзакция может быть зафиксирована тогда и только тогда, когда её действие не нарушает целостности БД.
  • Isolation(изоляция) – две параллельно работающие транзакции не должны действовать одна на другую.
  • Durability(долговечность) – после успешного завершения транзакции все внесённые ей изменения должны сохраняться даже в случае сбоев.

Степени изоляции транзакций:

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

    Таблица совместимости блокировок:

XSIXISSIX
no lockдадададада
Xнетнетнетнетнет
Sнетданетданет
IXнетнетдаданет
ISнетдададада
SIXнетданетданет

B+-деревья

B+-tree – сильно ветвистое сбалансированное дерево, применяется для построения индекса. Внутренние узлы дерева содержат адреса страниц-детей, перемежающиеся с ключами. При этом поддерживается упорядоченность ключей. Листовая страница содержит ключи, за которыми следуют указатели на списки id кортежей, содержащих этот ключ.