Хронологическая база данных

Хронологическая база данных — база данных, содержащая исторические (хронологические) данные, то есть данные, относящиеся к прошлым и, возможно, к будущим периодам времени. Обычная, нехронологическая база данных содержит только текущие данные.

Типы данных и операторыПравить

Хронологические данные представляют собой истинные высказывания с указанием интервалов времени. Интервалом времени является непустой отрезок временной шкалы, для его обозначения используется специальный интервальный тип данных INTERVAL_DATE. Значения этого типа записываются в виде $\text{[math]}$ $\text{[math]}$ $[b:e]$ , где $\text{[math]}$ $\text{[math]}$ $b, e$ — выражения типа DATE, соответствующие начальной и конечной временной позиции интервала. Под временными позициями (позициями на временной шкале) понимают единицы времени, подходящие для определённой цели (миллисекунды, секунды, сутки) и считающиеся неделимыми.

Допустим $\text{[math]}$ $\text{[math]}$ $i,i_{1},i_{2}$ — значения интервального типа, имеющие соответственно начальные позиции $\text{[math]}$ $\text{[math]}$ $b,b_{1},b_{2}$ и конечные позиции $\text{[math]}$ $\text{[math]}$ $e,e_{1},e_{2}$ , $\text{[math]}$ $\text{[math]}$ $p$ — произвольная временная позиция. Для обозначения предшествующей и последующей временной позиции используются выражения вида $\text{[math]}$ $\text{[math]}$ $p-1$ и $\text{[math]}$ $\text{[math]}$ $p+1$ . Оператор $\text{[math]}$ $\text{[math]}$ ${\text{COUNT}}(i)$ возвращает количество различных позиций $\text{[math]}$ $\text{[math]}$ $p$ таких, что $\text{[math]}$ $\text{[math]}$ $p\in i$ . Интервал $\text{[math]}$ $\text{[math]}$ $i$ является единичным интервалом, если $\text{[math]}$ $\text{[math]}$ ${\text{COUNT}}(i)=1$ .

Для проверки условий, связанных с интервалами, используются операторы Аллена:

интервалы равны: $\text{[math]}$ $\text{[math]}$ $i_{1}=i_{2}\Leftrightarrow (b_{1}=b_{2})\wedge (e_{1}=e_{2})$ ;
$\text{[math]}$ $\text{[math]}$ $i_{1}$ включает $\text{[math]}$ $\text{[math]}$ $i_{2}$ : $\text{[math]}$ $\text{[math]}$ $i_{1}\supseteq i_{2}\Leftrightarrow (b_{1}\leq b_{2})\wedge (e_{1}\geq e_{2})$
$\text{[math]}$ $\text{[math]}$ $i_{1}$ строго включает $\text{[math]}$ $\text{[math]}$ $i_{2}$ : $\text{[math]}$ $\text{[math]}$ $i_{1}\supset i_{2}\Leftrightarrow (i_{1}\supseteq i_{2})\wedge (i_{1}\neq i_{2})$ ;
$\text{[math]}$ $\text{[math]}$ $i_{1}$ перед $\text{[math]}$ $\text{[math]}$ $i_{2}$ : $\text{[math]}$ $\text{[math]}$ $i_{1}~{\text{BEFORE}}~i_{2}\Leftrightarrow e_{1}<b_{2}$ ;
интервалы встречаются: $\text{[math]}$ $\text{[math]}$ $i_{1}~{\text{MEETS}}~i_{2}\Leftrightarrow (b_{2}=e_{1}+1)\vee (b_{1}=e_{2}+1)$ ;
интервалы перекрываются: $\text{[math]}$ $\text{[math]}$ $i_{1}~{\text{OVERLAPS}}~i_{2}\Leftrightarrow (b_{1}\leq e_{2})\wedge (b_{2}\leq e_{1})$ ;
интервалы сливаются: $\text{[math]}$ $\text{[math]}$ $i_{1}~{\text{MERGES}}~i_{2}\Leftrightarrow (i_{1}~{\text{OVERLAPS}}~i_{2})\vee (i_{1}~{\text{MEETS}}~i_{2})$ .

Кроме того, имеются бинарные операторы над интервалами, которые возвращают интервалы:

оператор объединения $\text{[math]}$ $\text{[math]}$ $i_{1}~{\text{UNION}}~i_{2}$ возвращает [MIN(b1, b2):MAX(e1, e2)], если выражение $\text{[math]}$ $\text{[math]}$ $i_{1}~{\text{MERGES}}~i_{2}$ истинно, в противном случае результат не определён;
оператор пересечения $\text{[math]}$ $\text{[math]}$ $i_{1}~{\text{INTERSECT}}~i_{2}$ возвращает [MAX(b1, b2): MIN(e1, e2)], если выражение $\text{[math]}$ $\text{[math]}$ $i_{1}~{\text{OVERLAPS}}~i_{2}$ истинно, в противном случае результат не определён;
оператор разности $\text{[math]}$ $\text{[math]}$ $i_{1}~{\text{MINUS}}~i_{2}$ возвращает [b1:MIN(b2-1,e1)], если b1 < b2 и e1 ≤ e2 и возвращает [MAX(e2+1,b1), e1], если b1 ≥ b2 и e1 > e2, в противном случае результат не определён.

Операторы EXPAND и COLLAPSE принимают в качестве операнда унарное отношение, кортежи которого содержат интервалы и возвращают отношение того же типа, являющееся соответственно развёрнутой и сжатой формой исходного отношения.

