- •Основные функции субд:
- •По модели данных:
- •Иерархические (Иерархической базой данных является файловая система, состоящая из корневого каталога, в котором имеется иерархия подкаталогов и файлов).
- •Сетевые (Сетевые базы данных подобны иерархическим, за исключением того, что в них имеются указатели в обоих направлениях, которые соединяют родственную информацию).
- •По степени распределённости
- •Локальные субд (все части локальной субд размещаются на одном компьютере)
- •Распределённые субд (части субд могут размещаться на двух и более компьютерах).
- •Различные представления о данных в базах данных:
- •Ограничения не-Null Ограничение не-null просто говорит, что колонка не должна содержать значение null. Пример синтаксиса:
- •2. Определение структур базы данных (ddl)
- •3. Манипуляция данными (dml)
- •4. Отбор данных (dql)
- •5. Язык управления данными (dcl)
- •6. Команды администрирования данных
- •7. Команды управления транзакциями
- •14.Запись sql-операторов
- •15.Типы данных языка sql, определенные стандартом
- •16.Основные команды языка ddl
- •17.Основные команды языка dml
- •18.Оператор выбора select
- •19.Применение агрегатных функций и вложенных запросов в операторе выбора
- •20. Операторы манипулирования данными
- •21.Физическая организация бд: файлы, записи, блоки.
- •23.Организация файла бд в виде кучи. Эффективность таких файлов.
- •24.Хешированные файлы: бакет, каталог бакетов, дополнительный каталог бакетов, выбор хеш-функции. Операции над хешированными файлами.
- •25.Сравнение эффективности хешированных файлов и файлов, организованных в виде кучи. Причины снижения эффективности хешированных файлов.
- •26.Динамическое хеширование. Операции над динамически хешированными файлами.
- •27.Последовательная организация файлов. Операции добавления и удаления записей в последовательных файлах, блок переполнения.
- •28. Индексированные файлы: инициализация, поиск.
- •29. Индексированные файлы: операции вставки и удаления записей.
- •30.Разреженные и плотные индексы. Индексация по нескольким полям.
- •Составные индексы
- •31.Эффективность операций в индексированных файлах при различной организации поиска.
- •32.B-деревья: принципы построения, операция поиска.
- •33.В-деревья: операции добавления и удаления записей.
- •34.Эффективность организации файлов в виде в-дерева.
- •35.Технология кластеризации бд.
- •36.Технология сжатия информации в бд.
- •37.Основные шаги обработки запросов.
- •Можно транслировать в выражение
- •38.Статистика бд.
- •40.Алгоритмы выполнения селекции с одним условием сравнения: размер селекции, использование первичного индекса, использование вторичного индекса.
- •41.Размер комплексной селекции при конъюнкции и дизъюнкции условий.
- •43.Алгоритм внешней сортировки.
- •44.Размер операции соединения. Алгоритм соединения, основанный на двух вложенных циклах.
- •45.Алгоритмы выполнения соединения: поблочное соединение, усовершенствование алгоритма поблочного соединения, соединение по индексу.
- •46.Алгоритм соединения слиянием.
- •47.Алгоритмы выполнения операций с множествами, проекции, внешнего соединения.
- •48.Два подхода к вычислению выражений при обработке запросов.
- •50.Виды оптимизаторов: итеративный, основанный на стоимостях и эвристический.
- •51.Понятие транзакции. Свойства acid транзакций.
- •52.Аномалии параллельных транзакций: потерянное обновление, зависимость от нефиксированных результатов, несогласованная обработка.
- •53.Понятие плана параллельного выполнения транзакций. Последовательные, непоследовательные и неупорядоченные планы.
- •54.Конфликтное упорядочивание планов и упорядочивание планов по просмотру.
- •55.Блокировки как механизм управления параллельными транзакциями: понятие блокировки, хранение блокировок, виды блокировок.
- •56.Работа транзакций при использовании механизма блокировок. Предотвращение аномалий при использовании блокировок.
- •57.Понятие протокола. Двухфазный протокол.
- •58.Проблема каскадного отката в параллельных транзакциях. Строгий двухфазный протокол.
- •59.Взаимная блокировка параллельных транзакций.
- •60.Использование метода временных отметок для управления параллельными транзакциями.
- •61.Оптимистические технологии управления транзакциями.
- •63.Уровни изоляции параллельных транзакций.
- •64.Восстановление бд: возможные причины отказов, механизм резервного копирования, журнал транзакций, создание контрольных точек.
- •65.Методы восстановления бд: восстановление с резервной копии, метод «redo», метод теневых страниц.
- •66.Улучшенные модели транзакции: проблемы классических моделей транзакций, модель вложенных транзакций, модель хроник.
- •67.Технология raid. Уровни raid.
- •68.Oltp- технологии и хранилища данных. Хранилища данных.
- •Понятие хранилища данных.
- •Проблемы хранилищ данных.
- •Архитектура хранилища данных
- •Проектирование схемы бд для хранилища данных.
- •Olap-технологии.
50.Виды оптимизаторов: итеративный, основанный на стоимостях и эвристический.
Итеративный оптимизатор. Наиболее простой путь выбора плана заключается в выборе для каждой операции наиболее дешевого алгоритма выполнения. При этом можно также изменять порядок, в котором выполняются операции нижнего уровня до того как будет выполнена операция более высокого уровня.
Однако этот подход мало эффективен. Так как независимый выбор алгоритма для одной операции не гарантирует оптимального плана для всего запроса. Например, соединение смещением может оказаться дороже, чем соединение хешированием, но первый вариант сортирует отношение, что снижает стоимость выполнения операций более высокого уровня дерева. Простое соединение с использованием индекса может формировать результат для использования при конвейерной обработке, поэтому имеет смысл выбрать его, даже если другой алгоритм окажется дешевле. Поэтому необходимо рассматривать не только отдельные операции, но и алгоритмы вычисления запроса в целом.
Оптимизатор, основанный на стоимостях. Такой подход состоит в генерации множества планов согласно правилам эквивалентности, просчете для каждого стоимости и выборе плана с минимальной стоимостью. Для сложных запросов число построенных планов может быть огромно. Например, для выражения r1 >< r2 >< … >< rn можно построить (2(n-1))!/(n-1)! планов. (Число перестановок из n).
Эвристический оптимизатор. Этот подход предполагает использование эвристических правил для трансформации исходного плана выполнения запроса. Основное правило: выполнять селекцию и проекцию на самых ранних этапах, то есть смещать эти операции вниз по дереву плана. Это позволяет в последствии уменьшить входные отношения для других операций. Селекция выполняется раньше проекции, так как уменьшение числа кортежей играет более значительную роль, чем снижение числа атрибутов.
Преобразовать все конъюнкции селекции к последовательности селекций по правилу эквивалентности 1. Этот шаг перемещает селекцию вниз по дереву.
Перенести селекцию как можно ниже по дереву, используя правила эквивалентности 2, 7 и 11.
Проверить все операции селекции и соединения и переместить по дереву вниз те, которые накладывают более жесткие условия, а следовательно строят отношения с меньшим числом кортежей, используя ассоциативность операций. (то есть более жесткие спускаются, более мягкие поднимаются по дереву).
Заменить все операции декартова произведения операциями селекции и соединения по правилу 4а.
Раскрыть и перенести вниз по дереву проекции. Если необходимо создать новые проекции. (Правила 3, 8 и 12).
Установить какие поддеревья могут выполняться по конвейерной обработке.
51.Понятие транзакции. Свойства acid транзакций.
Транзакция – это действие или серия действий, выполняемых одним пользователем или прикладной программой, которые осуществляют доступ или изменение содержимого БД.
/*Возможно несколько действий, причем как изменяющих, так и читающих данные. */
Транзакция является логической единицей работы, выполняемой в БД. Она может быть представлена отдельной программой, являться частью алгоритма программы или даже отдельной командой (например,insert, update).
/*Например, изменение заработной платы сотруднику с некоторым табельным номером. Пользователь выполняет операцию
update сотрудник set з.п. = з.п.*1.1 where табельный номер = 23
Транзакция же будет состоять из чтения указанного элемента данных (поля з.п. некоторого кортежа), получения нового значения и записи указанного элемента, то есть из трех операций */
С точки зрения БД, выполнение программы некоторого приложения может расцениваться как серия транзакций, в промежутках между которыми выполняется некоторая обработка данных, осуществляемая вне среды БД.
Например, весь процесс пересмотра зарплаты сотрудникам организации. Выполняется транзакция, извлекающая список сотрудников с их зарплатой. После этого выполняется некоторая обработка данных по удобному представлению их пользователю, возможно он их будет переупорядочивать различным образом, увеличивать или уменьшать шрифт представления – это все будет обработка вне БД, если конечно программа не написана так, что при переупорядочивание данные не считываются заново, то есть если эта функция не решена средствами SQL. За тем может идти произвольное число простых транзакций, описанных ранее. Если не табельный номер, а суррогат, то обработка вне БД может заключаться в написании правильного запроса, так как пользователь не видит суррогаты, но они считываются и где-то размещаются в программе.
Любая транзакция всегда должна переводить БД из одного согласованного состояния в другое согласованное, хотя допускается, что согласованность БД будет нарушаться в ходе выполнения транзакции.
/* Пусть студент отучился на специальности некоторое время и получил оценки согласно плану этой специальности. При переводе его на другую специальность транзакция будет состоять из следующих действий: найти предметы, которые должен был изучить студент согласно плану новой специальности; для каждого этого предмета найти оценку у переводимого студента и перезачесть ее; все остальные оценки удалить. То есть и до и после выполнения транзакции БД находится в согласованном состоянии: все студенты имеют оценки согласно плану обучения по специальности, но в ходе выполнения часть оценок студента не относятся к специальности на которой он обучается.
Пример демонстрирует и сложность транзакции, и согласованность БД, и нарушение согласованности в ходе выполнения транзакции.
*/
Любая транзакция завершается одним из двух возможных способов. В случае успешного завершения результаты транзакции фиксируются (commit), и БД переходит в новое согласованное состояние. Если выполнение транзакции не увенчалось успехом, она отменяется. В этом случае в БД должно быть восстановлено то согласованное состояние, в котором она находилась до начала данной транзакции. Этот процесс называется откатом (roll back) транзакции. Зафиксированная транзакция не может быть отменена. Если зафиксированная транзакция была ошибочной, то необходимо выполнить другую транзакцию, возвращающую БД в предыдущее согласованное состояние.
В большинстве языков манипулирования данными для указания границ отдельных транзакций используются операторы begintransaction, commit, rollback.
Существуют свойства, которыми должна обладать транзакция. Они называются ACID:
1 Атомарность. («все или ничего» atomic). Любая транзакция представляет собой неделимую единицу работы, которая может быть либо выполнена вся целиком, либо не выполнена вовсе.
2 Согласованность (coordination). Каждая транзакция должна переводить БД из одного согласованного состояния в другое.
3 Изолированность (insulativity). Все транзакции выполняются независимо одна от другой. Другими словами, промежуточные результаты незавершенной транзакции не должны быть доступны другим транзакциям.
4 Продолжительность (duration). Результаты успешно завершенной транзакции должны сохраняться в БД постоянно и не должны быть утеряны в результате последующих сбоев.