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

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

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

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

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

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

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

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

оператор объединения $i_{1}~{\text{UNION}}~i_{2}$ $i_{1}~{\text{UNION}}~i_{2}$ возвращает [MIN(b1, b2):MAX(e1, e2)], если выражение $i_{1}~{\text{MERGES}}~i_{2}$ $i_{1}~{\text{MERGES}}~i_{2}$ истинно, в противном случае результат не определён;
оператор пересечения $i_{1}~{\text{INTERSECT}}~i_{2}$ $i_{1}~{\text{INTERSECT}}~i_{2}$ возвращает [MAX(b1, b2): MIN(e1, e2)], если выражение $i_{1}~{\text{OVERLAPS}}~i_{2}$ $i_{1}~{\text{OVERLAPS}}~i_{2}$ истинно, в противном случае результат не определён;
оператор разности $i_{1}~{\text{MINUS}}~i_{2}$ $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_ключу и распаковывается при внесении изменений для поддержания непротиворечивого состояния.