Пример использования операторов EXPAND и COLLAPSE:

R
D
[d06:d09]
[d04:d08]
[d05:d10]
[d01:d01]

Rx
D
[d01:d01]
[d04:d04]
[d05:d05]
[d06:d06]
[d07:d07]
[d08:d08]
[d09:d09]
[d10:d10]

Rc
D
[d01:d01]
[d04:d10]

Развёрнутой формой отношения R является отношение Rx, содержащее все кортежи с единичным интервалом [p: p], где p — позиция в некотором интервале некоторого кортежа отношения R. Сжатой формой отношения R является такое отношение Rc, что: отношения R и Rc имеют одну и ту же развёрнутую форму; никакие два разных кортежа в отношении Rc не содержат интервалы i1 и i2 такие, что i1 MERGES i2 является истиной.

Оператор PACK и UNPACK принимают в качестве операндов отношение и атрибут интервального типа, принадлежащий этому отношению, и возвращает отношение того же типа, соответственно свёрнутое по указанному атрибуту с группировкой по остальным атрибутам, и развёрнутое по указанному атрибуту.

Пример использования операторов PACK и UNPACK:

R
A	D
A2	[d02:d04]
A2	[d03:d05]
A4	[d02:d05]
A4	[d04:d06]
A4	[d09:d10]

PACK R ON D
A	D
A2	[d02:d05]
A4	[d02:d06]
A4	[d09:d10]

UNPACK R ON D
A	D
A2	[d02:d02]
A2	[d03:d03]
A2	[d04:d04]
A2	[d05:d05]
A4	[d02:d02]
A4	[d03:d03]
A4	[d04:d04]
A4	[d05:d05]
A4	[d06:d06]
A4	[d09:d09]
A4	[d10:d10]

Упаковать отношение R по нескольким атрибутам D1, D2, …, Dn можно распаковав R по всем указанным атрибутам, а затем упаковать полученный результат по атрибуту D1, результат упаковки упаковать по атрибуту D2, …, результат упаковки упаковать по атрибуту Dn.

Для всех обычных реляционных операторов определены аналогичные им U_операторы, которые распаковывают отношение по указанным атрибутам, выполняют соответствующую операцию и упаковывают полученный результат. Например, операторы U_MINUS, U_INTERSECT, U_UNION, U_JOIN соответствуют операторам MINUS, INTERSECT, UNION, JOIN. U_OPERATOR определяется как:

PACK ((UNPACK R1 ON D) OPERATOR (UNPACK R2 ON D)) ON D

Операция распаковки при использовании длинных интервалов с большой степенью детализации может потребовать слишком большого объёма памяти для своего выполнения. Использование U_операторов позволяет оптимизатору выбрать реализацию, которая требует минимального количества промежуточных результатов.

Пример использования оператора U_MINUS:

R1
D
[d02:d05]

R2
D
[d03:d03]

результат
D
[d02:d02]
[d04:d05]

ДекомпозицияПравить

Хранение текущей информации в одних переменных отношения, а исторической информации — в других называется горизонтальной декомпозицией. Хранение исторической информации в виде множества отдельных переменных отношения (каждая из которых содержит один атрибут интервального типа и один атрибут другого типа) называется вертикальной декомпозицией.

Предположим, переменная отношения R имеет атрибут интервального типа D и атрибуты других типов A1, A2, …, An. При изменении атрибутов A1, A2, …, An независимо друг от друга во времени в переменную отношения необходимо вносить сложный ряд обновлений, для представления информации о значении атрибута в течение определённого интервала времени может потребоваться более одного кортежа. Поэтому целесообразно распределить информацию по переменным отношения R1, R2, …, Rn, которые будут иметь атрибуты D и A1, D и A2, …, D и An соответственно.

Пример вертикальной декомпозиции

R
A1	A2	D
10	BB+	[d01:d03]
15	BB+	[d04:d05]
15	AA-	[d06:d08]

R1
A1	D
10	[d01:d03]
15	[d04:d08]

R2
A2	D
BB+	[d01:d05]
AA-	[d06:d08]

Данное отношение после выполнения декомпозиции находится в шестой нормальной форме.

Ограничения целостностиПравить

Вхождение атрибута D интервального типа в состав потенциального ключа не решает проблему избыточности и противоречия. Отношение может иметь два кортежа с перекрывающимися интервалами и совпадающими значениями остальных атрибутов. При этом имеется избыточность информации, данные за некоторые временные интервалы, указываются дважды. Кроме того, существует проблема многословия, когда два кортежа имеют интервалы следующие непосредственно друг за другом при совпадающих значениях остальных атрибутов. В этом случае, хотя информация и не дублируется, но её можно представить в виде одного кортежа. Для устранения проблемы избыточности и многословия необходимо, чтобы переменная отношения постоянно была упакована по атрибуту D.

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

Для удовлетворения этих требований вводятся U_ключи. Переменная отношения поддерживается упакованной по U_ключу и распаковывается при внесении изменений для поддержания непротиворечивого состояния.

ЛитератураПравить

Дейт К. Дж. Введение в системы баз данных = Introduction to Database Systems. — 8-е изд. — М.: Вильямс, 2005. — 1328 с. — ISBN 5-8459-0788-8 (рус.) ISBN 0-321-19784-4 (англ.).