Примеры реляционных баз данных. Ограниченная аналитика данных
Уровень 1: Уровень внешних моделей – это самый верхний уровень где каждая модель имеет свое видение данных. Этот уровень определяет точку зрения базы данных отдельных приложений.
Концептуальный уровень: Центральное управляющее звено, где здесь БД представлена в наиболее общем виде, который объединяет данные используемые всеми приложениями. Фактически концептуальный уровень отражает обобщённую модель предметной область.
Физический уровень (База данных): Это сами данные расположенные в файлах или в страничных структурах, расположенных навнешних носителях информации.
Модели данных
Выделяют следующие модели данных:
1. Инфологические
2. Дата логические
3. Физические
Процесс проектирования баз данных начинается с проектирования инфологической модели. Инфологическая модель данных это обобщённое неформальное описание создаваемой БД, выполненное с использованием естественного языка, математических формул, таблиц, графиков и др. средств понятных всем людям работающим над проектированием БД.
Кортеж доменов
Инфологическая модель отображает реальный мир в некоторой понятной человеку концепции, полностью независимой от среды хранения данных. Поэтому Инфологическая модель не должна изменяться до тех пор, пока какие то изменения в реальном мире не потребуют изменения вне определения, чтобы эта модель продолжала отображать предметную область.
Существует множество подходов к построению этой модели: графовые модели, семантические сети, сущность – связь и другие.
Даталогическая модель
Инфологическая модель должна быть отображена в даталогической модели, понятной СУБД. Даталогическая модель это формальное описание инфологической модели на языке СУБД.
Иерархическая модель
Эта модель представляет собой совокупность связанных элементов, образующих иерархическую структуру. К основным понятиям иерархии относятся уровень, узел и связь.
связь уровень
Узлом называется совокупность атрибутов данных описывающих некоторый объект. Каждый узел связан с одним узлом более высокого уровня и с любым количеством узлов нижнего уровня. Исключением является узел самого высокого уровня. Количество деревьев в базе данных определяется количеством корней деревьев. К каждой записи базы данных существует единственный путь от корневой записи. Простым примером может служить система доменных имен в интернете\ адрес. На первом уровне (корень дерева) лежит наша планета земля, на втором Страна, на третьем- Регион, на четвёртом – населённый пункт, улица, дом,квартира. Типичным представителем является СУБД от IBM - IMS.
Все экземпляры данного типа потомка с общим экземпляром типа предка называется близнецами. Для базы данных определён полный порядок обхода. Сверху вниз и с права на лево.
Физическая модель
На основе даталогической модели строится физическая модель. Физическая организация данных оказывает основное влияние на эксплуатационные характеристики базы данных. Разработчики СУБД пытаются создать наиболее производительные физические модели данных, предлагая пользователям тот или иной инструментарий, для под настройки модели для конкретной БД.
Пример: В частности для реляционной БД она уже учитывает:
1. Физические аспекты хранения таблиц в определённых файлах.
2. Создание индексов оптимизирующих скорости операций над данными с помощью приложения.
3. Выполнения различных действий над данными при определённых событиях, определяемых пользователям с помощь триггеров и хранимых процедур.
Инфологические модели ХФизические модели
Для всех уровней и для любого метода представления предметной области, лежит кодирование понятий отношений между понятиями. Ключевым этапом при разработке любой информационной системы является проведение системного анализа:
Формализация предметной области и представление системы как совокупности компонентов.
Композиция как основа системного анализа может быть функциональной (построение иерархия).
Однако в большинстве систем, если говорить о базах данных, типы данных являются более статичным элементом чем способы их обработки. Поэтому получили интенсивное развитие такие методы системного анализа как диаграмма потоков data flown diagram. Развитие реляционных БД. Стимулировала развитие построения методик развития данных в частности ER диаграмм ER. Реляционная модель данных в качестве отображения непосредственно использует понятие отношения. Она ближе всего находится к концептуальной модели представления данных. И часто лежит в основе её.
В отличие от теоретика графовых моделей, в реляционной модели связи между отношениями реализуются не явным способом для чего используют ключи отношений. Например, отношения иерархического типа реализуется механизмом первичных и внешних ключей, когда в подчинённом отношении должен присутствовать факт атрибутов.
Такой атрибут отношений в основном отношений будет называться первичным ключом, а в подчинённом вторичным.
Прогресс в области разработки языков программирования связанных в первую очередь с типизацией данных и появлением объектно-ориентированных языков позволило подойти к анализу сложных систем с точки зрения иерархических представлений то есть с помощью классов объектов со свойствами полиморфизма, наследование, инкапсуляция.
ОТНОШЕНИЕ ЭТО ТАБЛИЦА.
Удаление то что создали и
Редактирование.
Реляционная модель базы данных
Реляционные модели данных в настоящее время приобрели наибольшую популярность именно за такое представление данных.
Реляционную модель можно представить как особый метод представления данных, содержащий собственные данные (в виде таблиц), и способы работы и манипуляции с ними (в виде связей). Реляционная модель предполагает три концептуальных элемента: Структура, Целостность и Обработка данных. В этих элементах есть свои обязательные понятия которые для дальнейшего изложения необходимо пояснить.
Таблица рассматривается как непосредственное хранилище данных. Традиционно в реляционных системах таблицу называют отношением. Строку таблицы называют кортежем , а столбец атрибутом . При этом атрибуты имеют уникальные имена (в пределах отношения).
Количество кортежей в таблице называют кардинальным числом . Количество атрибутов степенью. Для отношения устанавливают уникальный идентификатор, то есть один или несколько атрибутов, значения которых в одно и то же время не бывают одинаковыми – идентификатор называют первичным ключом.Домен это множество допустимых однородных значений для того или иного атрибута. Таким образом домен можно рассмотреть как именованное множество данных причём составные части этого множества являются логически не делимыми единицами (в качестве домена могут выступать например перечень фамилий сотрудников учреждения однако не все фамилии могут присутствовать в таблице).
SUMMОтношение
атрибуты
Поля KOD, NAME, SUMM это атрибуты таблицы содержащиеся в заголовке.
Пары KOD 5216, NAME Киреева, SUMM 25.50 являются элементами тела отношения.
В Реляционных базах данных в отличие от других моделей пользователь указывает какие данные для него необходимы а не то как это делать. По этой причине процесс перемещения и навигации по базе данных в реляционных системах является автоматическим, а эту задачу в СУБД выполняет оптимизатор. Его работа заключается в том чтобы наиболее эффективным способом произвести выборку данных из базы данных по запросу. Таким образом, оптимизатор по крайней мере должен суметь определить из каких таблиц выбираются данные насколько много информации в этих таблицах и каков физический порядок записи в таблицах и как они сгруппированы.
Кроме того реляционная БД выполняет и функции каталога. В каталоге хранится описание всех объектов из которых состоит база данных: таблиц, индексов, триггеров и т.п. Очевидно, что жизненно необходимо для правильной работы всей системы, такой компонент как оптимизатор. Оптимизатор использует информацию хранящуюся в каталоге. Интересен тот факт что каталог сам является набором таблиц, поэтому СУБД может манипулировать им традиционными способами, не прибегая к каким либо особым приёмам и методам.
Домены и отношения
Основные определения: Домены, виды отношений, предикаты.
Отношения имеет ряд основных свойств:
1. В самом общем случае в отношениях не бывает общих кортежей – это следует из самого определения отношений. Однако для некоторых СУБД в ряде случаев допускается отступление от этого свойства. По сколько в отношений имеет место первичный ключ, одинаковые кортежи – исключены.
2. Кортежи не упорядочены сверху вниз – в отношении просто отсутствует понятие позиционного номера. В отношений без потери информации можно с успехом расположить кортежи в любом порядке.
3. Атрибуты не упорядочены слева на право. Атрибуты в заголовке отношений можно располагаетесь в любом порядке, при этом целостность данных не нарушается. Поэтому понятие позиционного номера в отношении атрибута тоже не существует.
4. Значение атрибутов состоят из логически не делимых единиц – это следует из того, что значения берутся из доменов иначе можно сказать, что отношения не содержат групп повторений. То есть являются нормализованными.
В реляционных системах поддерживается несколько видов отношений:
1. Именованные представляют собой переменные отношения определяемые в СУБД путём операторов создания и как правило необходимые для более удобного представления информации для пользователя.
2. Базовые отношения являются непосредственно важной частью БД, поэтому при проектировании им дают собственное название.
3. Производное отношение это то которое было определено через другие, как правило базовые, отношения путём использования средств СУБД.
4. Представление это фактически является именованным производным отношением, при этом представление выражается исключительно через операторы СУБД, применённые к именованным отношениям, поэтому их физически в БД не существует.
5. Результат запросов это не именованное производное отношение содержащее данные(результат конкретного запроса). Результат в БД не хранится а существует до тех пор пока он необходим пользователю.
6. Хранимое отношение это то которое физически поддерживаются в памяти отношений, к хранимым отношениям чаше всего относятся база отношений. Исходя из вышесказанного, можно определить реляционную базу данных как набор отношений, связанных между собой.
Связь в данном случае это ассоциирование двух или более отношений.
| KOD | ADRES |
∞ Бинарная связь
| Студенты |
| Преподы |
| Расписание занятий |
| ∞ |
| ∞ |
| ∞ |
| Студенты |
Тернарные связи
Целостность данных
В реляционных моделях вопросу целостности данных отводят особое место. Напомним, что ключ или потенциальный ключ это минимальный набор атрибутов, по значениям которых можно однозначно найти требуемый кортеж, минимальность означает что исключение из набора любого атрибута не позволяет идентифицировать кортеж по оставшимся атрибутам.
Каждое отношение обладает хотя бы одним возможным ключом. Один из них принимается за первичный ключ.
При выборе первичного ключа следует отдавать предпочтение не составным ключам или ключам, составленных из минимального набора атрибутов. Нежелательно также использовать ключи с длинными текстовыми значениями (Предпочтительней использовать в качестве ключей целочисленные атрибуты) . Так для идентификации работника можно использовать либо уникальный табельный номер, или номер паспорта, либо набор из фамилий имени отчества и номера отдела. Не допускается что бы первичный ключ отношения, то есть любой атрибут участвующий в первичном ключе принимал неопределённые значения. В этом случае возникнет противоречивая ситуация (коллизия ): Появится не обладающий уникальностью элемент первичного ключа. Поэтому при проектировании базы данных за этим следует тщательно следить.
О внешних ключах. Стоит отметить ввиду что отношение С связывает отношения B и А, то оно должно включать внешние ключи, соответствующий первичным ключам отношениям А и В.
Внешний ключ таблицы формируется с помощью нескольких первичных ключей других таблиц.
Таким образом при рассмотрении проблемы выбора способа связи отношения в базе данных возникает вопрос о том каковы же должны быть внешние ключи. При этом для каждого внешнего ключа необходимо решить проблему связанную с возможностью (или невозможностью) появления во внешних ключах неопределённых значений(NULL – значений- значение атрибута для отсутствующей информации). Другими словами может ли существовать некоторый кортеж в отношений, для которого не известен кортеж в связанных с ним отношении?
С другой стороны необходимо заранее обдумать вопрос о том что произойдёт при удаления кортежей из отношения на который ссылается внешний ключ. При этом существуют следующие вероятные возможности:
· Операция каскадируется – то есть удаление кортежей в отношениях приводит к удалению кортежей связанных отношением. Например удаление информации о фамилии имени и т.п. сотрудника в одном отношении приводит к удалению о его заработной плате в другом отношении;
· Операция ограничивается - то есть удаляются лишь те кортежи для которых связанной информации в другом отношении нет. Не вся информация удаляется (не во всех отношениях) так как она может быть использована в другом отношении, удаление информации в котором ведёт к нарушению целостности данных. Если такова информация имеется то удаление осуществить нельзя, например, удаление информации о имени, фамилии и т.п. сотрудника возможно лишь в том случае если информация в связанном отношении о его заработной плате отсутствует.
Нужно предусмотреть технологию того что будет происходить при попытке обновления первичного ключа отношения, на которые ссылается некоторый внешний ключ. Здесь имеются те же возможности как и при удалении:
· Операция каскадируется то есть при обновлении первичного ключа происходит обновление внешнего ключа в связанном отношении. Например обновление первичного ключа в отношении, где хранится информация о сотруднике приводит к обновлению внешнего ключа в отношении с информацией о заработной плате.
· Операция ограничивается то есть обновляются лишь те первичные ключи для которых связанной информации в другом отношении нет. Если таковая информация имеется то обновление сделать нельзя. Например обновление первичного ключа в отношении, где хранится информация о сотруднике, возможна лишь в том случае, если информация о его заработной плате в связанном отношении отсутсвует.1
Реляционная алгебра
Формальной основой базы реляционной модели БД является реляционная алгебра, основанное на теории множеств и рассматривающая специальный оператор над отношениями, и реляционное исчисление базирующиеся на математической логике.
| Произведение |
| А А А Б В В | Г Г Д |
| Г Д |
| А |
| А Б В | Г Г Д | Ж Ж З |
Надо отметить что реляционная алгебра обладает большой мощностью - сложные запросы к базе данных могут быть выражены с помощью одного выражения. Именно по этой причине эти механизмы включены в реляционную модель данных. Любой запрос выражаемый с помощью одного выражения реляционной алгебры, или одной формулой реляционного исчисления, может быть выражен с помощью одного оператора этого языка.
Реляционная алгебра обладает важным свойством - она замкнута относительно понятия отношения. Это означает что выражение реляционной алгебры выполняется над отношениями реляционных баз данных и результаты их вычисления также представляют собой отношения.
Основная идея реляционной алгебры состоит в том что средства манипулирования отношениями, рассматриваемыми как множество основаны на традиционных множественных операциях дополненных некоторыми специфическими операциями для БД.
Опишем вариант алгебры который был предложен КОДДОМ. Операция состоит из 8 основных операторов:
· Выборка отношения (унарная операция)
· Проекция отношения (унарная операция)
· Объединения отношений
· Пересечение отношений(бинарная операция)
· Вычитание отношений
· Произведение отношений
· Соединение отношений
· Деление отношений
Эти операции можно объяснить следующим образом:
· Результатом выборки отношения по некоторому условию является отношение который включает только те кортежи первоначального отношения которые удовлетворяют этому условию.
· При осуществлении проекции отношения на заданный набор его атрибутов будет получено отношение кортежи которого взяты из соответствующих кортежей первого отношения.
· При выполнении операции объединения двух отношений будет получено отношение включающее все кортежи входящие в хотя бы одно из участвующих в операции отношений.
· При выполнении операции пересечения двух отношений будет получено отношение включающее все кортежи входящие в оба первоначальных отношения.
· При выполнении операции вычитания двух отношений будет получено отношение включающее все кортежи входящие в первое отношение, кроме тех которые также входят и во второе отношение.
· При выполнении прямого произведения двух отношений получается отношение кортежи которого являются сочетанием кортежей первого и второго отношения.
· При соединении двух отношений по некоторому условию образуется результирующее отношение кортежей которого является сочетанием кортежей первого и второго отношений, удовлетворяющим этому условию.
· Операция реляционного деления имеет два операнда – бинарная то есть (состоящее из двух атрибутов) и унарная (состоящая из одного атрибута) отношения. Результат операции является отношение состоящее из кортежей включающие отношение первого атрибута кортежей первого отношения, причем таких что множество значений второго атрибута совпадает со множеством значений второго отношения.
Помимо выше перечисленных есть ряд особых операций характерных для работы с базами данных:
· В результате операции переименования получается отношение набор кортежей, которого совпадает с телом первоначального отношения, но имена атрибутов изменены.
Отсюда следует что результатом реляционной операции является некоторое отношение то имеется возможность образовывать реляционные выражения в которых вместо первоначального отношения (операнда), будет использоваться вложенное реляционное выражение. Это происходит благодаря тому факту что операция реляционной алгебры действительно замкнуты относительно понятия отношения. Начнём с операции объединения отношений , однако это в равной мере относится и к операциям пересечения и сочетания, то есть в реляционной алгебры результатом операции объединения является отношение. Если допустить в реляционной алгебре возможность объединения произвольных двух отношений с разными наборами атрибутов, то результатом такой операции будет множество, однако множество разнотипных кортежей, то есть вообще говоря не отношение. Если исходить из требования замкнутости реляционной алгебры относительно понятия отношения то такая операция объединения является бессмысленной. Это приводит к появлению понятия совместимости отношений по объединению : два отношения совместимы только в том случае, когда обладают одинаковыми заголовками, то есть имеет тот же набор имён атрибутов, и одноимённые атрибуты определены в том же домене.
При условии что два отношения совместимы по объединению, при обычном выполнении над ними операции объединения пересечения вычитания результатом операции является отношение с корректно определённым заголовком совпадающим с заголовком каждого из отношений – операндов. Если же два отношения не полностью совместимы по объединению, то есть совместимы во всем кроме имён атрибутов, то до выполнения операции типа соединения, эти отношения можно сделать полностью совместимыми по объединению путём применения операции переименования.
Операция прямого произведения двух отношений вызывает новые проблемы. В Теории множеств прямое произведение может быть получено для любых множеств. Элементы результирующего множества будут являться пары, составленные из элементов первого и второго множества. Поскольку отношения являются множествами то для любых двух отношений возможно получение прямого произведения. Однако результат не будет отношением. Элементами результата будут являться не кортежи, а пары кортежей. Поэтому в реляционной алгебре используется специальная форма операции взятия прямого произведения - расширенное прямое произведение отношений. При взятии расширенного прямого произведения двух отношений элементом результирующего отношения является кортеж, формирующийся при слиянии одного кортежа первого отношения, и одного кортежа второго отношения. Тут же возникает вторая проблема, связанная с получением корректно сформированного заголовка результирующего отношения, это приводит к необходимости ввода понятия совместимости отношений, по взятию расширенного прямого произведения.
Два отношения совместимы по взятию прямого произведения только в том случае, если множество имен атрибутов этих отношений не пересекаются. Любые два отношения могут быть преобразованы к совместимому виду по взятию прямого произведения путём применения операции переименования к одному из этих отношений.
Операция выборки требует наличия двух отношений: первоначального отношения – операнда, и простого условия ограничения. В результате выполнения операции выборки производится отношение заголовок которого совпадает с заголовком отношения операнда, а в тело входят те кортежи отношения операнда, которые удовлетворяют значениям условия ограничения.
Введём ряд операторов.
Пусть union означает операцию объединения, intersect – операция пересечение, minus – операция вычитания. Для обозначения операции выборки будем использовать конструкцию A where B , где А – отношение операнд, а В простое условие сравнения. Пусть С1 и С2 два простых условия выборки
A where C1 AND C2 идентично (A where C1) intersect (A where C2)
A where C1 OR C2 идентично (A where C1) union (A where C2)
A where C1 not C2 идентично (A where C1) minus (A where C2)
С использованием этих определений можно реализовать операции выборки, в которых условием выборки является произвольное логическое выражение составленное из простых условий с использованием логических связей (and, or, not) . Операция взятия проекций отношение А оп списку атрибутов а1, а2,…,an будет отношение заголовком которого является множество атрибутов, а1,а2,…,an. Тело результата будет состоять из кортежей для которых в отношении А имеется кортеж, атрибут а1 имеет значение b1, атрибут а2 значение b2< и так далее атрибут an – bn. По сути при выполнении операции проекции определяется «Вертикальная» вырезка отношения - операнда с удалением возникающих кортежей –дубликатов.
Операция соединения, называемая иногда соединением по условию требует наличия двух операндов – соединяемых отношений, и третьего операнда – простое условие. Пусть соединяется отношение А и В. Как и в случае операции выборки, условие соединения С имеет вид, (а comp –op b) либо (а comp –op const) где А и В имена атрибутов отношений А и В, const- литерально заданная константа. Comp-op – допустимая в данном контексте операция сравнения. Тогда по определению результатом операции соединения является отношение, получаемое путём, выполнения операции ограничения, по условию С прямого произведения отношения А и В.
Имеется важный частный случай соединения, естественное соединение. Операция соединения называется операцией естественного соединения, если условия соединения имеет вид (а=в) где а и в атрибуты разных операндов соединения. Этот случай важен потому что он особо часто встречается на практике и для него существуют эффективные алгоритмы реализации в СУБД. Операция естественного соединения применяется к паре отношений А и В, обладающих общим атрибутом Р, то есть атрибутом с одним и тем же именем и определённым на одном и том же домене. Пусть ав обозначает объединение заголовков отношений А и В. Тогда естественное соединение это спроецированный на ав результат соединения А и В. Операции естественного соединения не включается прямо в состав набора операций реляционной алгебры, но она имеет очень важное практическое значение.
Операция деления отношений нуждается в более подробном объяснении поскольку трудна для понимания. Пусть заданы два отношение А {a1,a2,..,an,b1,b2,…,bm}
B {b1,b2,…,bn} Будем полагать что атрибут b1 отношения A и атрибут b1 отношения B определены на одном и том же домене. Назавём множество атрибутов {aj} составным атрибутом а, множество {bj} cсоставным атрибутом b. После этого будем говорить о реляционном делении бинарного отношения А (а,b) на унарное отношение B (b).
Результатом деления А на В является унарное отношение С (а), состоящее из таких кортежей v что в отношении А имеются кортежи
Поскольку деление наиболее трудная операция поясним её примером. Пусть в БД студентов имеется два отношения: СТУДЕНТЫ (ФИО, НОМЕР) и ИМЕНА (ФИО), причем унарное отношение ИМЕНА содержит все фамилии которыми обладают студенты института. Тогда после выполнения операции реляционного деления отношения СТУДЕНТЫ на отношения ИМЕНА, будет получено унарное отношение содержащее номера студенческих билетов принадлежащих студентам со всеми возможными в этом институте фамилиями.
Реляционное счисление
Допустим имеется база данных обладающая структурой СТУДЕНТЫ (номер, имя, стипендия, код группы), и отношение ГРУППЫ(гр_ном, гр_кол, гр стар) Предположим что необходимо узнать имена и номера студ. билетов у студентов являющимися старостами групп с количеством человек больше 25. В реляционной алгебре нужно предпринять следующие действия для такого запроса:
1. Выполнить соединение отношений СТУДЕНТЫ и ГРУППЫ, по условию «студ_ номер =гр_стар»;
2. Ограничить полученное отношение по условию гр_кол>25.
3. Cпроецировать результат предыдущей операции на атрибут студ_имя, студ_номер.
Здесь пошагово сформулирована последовательность выполнения запроса в базе данных, каждый из которых соответствует одной реляционной операции. если же сформулировать тот же запрос с использование реляционного исчисления То мы получили бы формулу которую можно прочитать: Выдать СТУД_ИМЯ и СТУД_НОМЕР для таких студентов чтобы сосуществовала такая группа ГР_СТАР и значением ГР_КОЛ>25. Во второй формулировке мы указали лишь характеристики результирующего отношения но ничего не сказали о способе его формирования. В этом случае СУБД должна сама решить что за операции и в каком порядке нужно выполнить над отношениями СТУДЕНТЫ и ГРУППЫ. Оба рассмотренных в примере способа на самом деле эквиваленты и существует не очень сложные преобразования из одного в другой.
Базисными понятиями реляционного счисления являются понятия переменной с определённой область её значения, и понятия правильно построенной формулы, опирающиеся на переменные и спец. Функции. Что является областью определения переменной различаются исчисление кортежей, и исчисления доменов то есть вдоль или поперёк. В исчислении кортежей областями определения переменных является отношение баз данных, то есть допустимым значением каждой переменной является кортеж некоторого отношения. В исчислении доменов областями определения переменных являются домены на которых определены атрибуты отношений баз данных то есть допустимым значением каждой переменной является значение каждой переменной.
| Byte | Integer | String | Char | |
| M | ||||
| | N | |||
| K | ||||
Для определения кортежи используется команда RANGE. Например чтобы определить переменную СТУДЕНТ областью определения которой является СТУДЕНТЫ нужно употребить конструкцию RANGE СТУДЕНТ IS СТУДЕНТЫ. Из этого определения следует что в любой момент времени переменная студент представляет некоторый кортеж отношения СТУДЕНТЫ. При использовании кортежных переменных в формулах можно ссылать на значения атрибута переменных. Например для того чтобы сослаться на значение атрибута СТУД_ИМЯ переменной СТУДЕНТ нужно употребить конструкцию СТУДЕНТ.СТУД_ИМЯ.
Правильно построенные формулы служат для выражения условий, накладываемых на кортежные переменные. В основе таких формул лежат простые сравнения, представляющие собой, операции сравнения значений атрибутов переменных и литерально заданных констант. Например конструкция СТУДЕНТ.СТУД_НОМ=123456. Является простым сравнением. Более сложным вариантом составных формул является с помощью логических связей AND, OR, NOT, IF…THEN. Наконец допускается построение правильно построенных формул с помощью кванторов. Если F это правильно построенная формула в которой участвует переменная var то конструкция EXIST (квантор существования) var (F) и FORALL(для всех кортежей) var (F) являются правильными.
Переменные, входящие в правильно построенные формулы могут быть свободными или связанными. Все переменные входящие в их состав при построение которых не использовались кванторы являются свободными. Это означает что если для какого то набора значений свободных кортежных переменных при вычислении формул получено значение «истина», то эти значения могут входить в результирующие отношение. Если же при построении формул используется квантор то переменные являются связанными. При вычислении значения такой правильно построенной формулы используется ни одно значение связанной переменной а вся её область определения.
1)EXISTS СТУД2 (CТУД.1СТУД_СТИП> СТУД2.СТУД_СТИП)
2)FORALL СТУД2 (CТУД.1СТУД_СТИП> СТУД2.СТУД_СТИП)
Пусть СТУД1 и СТУД2 две кортежные переменные определённые на отношение студенты, тогда формула, для текущего кортежа переменной СТУД1 принимает значение истина только в том случае если во всём отношении студенты найдётся такой кортеж связанный с переменной СТУД2 что значение его атрибута СТУД_СТИП удовлетворяет внутреннему условию сравнения. Правильно построенная формула №2 для построенного кортежа СТУД 1 принимает значение истина если для всех кортежей отношение СТУДЕНТЫ связанных с переменной СТУД 2 значение атрибута СТУД.СТИП удовлетворяет внутреннему условию.
Таким образом правильно построенные формулы обеспечивают средства выражения условия выборки из отношения баз данных. Чтобы можно было использовать реляционное исчисление для реальной работы с БД, требуется ещё один компонент который определяет набор и имена столбцов результирующего отношения. Этот компонент называется целевым списком.
Целевой список имеет вид:
· Var.attr –имя свободной переменной, атр имя атрибута отношения на котором определена переменная var.
· Var что эквивалентно отношению от списка, Var.attr1, Var.attr1… Var.attr№ включает имена всех атрибутов определяющего отношения.
· New_name = var.attr; новое имя соответствующего атрибута результирующего отношения.
Последний вариант требуется в тех случаях кода в формуле используется несколько свободных переменных с одинаковой областью определения. В исчислении доменов областью определения доменов являются не отношения а домены. Применительно к бд СТУДЕНТЫ ГРУППЫ можно говорить о доменных переменных ИМЯ (Значения домена – допустимые имена или НОМ СТУД). (Значения домена допустимые номера студентов).
Основным отличием исчисления доменов от исчисления кортежей является наличие дополнительного набора предикатов, позволяющих выражать так называемые условия членства. Если R это n- арное отношение с атрибутами (a1, a2, … an) то условие членства имеет вид R(ai1:Vi1,ai2:Vi2,…aim:Vim) где (m<=n). Где в Vij это либо литерально заданная константа либо имя кортежной переменной. Условие членства принимает значение истина, только в том случае если в отношении R существует кортеж, содержащий следующие значения указанных атрибутов. Если от Vij константа то на атрибут aij накладывается жёсткое условие независящее от текущих доменных переменных. Если же Vij имя доменной переменной то условие членства может принимать различные значения при разных значениях этой переменной.
Предикатом называют логическую функцию, которая для некоторого аргумента возвращает значение истина или ложь. Отношение может быть рассмотрено как предикат с аргументами, являющимися атрибутами рассматриваемого отношения. Если заданный конкретный набор кортежей присутствует в отношении, то предикат выдаст истинный результат в противном случае – ложный.
Вов всех остальных отношениях формулы и выражения исчисление доменов выглядит похожими на формулы и выражения исчисления кортежей. Реляционное счисление доменов положено в основу большинства языковых запросов, основанных на использовании форм.
Похожая информация.
Реляционные БД
Реляционная база данных состоит из одной или нескольких связанных таблиц, структуру которых образуют столбцы и строки.
В реляционных базах данных приняты следующие обозначения:
Отношение - таблица;
Поле- набор однотипных записей для нескольких объектов (столбец);
Кортеж (запись) - строка таблицы, содержащая набор нескольких записей соответствующих одному объекту;
Атрибут - запись в строке одного поля.
Сущность - любой различимый объект, информация о котором хранится в базе данных.
Ключевые поля
Каждое отношение базы данных должно содержать в себе поле (или совокупность нескольких полей), однозначно идентифицирующее каждую запись отношения. Такие поля, позволяют связывать данные нескольких отношений и в конечном счете сформировать единую базу данных. Эти поля называют ключевыми полями.
Различают следующие виды ключей:
Потенциальный ключ - поле, атрибуты которого обеспечивают уникальность записи (в отношении таких полей может быть несколько).
Первичный ключ - один из потенциальных ключей, выбранный в качестве основного (как правило, имеет минимальную длину атрибута).
Внешний (вторичный) ключ - одно или несколько полей отношения, обеспечивающих связь с первичным ключом другого отношения.
В зависимости от количества полей образующих ключ выделяют:
Простой ключ - состоит из единственного атрибута, однозначно определяющего запись (номер зачетной книжки студента).
Составной ключ - состоит из двух и более атрибутов, совокупность которых однозначно определяет запись (серия и номер паспорта человека).
Если в отношении есть уникальное поле, однозначно определяющий каждую запись отношения, то его можно использовать в качестве первичного ключа, но значения его атрибутов должны быть различными для всех записей. Не следует использовать в качестве первичного ключа имена или фамилии людей, т. к. они могут повторятся и в одном отношении могут оказаться люди с одинаковы именем и фамилией. Даже если на данный момент фамилии всех людей зарегистрированных в базе данных разные, поле фамилия не должно использоваться в качестве ключевого, поскольку записи в отношении со временем могут быть изменены в связи с изменением состава людей учтенных в баз данных.
При выборе первичного ключа следует также учитывать, что атрибуты ключевого поля не могут быть пустыми. Если поле допускает пустые значения, то его не следует использовать в качестве первичного ключа.
Также при выборе первичного ключа следует учитывать, что его значения не должны меняются. Если же он меняется, то необходимо обеспечить обновление информации о данном изменении во всех связанных с данным полем отношениях. Применение первичного ключа с постоянным значением позволяет упростить синхронизацию между отношениями в базе данных.
Часто в качестве первичного ключа выбирают искусственно созданное поле, значения атрибутов которого не имеют фактического смысла. Таки полями могут быть Код или Номер , эти поля содержат только числовое обозначение строки, причем зачастую это обозначение выставляет компьютер при помощи счетчика. Такие коды не подвержены изменениям в отличие от полей содержащих фактические данные, т.к. Фамилия, Номер телефона, Адрес и т.д. могут меняться и повторятся.
В том случае если уникальность записи не может быть обеспечена одним полем применяется составной ключ, образованный двумя или более полями. Примером составного ключа могут являться поля серия и номер паспорта, отдельно серия и номер паспорта не могут гарантировать уникальность записи, т.к. есть паспорта с одинаковой серией, так же как и с одинаковым номером, но одновременное совпадение серии и номера двух паспортов невозможно.
РЕЛЯЦИОННАЯ БАЗА ДАННЫХ И ЕЕ ОСОБЕННОСТИ. ВИДЫ СВЯЗЕЙ МЕЖДУ РЕЛЯЦИОННЫМИ ТАБЛИЦАМИ
Реляционная база данных - это совокупность взаимосвязанных таблиц, каждая из которых содержит информацию об объектах определенного типа. Строка таблицы содержит данные об одном объекте (например, товаре, клиенте), а столбцы таблицы описывают различные характеристики этих объектов - атрибутов (например, наименование, код товара, сведения о клиенте). Записи, т. е. строки таблицы, имеют одинаковую структуру - они состоят из полей, хранящих атрибуты объекта. Каждое поле, т. е. столбец, описывает только одну характеристику объекта и имеет строго определенный тип данных. Все записи имеют одни и те же поля, только в них отображаются различные информационные свойства объекта.
В реляционной базе данных каждая таблица должна иметь первичный ключ - поле или комбинацию полей, которые единственным образом идентифицируют каждую строку таблицы. Если ключ состоит из нескольких полей, он называется составным. Ключ должен быть уникальным и однозначно определять запись. По значению ключа можно отыскать единственную запись. Ключи служат также для упорядочивания информации в БД.
Таблицы реляционной БД должны отвечать требованиям нормализации отношений. Нормализация отношений - это формальный аппарат ограничений на формирование таблиц, который позволяет устранить дублирование, обеспечивает непротиворечивость хранимых в базе данных, уменьшает трудозатраты на ведение базы данных.
Пусть создана таблица Студент, содержащая следу-рэщие поля: № группы, ФИО, № зачетки, дата рождения, шазвание специальности, название факультета. Такая организация хранения информации будет иметь ряд недостатков:
- дублирование информации (наименование специальности и факультета повторяются для каждого студента), следовательно, увеличится объем БД;
- процедура обновления информации в таблице затрудняется из-за необходимости редактирования каждой записи таблицы.
Нормализация таблиц предназначена для устранения этих недостатков. Имеется три нормальные формы отношений .
Первая нормальная форма. Реляционная таблица приведена к первой нормальной форме тогда и только тогда, когда ни одна из ее строк не содержит в любом своем поле более одного значения и ни одно из ее ключевых полей не пусто. Так, если из таблицы Студент требуется получать сведения по имени студента, то поле ФИО следует разбить на части Фамилия, Имя, Отчество.
Вторая нормальная форма . Реляционная таблица задана во второй нормальной форме, если она удовлетворяет требованиям первой нормальной формы и все ее поля, не входящие в первичный ключ, связаны полной функциональной зависимостью с первичным ключом. Чтобы привести таблицу ко второй нормальной форме, необходимо определить функциональную зависимость полей. Функциональная зависимость полей - это зависимость, при крторой в экземпляре информационного объекта определенному значению ключевого реквизита соответствует только одно значение описательного реквизита.
Третья нормальная форма. Таблица находится в третьей нормальной форме, если она удовлетворяет требованиям второй нормальной формы, ни одно из ее неключевых полей не зависит функционально от любого другого неключевого поля. Например, в таблице Студент (№ группы, ФИО, № зачетной книжки, Дата рождения, Староста) три поля - № зачетной книжки, № группы, Староста находятся в транзитивной зависимости. № группы зависит от № зачетной книжки, а Староста зависит от № группы. Для устранения транзитивной зависимости необходимо часть полей таблицы Студент перенести в другую таблицу Группа. Таблицы примут следующий вид: Студент (№ группы, ФИО, № зачетной книжки, Дата рождения), Группа (№ группы, Староста).
Над реляционными таблицами возможны следующие операции:
- Объединение таблиц с одинаковой структурой. Результат- общая таблица: сначала первая, затем вторая (конкатенация).
- Пересечение таблиц с одинаковой структурой. Результат - выбираются те записи, которые находятся в обеих таблицах.
- Вычитание таблиц с одинаковой структурой. Результат - выбираются те записи, которых нет в вычитаемом.
- Выборка (горизонтальное подмножество). Результат - выбираются записи, отвечающие определенным условиям.
- Проекция (вертикальное подмножество). Результат - отношение, содержащее часть полей из исходных таблиц.
- Декартово произведение двух таблиц Записи результирующей таблицы получаются путем объединения каждой записи первой таблицы с каждой записью другой таблицы.
Реляционные таблицы могут быть связаны друг с другом, следовательно, данные могут извлекаться одновременно из нескольких таблиц. Таблицы связываются между собой для того, чтобы в конечном счете уменьшить объем БД. Связь каждой пары таблиц обеспечивается при наличии в них одинаковых столбцов.
Существуют следующие типы информационных связей:
- один-к-одному;
- один-ко-многим;
- многие-ко-многим.
Связь один-к-одному предполагает, что одному атрибуту первой таблицы соответствует только один атрибут второй таблицы и наоборот.
Связь один-ко-многим предполагает, что одному атрибуту первой таблицы соответствует несколько атрибутов второй таблицы.
Связь многие-ко-многим предполагает, что одному атрибуту первой таблицы соответствует несколько атрибутов второй таблицы и наоборот.
Понятие реляционный (англ. relation -- отношение) связано с разработками известного американского специалиста в области систем баз данных, сотрудника фирмы IBM д-ра Е. Кодда (Codd E.F., A Relational Model of Data for Large Shared Data Banks. CACM 13: 6, June 1970), которым впервые был применен термин «реляционная модель данных».
В течение долгого времени реляционный подход рассматривался как удобный формальный аппарат анализа баз данных, не имеющий практических перспектив, так как его реализация требовала слишком больших машинных ресурсов. Только с появлением персональных ЭВМ реляционные и близкие к ним системы стали распространяться, практически не оставив места другим моделям.
Эти модели характеризуются простотой структуры данных, удобным для пользователя табличным представлением и возможностью использования формального аппарата алгебры отношений и реляционного исчисления для обработки данных.
Реляционная модель ориентирована на организацию данных в виде двумерных таблиц. Каждая реляционная таблица представляет собой двумерный массив и обладает следующими свойствами:
- - каждый элемент таблицы - один элемент данных; повторяющиеся группы отсутствуют;
- - все столбцы в таблице однородные, т.е. все элементы в столбце имеют одинаковый тип (числовой, символьный и т.д.) и длину;
- - каждый столбец имеет уникальное имя;
- - одинаковые строки в таблице отсутствуют;
- - порядок следования строк и столбцов может быть произвольным. Таблица такого рода называется отношением.
База данных, построенная с помощью отношений, называется реляционной базой данных.
Отношения представлены в виде таблиц, строки которых соответствуют кортежам или записям, а столбцы - атрибутам отношений, доменам, полям.
Поле, каждое значение которого однозначно определяет соответствующую запись, называется простым ключом (ключевым полем). Если записи однозначно определяются значениями нескольких полей, то такая таблица базы данных имеет составной ключ.
Чтобы связать две реляционные таблицы, необходимо ключ первой таблицы ввести в состав ключа второй таблицы (возможно совпадение ключей); в противном случае нужно ввести в структуру первой таблицы внешний ключ - ключ второй таблицы.
Предложив реляционную модель данных, Э.Ф. Кодд создал и инструмент для удобной работы с отношениями - реляционную алгебру. Каждая операция этой алгебры использует одну или несколько таблиц (отношений) в качестве ее операндов и продуцирует в результате новую таблицу, т.е. позволяет "разрезать" или "склеивать" таблицы.
То, чем принципиально отличаются реляционные модели от сетевых и иерархических, на это можно сказать следующим образом: иерархические и сетевые модели данных - имеют связь по структуре, а реляционные - имеют связь по значению.
Проектирование баз данных традиционно считалось очень трудной задачей. Реляционная технология значительно упрощает эту задачу.
Разделением логического и физического уровней системы она упрощает процесс отображения "уровня реального мира", в структуру, которую система может прямо поддерживать. Поскольку реляционная структура сама по себе концептуально проста, она позволяет реализовывать небольшие и/или простые (и поэтому легкие для создания) базы данных, такие как персональные, сама возможность реализации которых никогда даже бы не рассматривалась в старых более сложных системах.
Теория и дисциплина нормализации может помочь, показывая, что случается, если отношения не структурированы естественным образом.
Реляционная модель данных особенно удобна для использования в базах данных распределенной архитектуры - она позволяет получать доступ к любым информационным элементам, хранящимся в узлах сети ЭВМ. Необходимо обратить особое внимание на высокоуровневый аспект реляционного подхода, который состоит во множественной обработке записей. Благодаря этому значительно возрастает потенциал реляционного подхода, который не может быть достигнут при обработке по одной записи и, прежде всего, это касается оптимизации.
Данная модель позволяет определять:
- · операции по запоминанию и поиску данных;
- · ограничения, связанные с обеспечением целостности данных.
Для увеличения эффективности работы во многих СУБД реляционного типа приняты ограничения, соответствующие строгой реляционной модели.
Многие реляционные СУБД представляют файлы БД для пользователя в табличном формате -- с записями в качестве строк и их полями в качестве столбцов. В табличном виде информация воспринимается значительно легче. Однако в БД на физическом уровне данные хранятся, как правило, в файлах, содержащих последовательности записей.
Основным преимуществом реляционных СУБД является возможность связывания на основе определенных соотношений файлов БД.
Со структурной точки зрения реляционные модели являются более простыми и однородными, чем иерархические и сетевые. В реляционной модели каждому объекту предметной области соответствует одно или более отношений. При необходимости определить связь между объектами явно, она выражается в виде отношения, в котором в качестве атрибутов присутствуют идентификаторы взаимосвязанных объектов. В реляционной модели объекты предметной области и связи между ними представляются одинаковыми информационными конструкциями, существенно упрощая саму модель.
СУБД считается реляционной при выполнении следующих двух условий, предложенных еще Э. Коддом:
- · поддерживает реляционную структуру данных;
- · реализует, по крайней мере, операции селекции, проекции и соединения отношений.
В последующем был создан целый ряд реляционных СУБД, в той или иной мере отвечающих данному определению. Многие СУБД представляют собой существенные расширения реляционной модели, другие являются смешанными, поддерживая несколько даталогических моделей.
На сегодняшний день реляционные базы данных остаются самыми распространенными, благодаря своей простоте и наглядности, как в процессе создания, так и на пользовательском уровне.
Основным достоинством реляционных баз данных является совместимость с самым популярным языком запросов SQL.
С помощью единственного запроса на этом языке можно соединить несколько таблиц во временную таблицу и вырезать из нее требуемые строки и столбцы (селекция и проекция). Так как табличная структура реляционной базы данных интуитивно понятна пользователям, то и язык SQL является простым и легким для изучения. Реляционная модель имеет солидный теоретический фундамент, на котором были основаны эволюция и реализация реляционных баз данных. На волне популярности, вызванной успехом реляционной модели, SQL стал основным языком для реляционных баз данных.
Но выявлены и недостатки рассмотренной модели баз данных:
- - так как все поля одной таблицы должны содержать постоянное число полей заранее определенных типов, приходится создавать дополнительные таблицы, учитывающие индивидуальные особенности элементов, при помощи внешних ключей. Такой подход сильно усложняет создание сколько-нибудь сложных взаимосвязей в базе данных;
- - высокая трудоемкость манипулирования информацией и изменения связей.
Для лучшего понимания стоимостной оптимизации мы рассмотрим три распространённых способа объединения двух таблиц и увидим, как даже простой запрос на объединение может превратиться в кошмар для оптимизатора. В нашем рассмотрении мы будем ориентироваться на временнỳю сложность, хотя оптимизатор вычисляет «стоимость» в ресурсах процессора, памяти и операциях ввода/вывода. Просто временнáя сложность - понятие приблизительное, а для определения необходимых ресурсов процессора нужно подсчитывать все операции, включая добавление, операторы if, умножение, итерации и т.д.
Кроме того:
- Для выполнения каждой высокоуровневой операции процессор выполняет разное количество низкоуровневых операций.
- Стоимость процессорных операций (с точки зрения циклов) разная у разных видов процессоров, то есть она зависит от конкретной архитектуры ЦПУ.
Мы говорили о них, когда рассматривали В-деревья. Как вы помните, индексы уже отсортированы. К слову, есть и другие виды индексов, например, битовые (bitmap index). Но они не дают выигрыша с точки зрения использования процессора, памяти и дисковой подсистемы по сравнению с индексами В-деревьев. Кроме того, многие современные БД могут динамически создавать временные индексы для текущих запросов, если это поможет уменьшить стоимость выполнения плана.
4.4.2. Способы обращений
Прежде чем применять операторы объединения, нужно сначала получить необходимые данные. Сделать это можно следующими способами.
- Полное сканирование. БД просто считывает целиком таблицу или индекс. Как вы понимаете, для дисковой подсистемы индекс читать дешевле, чем таблицу.
- Сканирование диапазона.
Используется, например, когда вы используете предикаты наподобие WHERE AGE > 20 AND AGE < 40. Конечно, для сканирования диапазона индекса вам нужно иметь индекс для поля AGE.
В первой части статьи мы уже выяснили, что временнáя сложность запроса диапазона определяется как M + log(N), где N - количество данных в индексе, а М - предположительное количество строк внутри диапазона. Значения обеих этих переменных нам известны благодаря статистике. При сканировании диапазона считывается лишь часть индекса, поэтому данная операция стоит меньше по сравнению с полным сканированием.
- Сканирование по уникальным значениям. Используется в тех случаях, когда вам нужно получить из индекса только какое-то одно значение.
- Обращение по ID строки.
Если БД использует индекс, то бόльшую часть времени она будет заниматься поиском связанных с ним строк. Например, мы делаем такой запрос:
SELECT LASTNAME, FIRSTNAME from PERSON WHERE AGE = 28
Если у нас есть индекс для колонки возраста, то оптимизатор воспользуется индексом для поиска всех 28-летних, а затем запросит ID соответствующих строк таблицы, поскольку индекс содержит информацию только о возрасте.Допустим, у нас другой запрос:
SELECT TYPE_PERSON.CATEGORY from PERSON, TYPE_PERSON WHERE PERSON.AGE = TYPE_PERSON.AGE
Для объединения с TYPE_PERSON будет использоваться индекс по колонке PERSON. Но поскольку мы не запрашивали информацию у таблицы PERSON, то и обращаться к ней по ID строк никто не будет.Данный подход хорош только при небольшом количестве обращений, поскольку он дорог с точки зрения ввода/вывода. Если вам нужно часто обращаться по ID, то лучше воспользоваться полным сканированием.
- Другие способы . О них можно почитать в документации Oracle . В разных БД могут использоваться разные названия, но принципы везде одни и те же.
Итак, мы знаем, как получить данные, пришла пора их объединить. Но сначала давайте определимся с новыми терминами: внутренние зависимости и внешние зависимости . Зависимостью может быть:
- таблица,
- индекс,
- промежуточный результат предыдущей операции (например, предыдущего объединения).
Чаще всего стоимость A JOIN B не равна стоимости B JOIN A.
Предположим, что внешняя зависимость содержит N элементов, а внутренняя - М. Как вы помните, оптимизатору известны эти значения благодаря статистике. N и M являются кардинальными числами зависимостей .
- Объединение с помощью вложенных циклов.
Это простейший способ объединения.
Работает он так: для каждой строки внешней зависимости ищутся совпадения по всем строкам внутренней зависимости.
Пример псеводокода:
Nested_loop_join(array outer, array inner) for each row a in outer for each row b in inner if (match_join_condition(a,b)) write_result_in_output(a,b) end if end for end for
Поскольку здесь двойная итерация, временнáя сложность определяется как О(N*M).Для каждой из N строк внешней зависимости нужно считать М строк внешней зависимости. То есть этот алгоритм требует N + N*M чтений с диска. Если внутренняя зависимость достаточно мала, то можно поместить её целиком в память, и тогда на долю дисковой подсистемы придётся только M + N чтений. Так что рекомендуется делать внутреннюю зависимость как можно компактнее, чтобы загнать в память.
С точки зрения временнόй сложности разницы никакой.
Также можно заменить внутреннюю зависимость индексом, это позволит сэкономить операции ввода/вывода.
Если внутренняя зависимость не влезает в память целиком, можно использовать другой алгоритм, более экономно использующий диск.- Вместо чтения обеих зависимостей построчно, они считываются группами строк (bunch), при этом в памяти сохраняется по одной группе из каждой зависимости.
- Строки из этих групп сравниваются между собой, а найденные совпадения сохраняются отдельно.
- Затем в память подгружаются новые группы и тоже сравниваются друг с другом.
Пример алгоритма:
// improved version to reduce the disk I/O. nested_loop_join_v2(file outer, file inner) for each bunch ba in outer // ba is now in memory for each bunch bb in inner // bb is now in memory for each row a in ba for each row b in bb if (match_join_condition(a,b)) write_result_in_output(a,b) end if end for end for end for end for
В данном случае временнáя сложность остаётся той же, зато снижается количество обращений к диску: (количество групп внешней + количество групп внешней * количество групп внутренней). С увеличением размера групп ещё больше уменьшается количество обращений к диску.Примечание: в этом алгоритме при каждом обращении считывается больший объём данных, но это не играет роли, поскольку обращения последовательные.
- Хэш-объединение.
Это более сложная операция, но во многих случаях её стоимость ниже.
Алгоритм следующий:
- Считываются все элементы из внутренней зависимости.
- В памяти создаётся хэш-таблица.
- Один за другим считываются все элементы из внешней зависимости.
- Для каждого элемента вычисляется хэш (с помощью соответствующей функции из хэш-таблицы), чтобы можно было найти соответствующий блок во внутренней зависимости.
- Элементы из блока сравниваются с элементами из внешней зависимости.
- Внутренняя зависимость содержит Х блоков.
- Хэш-функция распределяет хэши почти одинаково для обеих зависимостей. То есть все блоки имеют идентичный размер.
- Стоимость поиска соответствия между элементами внешней зависимости и всеми элементами внутри блока равна количеству элементов внутри блока.
(М / Х) * (N / X) + стоимость_создания_хэш-таблицы(М) + стоимость_хэш-функции * N
А если хэш-функция создаёт достаточное маленькие блоки, то временнáя сложность будет равна О(М + N).
Есть ещё один способ хэш-объединения, более экономно расходующий память и не требующий больше операций ввода/вывода:
- Вычисляются хэш-таблицы для обеих зависимостей.
- Кладутся на диск.
- А затем сравниваются поведёрно друг с другом (один блок загружается в память, а второй считывается построчно).
Операцию объединения можно разделить на два этапа:
- (Опционально) сначала осуществляется объединение сортировкой, когда оба набора входных данных сортируются по ключам объединения.
- Затем осуществляется слияние.
Алгоритм сортировки слиянием уже обсуждался выше, в данном случае он вполне себя оправдывает, если вам важно экономить память.
Но бывает, что наборы данных поступают уже отсортированными, например:
- Если таблица организована нативно.
- Если зависимость является индексом при наличии условия объединения.
- Если объединение происходит с промежуточным отсортированным результатом.
Эта операция очень похожа на операцию слияния при процедуре сортировки слиянием. Но вместо выбора всех элементов обеих зависимостей мы выбираем только равные элементы.
- Сравниваются два текущих элемента обеих зависимостей.
- Если они равны, то заносятся в результирующую таблицу, и далее сравниваются два следующих элемента, по одному из каждой зависимости.
- Если они не равны, то сравнение повторяется, но вместо наименьшего из двух элементов берётся следующий элемент из той же зависимости, поскольку вероятность совпадения в этом случае выше.
- Шаги 1-3 повторяются, пока на закончатся элементы одной из зависимостей.
Если обе зависимости ещё нужно отсортировать, то временнáя сложность равна O(N * Log(N) + M * Log(M)).
Этот алгоритм работает хорошо, потому что обе зависимости уже отсортированы, и нам не приходится перемещаться по ним туда-обратно. Однако здесь допущено некоторое упрощение: алгоритм не обрабатывает ситуации, когда одни и те же данные встречаются многократно, то есть когда происходят многократные совпадения. В реальности используется более сложная версия алгоритма. Например:
MergeJoin(relation a, relation b) relation output integer a_key:=0; integer b_key:=0; while (a!=null and b!=null) if (a < b) a_key++; else if (a > b) b_key++; else //Join predicate satisfied write_result_in_output(a,b) //We need to be careful when we increase the pointers integer a_key_temp:=a_key; integer b_key_temp:=b_key; if (a != b) b_key_temp:= b_key + 1; end if if (b != a) a_key_temp:= a_key + 1; end if if (b == a && b == a) a_key_temp:= a_key + 1; b_key_temp:= b_key + 1; end if a_key:= a_key_temp; b_key:= b_key_temp; end if end while
Если бы существовал самый лучший способ объединения, то не существовало бы всех этих разновидностей. Так что ответ на этот вопрос зависит от кучи факторов:
- Объём доступной памяти . Если её мало, забудьте о мощном хэш-объединении. По крайне мере, о его выполнении целиком в памяти.
- Размер двух наборов входных данных. Если у вас одна таблица большая, а вторая очень маленькая, то быстрее всего сработает объединение с помощью вложенных циклов, потому что хэш-объединение подразумевает дорогую процедуру создания хэшей. Если у вас две очень большие таблицы, то объединение с помощью вложенных циклов поглотит все ресурсы процессора.
- Наличие индексов. Если у вас два индекса В-деревьев, то лучше использовать объединение слиянием.
- Нужно ли сортировать результат. Возможно, вы захотите использовать дорогое объединение слиянием (с сортировкой), если работаете с несортированными наборами данных. Тогда на выходе вы получите сортированные данные, которые удобнее объединить с результатами другого объединения. Или потому что запрос косвенно или явно предполагает получение данных, отсортированных операторами ORDER BY/GROUP BY/DISTINCT.
- Отсортированы ли выходные зависимости . В данном случае лучше использовать объединение слиянием.
- Зависимости каких типов вы используете . Объединение по эквивалентности (таблицаА.колонка1 = таблицаБ.колонка2)? Внутренние зависимости, внешние, декартово произведение или самообъединение (self-join)? В разных ситуациях некоторые способы объединения не работают.
- Распределение данных . Если данные отклонены по условию объединения (например, вы объединяете людей по фамилиям, но часто встречаются однофамильцы), то ни в коем случае нельзя использовать хэш-объединение. Иначе хэш-функция будет создавать корзины с очень плохим внутренним распределением.
- Нужно ли выполнять объединение в несколько процессов/потоков.
4.4.4. Упрощённые примеры
Допустим, нам нужно объединить пять таблиц, чтобы получить полное представление о неких людях. Каждый человек может иметь:
- Несколько номеров мобильных телефонов.
- Несколько адресов электронной почты.
- Несколько физических адресов.
- Несколько номеров банковских счетов.
SELECT * from PERSON, MOBILES, MAILS,ADRESSES, BANK_ACCOUNTS
WHERE
PERSON.PERSON_ID = MOBILES.PERSON_ID
AND PERSON.PERSON_ID = MAILS.PERSON_ID
AND PERSON.PERSON_ID = ADRESSES.PERSON_ID
AND PERSON.PERSON_ID = BANK_ACCOUNTS.PERSON_ID
Оптимизатору нужно найти наилучший способ обработки данных. Но есть две проблемы:
- Какой способ объединения использовать? Есть три варианта (хэш-объединение, объединение слиянием, объединение с помощью вложенных циклов), с возможностью использования 0, 1 или 2 индексов. Не говоря уже о том, что индексы тоже могут быть разными.
- В каком порядке нужно производить объединение?
Исходя из описанного, какие есть варианты действий?
- Использовать брутфорс-подход. С помощью статистики подсчитать стоимость каждого из возможных планов исполнения запроса и выбрать самый дешёвый. Но вариантов довольно много. Для каждого порядка объединения можно использовать три разных способа объединения, итого 34=81 возможных планов исполнения. В случае с бинарным деревом задача выбора порядка объединения превращается в задачу о перестановках, и количество вариантов равно (2 * 4)! / (4 + 1)!.. В результате, в данном очень упрощённом примере общее количество возможных планов исполнения запроса составляет 34 * (2 * 4)! / (4 + 1)! = 27 216. Если добавить к этому варианты, когда при объединении слиянием используется 0, 1 или 2 индекса В-дерева, то количество возможных планов повышается до 210 000. Мы уже упоминали, что это ОЧЕНЬ ПРОСТОЙ запрос?
- Поплакать и уволиться. Очень соблазнительно, но непродуктивно, да и деньги нужны.
- Попробовать несколько планов и выбрать самый дешёвый. Раз обсчитать стоимость всех возможных вариантов не получается, можно взять произвольный тестовый набор данных и прогнать по нему все виды планов, чтобы оценить их стоимость и выбрать лучший.
- Применить «умные» правила для уменьшения количества возможных планов.
Есть два типа правил:- «Логические», с помощью которых можно исключить бесполезные варианты. Но они далеко не всегда применимы. Например, «при объединении с помощью вложенных циклов внутренняя зависимость должна являться наименьшим набором данных».
- Можно не искать наиболее выгодное решение и применить более жёсткие правила для уменьшения числа возможных планов. Скажем, «если зависимость мала, используем объединение с помощью вложенных циклов, но никогда - объединение слиянием или хэш-объединение».
Так как же БД делает выбор?
4.4.5. Динамическое программирование, «жадный» алгоритм и эвристика
Реляционная БД использует разные подходы, о которых было сказано выше. И задачей оптимизатора является поиск подходящего решения в течение ограниченного времени. В большинстве случаев оптимизатор ищет не наилучшее, а просто хорошее решение.
Брутфорс может подойти в случае с маленькими запросами. А благодаря способам исключения ненужных вычислений даже для запросов среднего размера можно использовать грубую мужскую силу. Это называется динамическим программированием.
Его суть заключается в том, что многие планы исполнения очень похожи.
На этой иллюстрации все четыре плана используют поддерево A JOIN B. Вместо вычисления его стоимости для каждого плана, мы можем посчитать его лишь раз и затем использовать эти данные столько, сколько нужно. Иными словами, с помощью мемоизации мы решаем проблему перекрытия, то есть избегаем лишних вычислений.
Благодаря такому подходу вместо временнόй сложности (2*N)!/(N+1)! мы получаем «всего лишь» 3 N . Применительно к предыдущему примеру с четырьмя объединениями это означает уменьшение количества вариантов с 336 до 81. Если взять запрос с 8 объединениями (небольшой запрос), то уменьшение сложности будет с 57 657 600 до 6 561.
Если вы уже знакомы с динамическим программированием или алгоритмизацией, можете поиграться с этим алгоритмом:
Procedure findbestplan(S)
if (bestplan[S].cost infinite)
return bestplan[S]
// else bestplan[S] has not been computed earlier, compute it now
if (S contains only 1 relation)
set bestplan[S].plan and bestplan[S].cost based on the best way
of accessing S /* Using selections on S and indices on S */
else for each non-empty subset S1 of S such that S1 != S
P1= findbestplan(S1)
P2= findbestplan(S - S1)
A = best algorithm for joining results of P1 and P2
cost = P1.cost + P2.cost + cost of A
if cost < bestplan[S].cost
bestplan[S].cost = cost
bestplan[S].plan = “execute P1.plan; execute P2.plan;
join results of P1 and P2 using A”
return bestplan[S]
Динамическое программирование можно использовать и для более крупных запросов, но придётся вводить дополнительные правила (эвристику), чтобы уменьшить число возможных планов:
Жадные алгоритмы
Но если запрос очень велик, или если нам нужно крайне быстро получить ответ, используется другой класс алгоритмов - жадные алгоритмы.
В данном случае план исполнения запроса строится пошагово с помощью некоего правила (эвристики). Благодаря ему жадный алгоритм ищет наилучшее решение для каждого этапа по отдельности. План начинается с оператор JOIN, а затем на каждом этапе добавляется новый JOIN в соответствии с правилом.
Рассмотрим простой пример. Возьмём запрос с 4 объединениями 5 таблиц (A, B, C, D и E). Несколько упростим задачу и представим, что единственным вариантом является объединение с помощью вложенных алгоритмов. Будем использовать правило «применять объединение с наименьшей стоимостью».
- Начинаем с одной из таблиц, например, А.
- Вычисляем стоимость каждого объединения с А (она будет как в роли внешней, так и внутренней зависимости).
- Находим, что дешевле всего нам обойдётся A JOIN B.
- Затем вычисляем стоимость каждого объединения с результатом A JOIN B (его тоже рассматриваем в двух ролях).
- Находим, что выгоднее всего будет (A JOIN B) JOIN C.
- Опять делаем оценку возможных вариантов.
- В конце получаем такой план исполнения запроса: (((A JOIN B) JOIN C) JOIN D) JOIN E)/
Данный алгоритм называется «алгоритм ближайшего соседа ».
Не будем углубляться в подробности, но при хорошем моделировании сложности сортировки N*log(N) данная проблема может быть . Временнáя сложность алгоритма равна О(N*log(N)) вместо О(3 N) для полной версии с динамическим программированием. Если у вас большой запрос с 20 объединениями, то это будет 26 против 3 486 784 401. Большая разница, верно?
Но есть нюанс. Мы предполагаем, что если найдём наилучший способ объединения двух таблиц, то получим самую низкую стоимость при объединении результатом предыдущих объединений со следующими таблицами. Однако даже если A JOIN B будет самым дешёвым вариантом, то (A JOIN C) JOIN B может иметь стоимость ниже, чем (A JOIN B) JOIN C.
Так что если вам позарез нужно найти самый дешёвый план всех времён и народов, то можно посоветовать многократно прогонять жадные алгоритмы с использованием разных правил.
Другие алгоритмы
Если вы уже сыты по горло всеми этими алгоритмами, то можете пропустить эту главу. Она не обязательна для усвоения всего остального материала.
Многие исследователи занимаются проблемой поиска наилучшего плана исполнения запроса. Зачастую пытаются найти решения для каких-то конкретных задач и шаблонов. Например, для звездообразных объединений, исполнения параллельных запросов и т.д.
Ищутся варианты замены динамического программирования для исполнения больших запросов. Те же жадные алгоритмы являются подмножеством эвристических алгоритмов. Они действуют сообразно правилу, запоминают результат одного этапа и используют его для поиска лучшего варианта для следующего этапа. И алгоритмы, которые не всегда используют решение, найденное для предыдущего этапа, называются эвристическими.
В качестве примера можно привести генетические алгоритмы:
- Каждое решение представляет собой план полного исполнения запроса.
- Вместо одного решения (плана) алгоритм на каждом этапе формирует Х решений.
- Сначала создаётся Х планов, делается это случайным образом.
- Из них сохраняются только те планы, чья стоимости удовлетворяет некоему критерию.
- Затем эти планы смешиваются, что бы создать Х новых планов.
- Некоторые из новых планов модифицируются случайным образом.
- Предыдущие три шага повторяются Y раз.
- Из планов последнего цикла мы получаем наилучший.
Кстати, генетические алгоритмы интегрированы в PostgreSQL .
В БД используются и такие эвристические алгоритмы, как симулированная нормализация (Simulated Annealing), итеративное улучшение (Iterative Improvement), двухфазная оптимизация (Two-Phase Optimization). Но не факт, что они применяются в корпоративных системах, возможно, их удел - исследовательские продукты.
4.4.6. Настоящие оптимизаторы
Тоже необязательная глава, можно и пропустить.
Давайте отойдём от теоретизирования и рассмотрим реальные примеры. Например, как работает оптимизатор SQLite . Это «лёгкая» БД, использующая простую оптимизацию на основе жадного алгоритма с дополнительными правилами:
- SQLite никогда не меняет порядок таблиц в операции CROSS JOIN.
- Используется объединение с помощью вложенных циклов.
- Внешние объединения всегда оцениваются в том порядке, в котором они осуществлялись.
- Вплоть до версии 3.8.0 для поиска наилучшего плана исполнения запроса используется жадный алгоритм «ближайшего соседа» (Nearest Neighor). А с версии 3.8.0 применяется «N ближайших соседей » (N3, N Nearest Neighbors).
- Жадные алгоритмы:
- 0 - минимальная оптимизация. Используется сканирование индекса, объединение с помощью вложенных циклов и исключение перезаписи некоторых запросов.
- 1 - низкая оптимизация
- 2 - полная оптимизация
- Динамическое программирование:
- 3 - средняя оптимизация и грубая аппроксимация
- 5 - полная оптимизация, используются все эвристические методики
- 7 - то же самое, но без эвристики
- 9 - максимальная оптимизация любой ценой, без оглядки на затрачиваемые усилия. Оцениваются все возможные способы объединения, включая декартовы произведения.
- Сбор всей возможной статистики, включая частотные распределения и квантили.
- Применение всех правил перезаписи запросов, включая составление табличного маршрута для материализованных запросов). Исключение составляют правила, требующие интенсивных вычислений, применяемые для очень ограниченного числа случаев.
- При переборе вариантов объединения с помощью динамического программирования:
- Ограниченно используется составная внутренняя зависимость.
- Для звездообразных схем с таблицами преобразования ограниченно используются декартовы произведения.
- Рассматривается широкий диапазон способов доступа, включая предварительную выборку списка (об этом ниже), специальную операцию с индексами AND и составление табличного маршрута для материализованных запросов.
Прочие условия (GROUP BY, DISTINCT и т.д.) обрабатываются простыми правилами.
4.4.7. Кэш плана запросов
Поскольку составление плана требует времени, большинство БД хранят план в кэше плана запросов. Это помогает избежать ненужных вычислений одних и тех же этапов. БД должна знать, когда именно ей нужно обновить устаревшие планы. Для этого устанавливается некий порог, и если изменения в статистике его превышают, то план, относящийся к данной таблице, удаляется из кэша.
Исполнитель запросов
На данном этапе наш план уже оптимизирован. Он перекомпилируется в исполняемый код и, если ресурсов достаточно, исполняется. Операторы, содержащиеся в плане (JOIN, SORT BY и т.д.) могут обрабатываться как последовательно, так и параллельно, решение принимает исполнитель. Для получения и записи данных он взаимодействует с диспетчером данных.5. Диспетчер данных
Диспетчер запросов исполняет запрос и нуждается в данных из таблиц и индексов. Он запрашивает их у диспетчера данных, но тут есть две трудности:
- Реляционные БД используют транзакционную модель. Нельзя в конкретный момент времени получить любые желаемые данные, потому что в это время они могут кем-то использоваться/модифицироваться.
- Извлечение данных - самая медленная операция в БД. Поэтому диспетчеру данных нужно уметь прогнозировать свою работу, чтобы своевременно заполнять буфер памяти.
5.1. Диспетчер кэша
Как уже не раз говорилось, самым узким местом в БД является дисковая подсистема. Поэтому для увеличения производительности используется диспетчер кэша.
Вместо того, чтобы получать данные напрямую от файловой системы, исполнитель запросов обращается за ними к диспетчеру кэша. Тот использует содержащийся в памяти буферный пул, что позволяет радикально увеличить производительность БД. В цифрах это трудно оценить, поскольку многое зависит от того, что вам нужно:
- Последовательный доступ (полное сканирование) или случайный (доступ по ID строки).
- Читать или записывать.
Однако тут мы сталкиваемся с другой проблемой. Диспетчеру кэша нужно положить данные в память ДО того, как они понадобятся исполнителю запросов. Иначе тому придётся ждать их получения с медленного диска.
5.1.1. Упреждение
Исполнитель запросов знает, какие данные ему понадобятся, поскольку ему известен весь план, то, какие данные содержатся на диске и статистика.
Когда исполнитель обрабатывает первую порцию данных, он просит диспетчер кэша заранее подгрузить следующую порцию. А когда переходит к её обработке, то просит ДК подгрузить третью и подтверждает, что первую порцию можно удалить из кэша.
Диспетчер кэша хранит эти данные в буферном пуле. Он также добавляет к ним сервисную информацию (триггер, latch), чтобы знать нужны ли они ещё в буфере.
Иногда исполнитель не знает, какие данные ему будут нужны, или некоторые БД не имеют подобного функционала. Тогда используется спекулятивное упреждение (speculative prefetching) (например, если исполнитель запрашивает данные 1, 3, 5, то наверняка запросит в будущем 7, 9, 11) или последовательное упреждение (sequential prefetching) (в данном случае ДК просто подгружает с диска следующую по порядку порцию данных.
Нельзя забывать, что буфер ограничен объёмом доступной памяти. То есть для загрузки одних данных нам приходится периодически удалять другие. Заполнение и очистка кэша потребляет часть ресурсов дисковой подсистемы и сети. Если у вас есть часто исполняемый запрос, то было бы контрпродуктивно каждый раз загружать и очищать используемые им данные. Для решения данной проблемы в современных БД используется стратегия замены буфера.
5.1.2. Стратегии замены буфера
Большинство БД (по крайне мере, SQL Server, MySQL, Oracle и DB2) используют для этого алгоритм LRU (Least Recently Used). Он предназначен для поддержания в кэше тех данных, которые недавно использовались, а значит велика вероятность, что они могут понадобиться снова.
Для облегчения понимания работы алгоритма примем, что данные в буфере не блокируются триггерами (latch), а значит могут быть удалены. В нашем примере буфер может хранить три порции данных:
- Диспетчер кэша используется данные 1 и кладёт их в пустой буфер.
- Затем он использует данные 4 и тоже отправляет их в буфер.
- То же самое делается и с данными 3.
- Далее берутся данные 9. Но буфер-то уже заполнен. Поэтому из него удаляются данные 1, так как они не использовались дольше всего. После этого в буфер помещаются данные 9.
- Диспетчер кэша снова использует данные 4. Они уже есть в буфере, поэтому помечаются как последние использованные.
- Снова становятся востребованы данные 1. Чтобы их поместить в буфер, из него удаляются данные 3, как не использовавшиеся дольше всего.
Улучшения алгоритма
Чтобы этого не произошло, в некоторых БД используются специальные правила. Согласно документации Oracle :
«Для очень больших таблиц обычно используется прямой доступ, то есть блоки данных считываются напрямую, чтобы избежать переполнения буфера кэша. Для таблиц среднего размера может использоваться как прямой доступ, так и чтение из кэша. Если система решит использовать кэш, то БД помещает блоки данных в конец списка LRU, чтобы предотвратить очистку буфера».
Также используется улучшенная версия LRU - LRU-K. В SQL Server применяется LRU-K при К = 2. Суть этого алгоритма в том, что при оценке ситуации он учитывает больше информации о прошлых операциях, а не только запоминает последние использованные данные. Буква К в названии означает, что алгоритм принимает во внимание, какие данные использовались последние К раз. Им присваивается определённый вес. Когда в кэш загружаются новые данные, то старые, но часто используемые не удаляются, потому что их вес выше. Конечно, если данные больше не используются, то они всё-таки будут удалены. И чем дольше данные остаются невостребованными, тем сильнее уменьшается со временем их вес.
Вычисление веса довольно накладно, поэтому в SQL Server используется LRU-K при К равном всего лишь 2. При некотором увеличении значения К эффективность алгоритма улучшается. Вы можете ближе познакомиться с ним благодаря .
Другие алгоритмы
Конечно, LRU-K не единственное решение. Существуют также 2Q и CLOCK (оба похожи на LRU-K), MRU (Most Recently Used, в котором используется логика LRU, но применяется другое правило, LRFU (Least Recently and Frequently Used) и т.д. В некоторых БД можно выбирать, какой алгоритм будет использоваться.
5.1.3. Буфер записи
Мы говорили только о буфере чтения, но БД используют и буферы записи, которые накапливают данные и сбрасывают на диск порциями, вместо последовательной записи. Это позволяет экономить операции ввода/вывода.
Помните, что буферы хранят страницы
(неделимые единицы данных), а не ряды из таблиц. Страница в буферном пуле называется «грязной», если она модифицирована, но не записана на диск. Есть много разных алгоритмов, с помощью которых выбирается время записи грязных страниц. Но это во многом связано с понятием транзакций.
5.2. Диспетчер транзакций
В его обязанности входит отслеживание, чтобы каждый запрос исполнялся с помощью собственной транзакции. Но прежде чем поговорить о диспетчере, давайте проясним концепцию ACID-транзакций.5.2.1. «Под кислотой» (игра слов, если кто не понял)
ACID-транзакция (Atomicity, Isolation, Durability, Consistency) - это элементарная операция, единица работы, которая удовлетворяет 4 условиям:
- Атомарность (Atomicity). Нет ничего «меньше» транзакции, никакой более мелкой операции. Даже если транзакция длится 10 часов. В случае неудачного выполнения транзакции система возвращается в состояние «до», то есть транзакция откатывается.
- Изолированность (Isolation) . Если в одно время выполняются две транзакции А и В, то их результат не должен зависеть от того, завершилась ли одна из них до, во время или после исполнения другой.
- Надёжность (Durability). Когда транзакция зафиксирована (commited), то есть успешно завершена, использовавшиеся ею данные остаются в БД вне зависимости от возможных происшествий (ошибки, падения).
- Консистентность (согласованность) (Consistency). В БД записываются только валидные данные (с точки зрения реляционных и функциональных связей). Консистентность зависит от атомарности и изолированности.
Во время выполнения какой-либо транзакции можно исполнять различные SQL-запросы на чтение, создание, обновление и удаление данных. Проблемы начинаются, когда две транзакции используют одни и те же данные. Классический пример - перевод денег со счёта А на счёт Б. Допустим, у нас есть две транзакции:
- Т1 берёт $100 со счёта А и отправляет их на счёт Б.
- Т2 берёт $50 со счёта А и тоже отправляет их на счёт Б.
- Атомарность позволяет быть уверенным, что какое бы событие не произошло в ходе Т1 (падение сервера, сбой сети), не может случиться так, что $100 будут списаны с А, но не придут на Б (в противном случае говорят о «несогласованном состоянии»).
- Изолированность говорит о том, что даже если Т1 и Т2 осуществляются одновременно, в результате с А будет списано $100 и та же сумма поступит на Б. Во всех остальных случаях опять говорят о несогласованном состоянии.
- Надёжность позволяет не беспокоиться о том, что Т1 исчезнет, если база упадёт сразу после коммита Т1.
- Консистентность предотвращает возможность создания денег или их уничтожения в системе.
Многие БД не обеспечивают полную изолированность по умолчанию, поскольку это приводит к огромным издержкам в производительности. В SQL используется 4 уровня изолированности:
- Сериализуемые транзакции (Serializable). Наивысший уровень изолированности. По умолчанию используется в SQLite. Каждая транзакция исполняется в собственной, полностью изолированной среде.
- Повторяемое чтение (Repeatable read).
По умолчанию используется в MySQL. Каждая транзакция имеет свою среду, за исключением одной ситуации: если транзакция добавляет новые данные
и успешно завершается, то они будут видимы для других, всё ещё выполняющихся транзакций. Но если транзакция модифицирует данные
и успешно завершается, то эти изменения будут не видны для всё ещё выполняющихся транзакций. То есть для новых данных принцип изолированности нарушается.
Например, транзакция А выполняет
SELECT count(1) from TABLE_X
Потом транзакция Б добавляет в таблицу Х и коммитит новые данные. И если после этого транзакция А снова выполняет count(1), то результат будет уже другим.Это называется фантомным чтением.
- Чтение зафиксированных данных (Read commited)
. По умолчанию используется в Oracle, PostgreSQL и SQL Server. Это то же самое, что и повторяемое чтение, но с дополнительным нарушением изолированности. Допустим, транзакция А читает данные; затем они модифицируются или удаляются транзакцией Б, которая коммитит эти действия. Если А снова считает эти данные, то она увидит изменения (или факт удаления), сделанные Б.
Это называется неповторяемым чтением (non-repeatable read).
- Чтение незафиксированных данных (Read uncommited).
Самый низкий уровень изолированности. К чтению зафиксированных данных добавляется новое нарушение изолированности. Допустим, транзакция А читает данные; затем они модифицируются транзакцией Б (изменения не коммитятся, Б всё ещё выполняется). Если А считает данные снова, то увидит сделанные изменения. Если же Б будет откачена назад, то при повторном чтении А не увидит изменений, словно ничего и не было.
Это называется грязным чтением.
Большинство БД добавляют собственные уровни изолированности (например, на основе снэпшотов, как в PostgreSQL, Oracle и SQL Server). Также во многих БД не реализованы все четыре вышеописанных уровня, особенно чтение незафиксированных данных.
Пользователь или разработчик может сразу же после установления соединения переопределить уровень изолированности по умолчанию. Для этого достаточно добавить очень простую строчку кода.
5.2.2. Управление параллелизмом
Главное, для чего нам нужны изолированность, согласованность и атомарность, это возможность осуществлять операции записи над одними и теми же данными (добавлять, обновлять и удалять).
Если все транзакции будут только читать данные, то смогут работать одновременно, не влияя на другие транзакции.
Если хотя бы одна транзакция изменяет данные, читаемые другими транзакциями, то БД нужно найти способ скрыть от них эти изменения. Также нужно удостовериться, что сделанные изменения не будут удалены другими транзакциями, которые не видят изменённых данных.
Это называется управлением параллелизмом.
Проще всего просто выполнять транзакции поочерёдно. Но такой подход обычно неэффективен (задействуется лишь одно ядро одного процессора), и к тому же теряется возможность масштабирования.
Идеальный способ решения проблемы выглядит так (при каждом создании или отмене транзакции):
- Мониторить все операции каждой транзакции.
- Если две и более транзакции конфликтуют из-за чтения/изменения одних и тех же данных, то менять очерёдность операций внутри участников конфликта, чтобы свести к минимуму количество причин.
- Выполнять конфликтующие части транзакций в определённом порядке. Неконфликтующие транзакции в это время выполняются параллельно.
- Иметь в виду, что транзакции могут быть отменены.
5.2.3. Диспетчер блокировок
Для решения вышеописанной проблемы во многих БД используются блокировки (locks) и/или версионность данных.
Если транзакции нужны какие-то данные, то она блокирует их. Если другой транзакции они тоже потребовались, то её придётся ждать, пока первая транзакция не снимет блокировку.
Это называется эксклюзивной блокировкой.
Но слишком расточительно использовать эксклюзивные блокировки в случаях, когда транзакциям нужно всего лишь считать данные. Зачем мешать чтению данных? В таких случаях используются совместные блокировки. Если транзакции нужно считать данные, они применяет к ним совместную блокировку и читает. Это не мешает другим транзакциям тоже применять совместные блокировки и читать данные. Если же какой-то из них нужно изменить данные, то ей придётся подождать, пока все совместные блокировки не будут сняты. Только после этого она сможет применить эксклюзивную блокировку. И тогда уже всем остальным транзакциям придётся ждать её снятия, чтобы считывать эти данные.
Диспетчер блокировок - это процесс, который применяет и снимает блокировки. Они хранятся в хэш-таблице (ключами являются блокируемые данные). Диспетчер знает для всех данных, какие транзакции применили блокировки или ждут их снятия.
Взаимная блокировка (deadlock)
Использование блокировок может привести к ситуации, когда две транзакции бесконечно ожидают снятия блокировок:
Здесь транзакция А эксклюзивно заблокировала данные 1 и ожидает освобождения данных 2. В то же время транзакция Б эксклюзивно заблокировала данные 2 и ожидает освобождения данных 1.
При взаимной блокировке диспетчер выбирает, какую транзакцию отменить (откатить назад). И решение принять не так просто:
- Будет ли лучше убить транзакцию, которая изменила последний набор данных (а значит, откат будет наименее болезненным)?
- Будет ли лучше убить самую молодую транзакцию, поскольку пользователи других транзакций прождали дольше?
- Будет ли лучше убить транзакцию, которой требуется меньше времени для завершения?
- На сколько других транзакций повлияет откат?
Представим хэш-таблицу в виде диаграммы, как на иллюстрации выше. Если на диаграмме присутствует циклическая связь, то взаимная блокировка подтверждена. Но поскольку проверять на наличие циклов достаточно дорого (ведь диаграмма, на которой отражены все блокировки, будет весьма большой), зачастую используется более простой подход: использование таймаутов. Если блокировка не снимается в течение определённого времени, значит транзакция вошла в состояние взаимной блокировки.
Перед наложением блокировки диспетчер также может проверить, не приведёт ли это к возникновению взаимной блокировки. Но чтобы однозначно на это ответить, тоже придётся потратиться на вычисления. Поэтому подобные предпроверки зачастую представлены в виде набора базовых правил.
Двухфазная блокировка
Проще всего полная изолированность обеспечивается, когда блокировка применяется в начале и снимается в конце транзакции. Это означает, что транзакции перед началом приходится дожидаться снятия всех блокировок, а применённые ею блокировки снимаются лишь по завершении. Такой подход можно применять, но тогда теряется куча времени на все эти ожидания снятия блокировок.
В DB2 и SQL Server применяется протокол двухфазной блокировки, при котором транзакция делится на две фазы:
- Фазу подъёма (growing phase) , когда транзакция может только применять блокировки, но не снимать их.
- Фазу спада (shrinking phase) , когда транзакция может только снимать блокировки (с данных, которые уже обработаны и не будут обрабатываться снова), но не применять новые.
До транзакции А X = 1 и Y = 1. Она обрабатывает данные Y = 1, которые были изменены транзакцией В уже после начала транзакции А. В связи с принципом изолированности транзакция А должна обрабатывать Y = 2.
Цели, решаемые с помощью этих двух простых правил:
- Снимать блокировки, которые больше не нужны, чтобы уменьшить время ожидания других транзакций.
- Предотвращать случаи, когда транзакция получают данные, модифицированные ранее запущенной транзакцией. Такие данные не совпадают с запрашиваемыми.
Конечно, реальные БД используют более сложные системы, больше видов блокировок и с большей гранулярностью (блокировки строк, страниц, партиций, таблиц, табличных пространств), но суть та же.
Версионность данных
Ещё один способ решения проблемы конфликта транзакций - использование версионности данных.
- Все транзакции могут модифицировать одни и те же данные в одно и то же время.
- Каждая транзакция работает с собственной копией (версией) данных.
- Если две транзакции изменяют одни и те же данные, то принимается только одна из модификаций, другая будет отклонена, а сделавшая её транзакция будет откачена (и, может быть, перезапущена).
- Читающие транзакции не блокируют записывающие, и наоборот.
- Неповоротливый диспетчер блокировок не оказывает влияния.
Оба подхода - блокировки и версионность - имеют плюсы и минусы, многое зависит от того, в какой ситуации они применяются (больше чтений или больше записей). Можете изучить очень хорошую презентацию , посвящённую реализации мультиверсионного управления параллелизмом в PostgreSQL.
В некоторых БД (DB2 до версии 9.7, SQL Server) используются только блокировки. Другие, вроде PostgreSQL, MySQL и Oracle, используются комбинированные подходы.
Примечание: версионность оказывает интересное влияние на индексы. Иногда в уникальном индексе появляются дубликаты, индекс может содержаться больше записей, чем строк в таблице и т.д.
Если часть данных считывается при одном уровне изолированности, а потом он увеличивается, то вырастает количество блокировок, а значит теряется больше времени на ожидания транзакций. Поэтому большинство БД не используют по умолчанию максимальный уровень изолированности.
Как обычно, за более подробной информацией обращайтесь к документации: MySQL , PostgreSQL , Oracle .
5.2.4. Диспетчер логов
Как мы уже знаем, ради увеличения производительности БД хранит часть данных в буферной памяти. Но если сервер падает во время коммита транзакции, то находящиеся в памяти данные будут потеряны. А это нарушает принцип надёжности транзакций.
Конечно, можно всё писать на диск, но при падении вы останетесь с недописанными данными, а это уже нарушение принципа атомарности.
Любые изменения, записанные транзакцией, должны быть отменены или завершены.
Это делается двумя способами:
- Теневые копии/страницы. Каждая транзакция создаёт собственную копию БД (или её часть), и работает с этой копией. В случае ошибки копия удаляется. Если всё прошло успешно, то БД мгновенно переключается на данные из копии с помощью одной уловки на уровне файловой системы, а потом удаляет «старые» данные.
- Лог транзакции. Это специальное хранилище. Перед каждой записью на диск БД пишет информацию в лог транзакции. Так что в случае сбоя БД будет знать, как удалить или завершить незавершённую транзакцию.
В больших БД с многочисленными транзакциями теневые копии/страницы занимают невероятно много места в дисковой подсистеме. Поэтому в современных БД используется лог транзакции. Он должен размещаться в защищённом от сбоев хранилище.
Большинство продуктов (в частности, Oracle, SQL Server , DB2 , PostgreSQL , MySQL и SQLite) работают с логом транзакции через протокол WAL (Write-Ahead Logging). Данные протокол содержит три правила:
- Каждая модификация в БД должна сопровождаться записью в лог, и она должна вноситься ДО того, как данные будут записаны на диск.
- Записи в логе должны располагаться в соответствии с очерёдностью соответствующих событий.
- Когда транзакция коммитится, запись об этом должна вноситься в лог ДО момента успешного завершения транзакции.
За выполнением этих правил следит диспетчер логов. Логически он расположен между диспетчером кэша и диспетчером доступа к данным. Диспетчер логов регистрирует каждую операцию, выполняемую транзакциями, до момента записи на диск. Вроде верно?
НЕВЕРНО! После всего, через что мы с вами прошли в этой статье, пора бы уже запомнить, что всё связанное с БД подвергается проклятью «эффекта базы данных». Если серьёзно, то проблема в том, что нужно найти способ писать в лог, при этом сохраняя хорошую производительность. Ведь если лог транзакций работает медленно, то он тормозит все остальные процессы.
ARIES
В 1992 год исследователи из IBM создали расширенную версию WAL, которую назвали ARIES. В том или ином виде ARIES используется большинством современных БД. Если вы захотите поглубже изучить этот протокол, можете проштудировать соответствующую работу .
Итак, ARIES расшифровывается как A lgorithms for R ecovery and I solation E xploiting S emantics. У этой технологии две задачи:
- Обеспечить хорошую производительность при записи логов.
- Обеспечить быстрое и надёжное восстановление.
- Пользователь отменил её.
- Ошибка сервера или сети.
- Транзакция нарушила целостность БД. Например, вы применили к колонке условие UNIQUE, а транзакция добавила дубликат.
- Наличие взаимных блокировок.
Как это возможно? Чтобы ответить на это, нужно сначала разобраться с тем, какая информация сохраняется в логе.
Логи
Каждая операция (добавления/удаления/изменения) во время выполнения транзакции ведёт к появлению записи в логе. Запись содержит:
- LSN (Log Sequence Number) . Это уникальный номер, значение которого определяется хронологическим порядком. То есть если операция А произошла до операции Б, LSN для А будет меньше LSN для Б. В реальности способ генерирования LSN сложнее, поскольку он связан и со способом хранения лога.
- TransID. Идентификатор транзакции, осуществившей операцию.
- PageID . Место на диске, где находятся изменённые данные.
- PrevLSN . Ссылка на предыдущую запись в логе, созданную той же транзакцией.
- UNDO
. Способ отката операции.
Например, если была проведена операция обновления, то в UNDO записывается предыдущее значение/состояние изменённого элемента (физический UNDO) или обратная операция, позволяющая вернуться в предыдущее состояние (логический UNDO). В ARIES используется только логический, с физическим работать очень тяжело.
- REDO . Способ повтора операции.
Насколько известно, UNDO не используется только в PostgreSQL. Вместо этого используется сборщик мусора, убирающий старые версии данных. Это связано с реализацией версионности данных в этой СУБД.
Чтобы вам было легче представить состав записи в логе, вот визуальный упрощённый пример, в котором выполняется запрос UPDATE FROM PERSON SET AGE = 18;. Пусть он исполняется в транзакции номер 18:
Каждый лог имеет уникальный LSN. Связанные логи относятся к одной и той же транзакции, причём линкуются они в хронологическом порядке (последний лог списка относится к последней операции).
Буфер логов
Чтобы запись в лог не превратилась в узкое место системы, используется буфер логов.
Когда исполнитель запросов запрашивает модифицированные данные:
- Диспетчер кэша хранит их в буфере.
- Диспетчер логов хранит в собственном буфере соответствующий лог.
- Исполнитель запросов определяет, завершена ли операция, и, соответственно, можно ли запрашивать изменённые данные.
- Диспетчер логов сохраняет нужную информацию в лог транзакции. Момент внесения этой записи задаётся алгоритмом.
- Диспетчер кэша записывает изменения на диск. Момент осуществления записи также задаётся алгоритмом.
Политики STEAL и FORCE
Для увеличения производительности шаг номер 5 нужно делать после коммита, поскольку в случае сбоя всё ещё возможно восстановить транзакцию с помощью REDO. Это называется «политика NO-FORCE».
Но БД может выбрать и политику FORCE ради уменьшения нагрузки во время восстановления. Тогда шаг номер 5 выполняется до коммита.
Также БД выбирает, записывать ли данные на диск пошагово (политика STEAL) или, если диспетчер буфера должен дождаться коммита, записать всё разом (NO-STEAL). Выбор зависит от того, что вам нужно: быструю запись с долгим восстановлением или быстрое восстановление?
Как упомянутые политики влияют процесс восстановления:
- Для STEAL/NO-FORCE нужны UNDO и REDO. Производительность высочайшая, но более сложная структура логов и процессов восстановления (вроде ARES). Эту комбинацию политик использует большинство БД.
- Для STEAL/FORCE нужен только UNDO.
- Для NO-STEAL/NO-FORCE - только REDO.
- Для NO-STEAL/FORCE вообще ничего не нужно. Производительность в данном случае самая низкая, и требуется огромное количество памяти.
Итак, как нам можно использовать наши замечательные логи? Предположим, что новый сотрудник порушил БД (правило №1: всегда виноват новичок!). Вы её перезапускаете и начинается процесс восстановления.
ARIES восстанавливает в три этапа:
- Анализ . Считывается весь лог транзакции, чтобы можно было восстановить хронологию событий, произошедших в процессе падения базы. Это помогает определить, какую транзакцию нужно откатить. Откатываются все транзакции без приказа о коммите. Также система решает, какие данные должны были записаться на диск во время сбоя.
- Повтор
. Для обновления БД до состояния перед падением используется REDO. Его логи обрабатываются в хронологическом порядке. Для каждого лога считывается LSN страницы на диске, содержащей данные, которые нужно изменить.
Если LSN(страницы_на_диске)>=LSN(записи_в_логе), то значит данные уже были записаны на диск перед сбоем. Но значение было перезаписано операцией, которая была выполнена после записи в лог и до сбоя. Так что ничего не сделано, на самом деле.
Если LSN(страницы_на_диске)
Повтор выполняется даже для транзакций, которые будут откачены, потому что это упрощает процесс восстановления. Но современные БД наверняка этого не делают.
- Отмена. На этом этапе откатываются все незавершённые на момент сбоя транзакции. Процесс начинается с последних логов каждой транзакции и обрабатывает UNDO в обратном хронологическом порядке с помощью PrevLSN.
Если транзакция отменена «вручную», или диспетчером блокировок, или из-за сбоя сети, то этап анализа не нужен. Ведь информация для REDO и UNDO содержится в двух таблицах, размещённых в памяти:
- В таблице транзакций (тут хранятся состояния всех текущих транзакций).
- В таблице грязных страниц (здесь содержится информация о том, какие данные нужно записать на диск).
Этап анализа нужен как раз для восстановления обеих таблиц с помощью информации из лога транзакций. Для ускорения этого этапа в ARIES используются контрольные точки. На диск время от времени записывается содержимое обеих таблиц, а также последний на момент записи LSN. Так что во время восстановления анализируются только логи, следующие после этого LSN.
6. Заключение
В качестве дополнительного обзорного чтива про базы данных можно порекомендовать статью Architecture of a Database System . Это хорошее введение в тему, написанное довольно понятным языком.Если вы внимательно прочитали весь вышеизложенный материал, то наверняка получили представление о том, насколько велики возможности баз данных. Однако в этой статье не затронуты другие важные проблемы:
- Как управлять кластеризованными БД и глобальными транзакциями.
- Как получить снэпшот, если база всё работает.
- Как эффективно хранить и сжимать данные.
- Как управлять памятью.
Итак, если вас кто-нибудь спросит, а как же работают базы данных, то вместо того, чтобы плюнуть и уйти, вы можете ответить:
Теги: Добавить метки
Загрузка...
