-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathdb_exam.tex
127 lines (119 loc) · 14.6 KB
/
db_exam.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
% Created 2020-11-19 Thu 18:49
% Intended LaTeX compiler: pdflatex
\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{grffile}
\usepackage{longtable}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{textcomp}
\usepackage{amssymb}
\usepackage{capt-of}
\usepackage{hyperref}
\usepackage[russian]{babel}
\usepackage{amsmath}
\usepackage{esint}
\usepackage{mathtools}
\usepackage{amsthm}
\usepackage{minted}
\usepackage[top=0.8in, bottom=0.75in, left=0.625in, right=0.625in]{geometry}
\usepackage{float}
\def\zall{\setcounter{lem}{0}\setcounter{cnsqnc}{0}\setcounter{th}{0}\setcounter{Cmt}{0}\setcounter{equation}{0}\setcounter{stnmt}{0}}
\newcounter{lem}\setcounter{lem}{0}
\def\lm{\par\smallskip\refstepcounter{lem}\textbf{\arabic{lem}}}
\newtheorem*{Lemma}{Лемма \lm}
\newcounter{th}\setcounter{th}{0}
\def\th{\par\smallskip\refstepcounter{th}\textbf{\arabic{th}}}
\newtheorem*{Theorem}{Теорема \th}
\newcounter{cnsqnc}\setcounter{cnsqnc}{0}
\def\cnsqnc{\par\smallskip\refstepcounter{cnsqnc}\textbf{\arabic{cnsqnc}}}
\newtheorem*{Consequence}{Следствие \cnsqnc}
\newcounter{Cmt}\setcounter{Cmt}{0}
\def\cmt{\par\smallskip\refstepcounter{Cmt}\textbf{\arabic{Cmt}}}
\newtheorem*{Note}{Замечание \cmt}
\newcounter{stnmt}\setcounter{stnmt}{0}
\def\st{\par\smallskip\refstepcounter{stnmt}\textbf{\arabic{stnmt}}}
\newtheorem*{Statement}{Утверждение \st}
\author{Макаров Сергей, группа 427}
\date{\today}
\title{Базы данных}
\hypersetup{
pdfauthor={Макаров Сергей, группа 427},
pdftitle={Базы данных},
pdfkeywords={},
pdfsubject={},
pdfcreator={Emacs 27.1 (Org mode 9.4)},
pdflang={Russian}}
\begin{document}
\maketitle
\section{Вопрос 1}
\label{sec:org04b8f07}
Основные черты модели данных ODMG.
\subsection{Решение}
\label{sec:orgac92989}
\begin{enumerate}
\item База данных -- это набор объектов произвольного типа.
\item Типы подразделяются на две группы: литеральные типы, соответствующие типам данных из объектно-ориентированных языков, и объектные типы.
\item Литеральные типы: скалярные (атомарные) типы, типы структур и типы-коллекции.
\begin{enumerate}
\item Каждому экземпляру структурного типа соответствует уникальный идентификатор объекта. Этот идентификатор является аналогом ссылки на экземпляр объекта в ООЯП. Всегда, когда какой-то структурный тип содержит в себе в качестве атрибута другой структурный тип, значением этого атрибута будет идентификатор соответствующего объекта. Соответственно, атрибут такого типа может определяться, как на литеральном, так и на объектном типе.
\item Типы коллекций разбиваются на четыре вида: множества, мультимножества (множества, допускающие дубликаты), списки и словари (все ключи в словарях должны быть различны).
\end{enumerate}
\item Объектные типы подразделяются на атомарные и типы коллекций.
\begin{enumerate}
\item Атомарный объект описывается набором его атрибутов и связей, а так же применимых к нему операций. В частности, у каждого объекта должен быть конструктор, позволяющий создать новый объект, и получить его идентификатор, который впоследствии можно использовать для доступа к атрибутам и связям объектов. Атрибут объекта может быть любого типа, как литерального, так и объектного. В отличие от атрибутов, связи позволяют устанавливать двустороннюю связь между объектами различных видов: one-to-one, one-to-many, many-to-many.
\item Объектные типы-коллекции разрешены те же, что и литеральные. Типом элемента такого типа может быть любой тип, за исключением самого типа-коллекции. Существует частный случай использования типа-коллекции, когда при описании атомарного объектного типа можно описать тип-множество, содержащий объекты этого типа(так называемый экстент). Имя такой коллекции совпадает с именем атомарного объектного типа.
\end{enumerate}
\end{enumerate}
Для манипулирования данными применяется язык OQL. Этот язык обладает рядом полезных свойств:
\begin{enumerate}
\item Он очень близок к SQL/92
\item Он опирается на объектную модель ODMG, при этом он может свободно взаимодействовать с языками, определёнными в ODMG.
\item OQL является декларативным функциональным языком, что позволяет:
\begin{enumerate}
\item Неограниченную композируемость операторов OQL
\item Эффективную оптимизацию запросов OQL
\end{enumerate}
\item Эффективности OQL способствует тот факт, что он не является Тьюринг-полным языком. Кроме того, он легко формализуем.
\end{enumerate}
Объекты в ODMG считаются одинаковыми, только если они совпадают, т. е. у них одинаковый идентификатор. Это означает, что в модели ODMG нет аналога ограничения целостности сущности. При этом ограничения ссылочной целостности поддерживаются для связей "один-ко-многим". В этом случае объекты на стороне связи "один" считаются предками, а объекты на другой стороне -- потомками. При этом СУБД должен поддерживаться инвариант отсутствия потомков без предков.
\pagebreak
\section{Вопрос 2}
\label{sec:org9a09461}
Физически согласованное состояние базы данных. Восстановление базы данных после мягкого сбоя.
\subsection{Решение}
\label{sec:org97ff53c}
Состояние внешней памяти БД называется \emph{физически согласованным}, если состояние всех страниц всех объектов согласовано, т. е. для каждого объекта либо все страницы соответствуют его состоянию до изменения, либо все соответствуют его состоянию после изменения.
Мягким сбоем называется сбой, при котором было потеряно содержимое оперативной памяти, но состояние внешней памяти не потеряно. Примером такого сбоя может быть внезапное отключение питания.
Для поддержки возможности восстановления после мягких сбоев в журнале отмечаются точки физической согласованности БД, в которые состояние БД физически согласовано, а журнал записан во внешнюю память. Тогда с использованием журнализации изменений физических данных, либо с помощью теневого механизма возможно восстановить состояние БД в последней точке согласованности.
Теневой механизм для БД реализуется следующим образом: во внешней памяти поддерживается теневая таблица отображения файлов на сегменты внешней памяти, соответствующая состоянию этого отображения в последней точке физической согласованности. Соответственно, при установке точки физической согласованности нужно завершить все логические операции, откачать на диск все изменившиеся страницы буферного пула БД, и обновить теневую таблицу. Заметим, что такое обновление должно быть атомарным. Это можно сделать за счёт поддержки двух областей для теневой таблицы, и флага, указывающего на активную таблицу. Меняется активная таблица только после успешной её записи. При использовании теневого механизма для восстановления последнего физически согласованного состояния БД достаточно взять в качестве текущей страницы отображения активную теневую таблицу, подгрузив её в ОЗУ.
Альтернативным методом восстановления последнего физически целостного состояния БД может быть ведение журнала постраничных изменений. В этом случае для восстановления физически целостного состояния нужно откатить изменения, произошедшие после последней точки физической согласованности.
Дальнейшее восстановление последнего логически целостного состояния БД можно произвести следующим образом:
\begin{enumerate}
\item Повторно выполнить те действия тех транзакций, что начались до последней точки физической согласованности, и закончились до момента сбоя, которые не были выполнены. Эти действия можно восстановить из журнала.
\item Откатить действия тех транзакций, что начались до последней точки физической согласованности, и не успели закончиться до момента сбоя. Выполненные действия можно восстановить из журнала.
\item Если транзакция была закончена до последней точки физической согласованности, либо началась после точки физической согласованности, и не успела завершиться до сбоя, то ничего делать не надо. В первом случае результаты этой транзакции уже зафиксированы, а во втором они никак не отражены во внешней памяти.
\item Наконец для транзакций, которые были начаты после последней точки физической согласованности, а закончены до сбоя, нужно повторить все их действия. В журнале эти действия были зафиксированы.
\end{enumerate}
Заметим, что такое восстановление после сбоя возможно потому, что выполняемые транзакциями действия записываются в журнал \textbf{\textbf{до}} того, как они будут отражены во внешней памяти, т. е. используется протокол Write Ahead Log.
\pagebreak
\section{Задача}
\label{sec:orga1c16fa}
Написать запрос на языке исчисления кортежей, позволяющий найти всех начальников отделов, получающих зарплату, равную максимальной зарплате служащих в отделах, которыми они руководят.
\subsection{Решение}
\label{sec:orga46c9d6}
\begin{minted}[]{text}
RANGE СЛУЖАЩИЙ IS СЛУЖАЩИЕ
RANGE СЛУЖАЩИЙ2 IS СЛУЖАЩИЕ
RANGE ОТДЕЛ IS ОТДЕЛЫ
СЛУЖАЩИЙ.СЛУ_НОМЕР = ОТДЕЛ.ОТД_РУК AND СЛУЖАЩИЙ.СЛУ_ОТД_НОМЕР = ОТДЕЛ.ОТД_НОМЕР
AND FORALL СЛУЖАЩИЙ2 (NOT СЛУЖАЩИЙ2.СЛУ_ОТД_НОМЕР = СЛУЖАЩИЙ.СЛУ_ОТД_НОМЕР
OR СЛУЖАЩИЙ2.СЛУ_ЗАРП <= СЛУЖАЩИЙ.СЛУ_ЗАРП)
\end{minted}
Схема базы данных предполагается такой же, как на рисунке 1.7 из первой лекции, за исключением того, что зарплата служащего является атрибутом отношения СЛУЖАЩИЕ, а не ОТДЕЛЫ.
\pagebreak
\end{document}