Skip to content

Latest commit

 

History

History
93 lines (78 loc) · 14 KB

db_exam.org

File metadata and controls

93 lines (78 loc) · 14 KB

Базы данных

Вопрос 1

Основные черты модели данных ODMG.

Решение

  1. База данных – это набор объектов произвольного типа.
  2. Типы подразделяются на две группы: литеральные типы, соответствующие типам данных из объектно-ориентированных языков, и объектные типы.
  3. Литеральные типы: скалярные (атомарные) типы, типы структур и типы-коллекции.
    1. Каждому экземпляру структурного типа соответствует уникальный идентификатор объекта. Этот идентификатор является аналогом ссылки на экземпляр объекта в ООЯП. Всегда, когда какой-то структурный тип содержит в себе в качестве атрибута другой структурный тип, значением этого атрибута будет идентификатор соответствующего объекта. Соответственно, атрибут такого типа может определяться, как на литеральном, так и на объектном типе.
    2. Типы коллекций разбиваются на четыре вида: множества, мультимножества (множества, допускающие дубликаты), списки и словари (все ключи в словарях должны быть различны).
  4. Объектные типы подразделяются на атомарные и типы коллекций.
    1. Атомарный объект описывается набором его атрибутов и связей, а так же применимых к нему операций. В частности, у каждого объекта должен быть конструктор, позволяющий создать новый объект, и получить его идентификатор, который впоследствии можно использовать для доступа к атрибутам и связям объектов. Атрибут объекта может быть любого типа, как литерального, так и объектного. В отличие от атрибутов, связи позволяют устанавливать двустороннюю связь между объектами различных видов: one-to-one, one-to-many, many-to-many.
    2. Объектные типы-коллекции разрешены те же, что и литеральные. Типом элемента такого типа может быть любой тип, за исключением самого типа-коллекции. Существует частный случай использования типа-коллекции, когда при описании атомарного объектного типа можно описать тип-множество, содержащий объекты этого типа(так называемый экстент). Имя такой коллекции совпадает с именем атомарного объектного типа.

Для манипулирования данными применяется язык OQL. Этот язык обладает рядом полезных свойств:

  1. Он очень близок к SQL/92
  2. Он опирается на объектную модель ODMG, при этом он может свободно взаимодействовать с языками, определёнными в ODMG.
  3. OQL является декларативным функциональным языком, что позволяет:
    1. Неограниченную композируемость операторов OQL
    2. Эффективную оптимизацию запросов OQL
  4. Эффективности OQL способствует тот факт, что он не является Тьюринг-полным языком. Кроме того, он легко формализуем.

Объекты в ODMG считаются одинаковыми, только если они совпадают, т. е. у них одинаковый идентификатор. Это означает, что в модели ODMG нет аналога ограничения целостности сущности. При этом ограничения ссылочной целостности поддерживаются для связей “один-ко-многим”. В этом случае объекты на стороне связи “один” считаются предками, а объекты на другой стороне – потомками. При этом СУБД должен поддерживаться инвариант отсутствия потомков без предков. \pagebreak

Вопрос 2

Физически согласованное состояние базы данных. Восстановление базы данных после мягкого сбоя.

Решение

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

Теневой механизм для БД реализуется следующим образом: во внешней памяти поддерживается теневая таблица отображения файлов на сегменты внешней памяти, соответствующая состоянию этого отображения в последней точке физической согласованности. Соответственно, при установке точки физической согласованности нужно завершить все логические операции, откачать на диск все изменившиеся страницы буферного пула БД, и обновить теневую таблицу. Заметим, что такое обновление должно быть атомарным. Это можно сделать за счёт поддержки двух областей для теневой таблицы, и флага, указывающего на активную таблицу. Меняется активная таблица только после успешной её записи. При использовании теневого механизма для восстановления последнего физически согласованного состояния БД достаточно взять в качестве текущей страницы отображения активную теневую таблицу, подгрузив её в ОЗУ.

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

Дальнейшее восстановление последнего логически целостного состояния БД можно произвести следующим образом:

  1. Повторно выполнить те действия тех транзакций, что начались до последней точки физической согласованности, и закончились до момента сбоя, которые не были выполнены. Эти действия можно восстановить из журнала.
  2. Откатить действия тех транзакций, что начались до последней точки физической согласованности, и не успели закончиться до момента сбоя. Выполненные действия можно восстановить из журнала.
  3. Если транзакция была закончена до последней точки физической согласованности, либо началась после точки физической согласованности, и не успела завершиться до сбоя, то ничего делать не надо. В первом случае результаты этой транзакции уже зафиксированы, а во втором они никак не отражены во внешней памяти.
  4. Наконец для транзакций, которые были начаты после последней точки физической согласованности, а закончены до сбоя, нужно повторить все их действия. В журнале эти действия были зафиксированы.

Заметим, что такое восстановление после сбоя возможно потому, что выполняемые транзакциями действия записываются в журнал **до** того, как они будут отражены во внешней памяти, т. е. используется протокол Write Ahead Log. \pagebreak

Задача

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

Решение

RANGE СЛУЖАЩИЙ IS СЛУЖАЩИЕ
RANGE СЛУЖАЩИЙ2 IS СЛУЖАЩИЕ
RANGE ОТДЕЛ IS ОТДЕЛЫ

СЛУЖАЩИЙ.СЛУ_НОМЕР = ОТДЕЛ.ОТД_РУК AND СЛУЖАЩИЙ.СЛУ_ОТД_НОМЕР = ОТДЕЛ.ОТД_НОМЕР
AND FORALL СЛУЖАЩИЙ2 (NOT СЛУЖАЩИЙ2.СЛУ_ОТД_НОМЕР = СЛУЖАЩИЙ.СЛУ_ОТД_НОМЕР
    OR СЛУЖАЩИЙ2.СЛУ_ЗАРП <= СЛУЖАЩИЙ.СЛУ_ЗАРП)

Схема базы данных предполагается такой же, как на рисунке 1.7 из первой лекции, за исключением того, что зарплата служащего является атрибутом отношения СЛУЖАЩИЕ, а не ОТДЕЛЫ. \pagebreak