Главная » SQL, Базы данных » Хронологические базы данных

0

Хронологическая база данных может быть неформально определена как  база, которая содержит исторические данные1 наряду с текущими данными или вместо них (в  качестве  наглядного  примера  такой  базы  данных  можно  указать  хранилище данных; см. главу 22). Обычные, или  нехронологические,  базы данных содержат только текущие данные; актуальность таких баз поддерживается путем обновления данных сразу же  после того, как представленные в них высказывания становятся ложными. В отличие от них, хронологические базы данных обновляются очень редко (а  могут вообще не обновляться), если не считать выполнения операций  INSERT, которые применяются для их первоначального заполнения. Например, рассмотрим базу  данных  поставщиков  и  деталей.  Если  в  ней  находятся  значения,  обычно используемые в данной книге в качестве примеров, то эта база данных, кроме всего прочего,  показывает,  что  статус  поставщика  S1  (под  этим  подразумевается  тот статус, каковым он является "в настоящее время") равен 20. Но в хронологической

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

‘ могут содержать данные, относящиеся не только к прошлому, но и к будущему, поэтому термин"исторический"следуетпониматькакохватывающийиэтувозможность.

время статус поставщика S1 равен 20, но и то, что он был равен 20 с 1 июля прошлого года, а также, возможно, что он был равен 15 с 5 апреля до 30 июня прошлого года и т.д.

Исследования в области хронологических баз данных интенсивно  проводились,  по

меньшей мере, с начала 1980-х годов и предусматривали в значительной степени изучение самой природы времени. Ниже перечислены некоторые проблемы, которые рассматривались в этих исследованиях.

■     Имеет ли время начало или конец?

■     Является ли время непрерывным или делится на дискретные кванты?

■     Как можно лучше всего охарактеризовать важное понятие "текущего времени" (иногда определяемое как "движущаяся по временной шкале позиция текущего времени")?

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

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

Рис. 23.4. База данных поставщиков и поставок (вторая полностью хронологическая версия, в которой используются интервалы) и примеры значений

Затем  определим6   генератор  типа  INTERVAL. ЕСЛИ  Т  —  позиционный  тип,  то INTERVAL_T                                        —     это     интервальный     тип,     полученный                                        путем                                        вызова соответствующего генератора типа т.

6 Следует отметить, что генератор типа INTERVAL является единственной конструкцией, описанной в этой главе, которая не является просто сокращенным обозначением. Поэтому применяемый автором подход к  определению хронологических баз данных (в отличие от некоторых других подходов, описанных в литературе) не предусматривает введения каких-либо изменений в классическую реляционную модель (хотя и связан с  необходимостью ввести некоторые обобщения, как будет показано в разделах 23.5 и 23.7).

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

■     Рассматривается только одно возможное представление — любое значение типа INTERVAL_T (т.е. любой интервал времени этого типа) может быть представлено в виде пары значений типа т, соответствующих начальной и конечной позициям рассматриваемого интервала. Соответствующий оператор селектора имеет сле дующий синтаксис.

INTERVAL_T    (    [   b   :    е   ]    )

Здесь b и е — выражения типа т, и общий вызов селектора возвращает значение интервала с начальной и конечной позициями, которые равны  значениям, обозначенным этими выражениями.

■     Соответствующие "операторы ТНЕ_", BEGIN И END, имеют следующий синтаксис.

BEGIN   (   i   ) END    (   i   )

Здесь i — выражение некоторого интервального типа, и эти два вызова операторов возвращают, соответственно, начальную и конечную позиции интервала, обозначенного этим выражением.

Примечание. Как уже было указано, операторы BEGIN and END фактически являются "операторами ТНЕ_", а в языке Tutorial D такие операторы обычно обозначаются как THE_BEGIN и THE_END. Но вместо этого здесь и дальше в данной главе для согласования с другими работами в области исследования хронологических баз данных используются обозначения BEGIN и END.

■     К другим универсальным операторам относятся оператор присваивания ": =", множество логических операторов (включающих, в частности, оператор "="), из вестных под общим названием операторов Аллена (они описаны ниже в этом разде ле), и целый ряд других операторов (которые также описаны ниже в этом разделе).

■      Рассмотрим только одно универсальное ограничение, а именно ограничение, согласно которому, если i является интервалом, то BEGIN  (i)  < END (i). Одним из следствий этого ограничения является то, что интервалы никогда не бывают пустыми — они всегда содержат по меньшей мере одну позицию. Другим следствием становится то, что больше не нужны явные ограничения, "позволяющие предотвратить появление бессмысленных пар FROM-TO, в которых значение то меньше значения FROM" (как было указано в предыдущем разделе).

Теперь должно быть очевидно, что тип DATE, в частности, удовлетворяет требованиям к позиционному типу и поэтому может использоваться в качестве такого типа. Следовательно,  INTERVAL_DATE —  это допустимый  интервальный  тип,  поэтому определения переменных отношения S_DURING и SP_DURING могут выглядеть примерно следующим образом.

VAR S_DURING BASE RELATION

{ S# S#, DURING INTERVAL_DATE } KEY { S#, DURING } ;

VAR SP_DURING BASE RELATION

{ S# S#, P# P#, DURING INTERVAL_DATE } KEY { S#, P#, DURING } ;

Следует отметить, что эти определения все еще остаются весьма неполными! Мы вернемся к этой теме и доработаем указанные определения в разделе 23.7. Но следует отметить, что эти определения позволяют устранить проблему, связанную с необходимостью применять произвольный выбор в отношении того, какой из двух потенциальных ключей должен стать первичным. А что касается других ограничений и запросов, приведенных в разделе 23.2, то должно быть ясно, что непосредственные аналоги этих ограничений и запросов могут быть легко сформулированы применительно к базе данных, показанной на рис. 23.4, благодаря существованию операторов BEGIN и END. Но здесь не показаны какие-либо из этих формулировок, поскольку в задачу автора входит именно предоставление читателю гораздо более лучшего способа выражения таких ограничений и запросов.

Еще раз отметим, что тип DATE является допустимым позиционным типом, но до сих

пор в этой главе еще не было выдвинуто ни одного требования, чтобы позиционные типы относились именно к типам "даты и времени" или чтобы сами интервалы были именно интервалами "даты и времени". В действительности, хотя интервалы являются фундаментальной абстракцией, необходимой для работы с хронологическими данными,

: должно быть ясно, что понятие интервала фактически имеет гораздо более широкую об-: ласть применения; это означает, что имеется также много других приложений для

интер-i валов, в которых интервалы не обязательно являются хронологическими. Ниже приведено несколько примеров.

■     Суммы, облагаемые налогами, разбиты на шкалы с разными ставками налогов; иными словами, на интервалы, начальными и конечными позициями которых (а также всеми промежуточными позициями) являются денежные значения. Компьютеры рассчитаны на эксплуатацию в пределах определенных диапазонов температур и напряжений, иными словами, интервалов, которые состоят из позиций, представляющих собой, соответственно, температуры и напряжения.

■     Чувствительность различных животных к внешней среде характеризуется разными частотами световых и звуковых волн, которые могут восприниматься их

органами зрения и слуха.

■     Различные природные явления возникают и могут быть измерены с учетом интер валов глубины земли или моря, либо высоты над уровнем моря.

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

■     INTERVAL_INTEGER

Здесь позиционным типом является INTEGER, функцией определения последующей позиции является функция определения "следующего целого числа" (т.е.

функция "сложения с единицей"), а значениями этого интервального типа являются интервалы в форме [b: е], где b и е — значения типа INTEGER и b ≤ e.

■    INTERVAL_MONEY

Здесь MONEY (остановимся на таком допущении) — тип, который представляет денежные суммы, измеряемые в долларах и центах. Функцией определения последующей позиции является функция "сложения с одним центом". Значениями этого интервального типа являются интервалы в форме [b: е], где Ь и е — значения типа MONEY И b ≤ е.

Операции над позициями и интервалами

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

Терминология. Допустим, что т — позиционный тип, а р, p1 и р2 — значения типа т; неформально  можно  предположить,  что  для  обозначения  позиций,  соответственно, предшествующей и последующей по отношению к р, могут использоваться выражения р+1

и р-1. Кроме того, допустим, что i, il и i2 — интервалы типа INTERVAL_T; b, Ы и Ь2 —

начальные позиции, а е, el и е2 — конечные позиции, соответственно, интервалов i, il и i2; неформально можно предположить, что для обозначения  интервалов i, il и i2 используются, соответственно, выражения [b:e], [Ы:е1] и [b 2: е 2].

В таком случае справедливы приведенные ниже утверждения.

Выражение ls_NEXT_T(pl,p2) принимает истинное значение тогда и  только тогда, когда позиция pi является непосредственно предшествующей по отношению к позиции р2. Выражение is_PRlOR_T(pl,p2) принимает  истинное значение тогда и только тогда, когда является истинным выражение ls_NEXT_T(p2,pl); это означает, что is_PRiOR_T(pl,p2)  = is_NEXT_T(p2,pl).

Выражение MAX (pi, р2) возвращает р2, если выражение pi < р2 является  истинным, в противном случае оно возвращает pi; выражение мш(р1,р2) возвращает pi, если выражение pi < р2 является истинным, в  противном случае оно возвращает р2.

■     Выражение р £  i является истинным тогда и только тогда, когда выражения b < р ир < е оба являются истинными; это означает, что р е   i =   (b < р AND p < е ). Кроме  то го ,  i  зр  = р  е     i.

Примечание. Символы "е " и "э" читаются, соответственно, как "содержится в" и

"содержит".

Выражение COUNT( i ) возвращает результат подсчета количества различных позицийр, таких что р Е   i.

■     Интервал   i  является  единичным  интервалом  тогда  и  только  тогда,   когда COUNT (i)   = 1. Выражение POINT FROM i возвращает единственную позицию из единичного интервала i.

Выражения PRE (i) и POST (i), соответственно, возвращают позиции b-1 и е+1. Примечание. Выражения PRE(i) и POST(i), соответственно, являются сокращениями ОТ PRIOR_T(BEGIN ( i)) И NEXT_T(END(i)) .

Затем может быть определен целый ряд операторов для проверки того, являются ли два интервала равными, перекрываются ли они и т.д. Рассматриваемые операторы известны под общим названием операторов  Аллена, поскольку основная из часть была впервые предложена Алленом (Allen) в [23.1], но здесь мы не всегда следуем предложенной Алленом классификации этих операторов. Эти операторы определены наиболее сжато, в терминах  эквивалентностей, но читателю рекомендуется нарисовать какие-то наглядные схемы, чтобы понять их на интуитивном уровне.

■   Равняется (=): ( i l  =  i2)   =   (b1  = b2 AND el  =  e2).

■   Включает ("  ⊇  ") и включено в (" ⊆ "): ( i l ⊇  i2)   =   (b1 ≤ b2  AND el   ≥

e 2 );  (i 2 ⊆ il)    =    (il   ⊇  i2 ).

■ Строго включает (" ⊃ ") и строго включено в (" ⊂ "): (il  ⊃  i2)   =   ( i l  ⊇  i2

AND il  ≠ i2 ) ; ( i 2   ⊂  il)    =    (il   ⊃ i2 ).

■     BEFORE И AFTER:   ( i l    BEFORE   i2)     =     (el     <   b2) ;   ( i l    AFTER i2)     =     ( i 2  BEFORE    i l ) .

■     MEETS:  ( i l  MEETS   i2)     =     (b2  =   el+1  ; OR  b1   =   e 2 +l).

OVERLAPS: ( i l    OVERLAPS    i2)    =    (b1 ≤  e2  AND b2 ≤  e1) .

■     MERGES: ( i l    MERGES   i2)   =   ( i l    OVERLAPS   i2   OR   il   MEETS i2).

BEGINS:  ( i l     BEGINS    i2)    =    (b1    =   b2   AND   el  ≤ e2).

ENDS: ( i l    ENDS    i2)    =    (el    =    e2    AND   b1≥ b2 ).

Наконец,  определим  некоторые полезные бинарные операторы над  интервалами, которые возвращают интервалы, а именно аналоги знакомых операторов UNION, INTERSECT и MINUS для работы с интервалами. Каждый из них принимает два интервала такого же типа, как и его операнды, и возвращает в качестве результата другой интервал такого же типа (ниже даны определения этих операторов и приведены некоторые примеры).

■     Оператор UNION. Выражение il  UNION i2 возвращает [MlN(bl,b2) : MAX (el, e2) ], если выражение il  MERGES   i2 принимает истинное значение; в против ном случае оно не определено. Например, объединением интервалов [d04 : d08 ] и

[d06:dl0] является интервал  [d04:dl0]; объединение интервалов [d02:d03]

и [d06:dl0] не определено.

■     Оператор INTERSECT. Выражение il   INTERSECT   i2 возвращает [МАХ   (Ы, Ь2) :MIN   (el,   e2) ], если выражение il   OVERLAPS   i2 принимает истинное значение; в противном случае оно не определено. Например, пересечением интер валов  [d04:d08]  и   [d06:dl0]   является интервал   [ d 06: d0 8] ;  пересечение

[d02:d03] и [d06:dl0] не определено.

Оператор MINUS. Выражение il   MINUS   i2 возвращает [bl:MlN(b2-l, el) ], если оба выражения, Ы   <   b2 и el ≤ e2, принимают истинное значение и возвращает [МАХ(е2 + 1,b1): el], если оба выражения,b1≥ b2 и el > e2,

принимают истинное значение, а в противном случае результат этого выражения не определен. Например, разность между интервалами [d04:d08] и [d06:dl0] (в указанном порядке) равна [ d04: d05 ], разность  между интервалами [ d06: dl0 ] и [d04:d08] (в указанном порядке) равна  [dO9 :dl0], разность между интервалами [d02:d03] и [d06:dl0] (в любом порядке) не определена.

Примеры запросов

В завершение этого раздела рассмотрим несколько примеров запросов, которые наглядно иллюстрируют использование некоторых операторов,  определенных в предыдущем подразделе. Вначале рассмотрим запрос: "Получить номера поставщиков, которые были  способны  поставлять  деталь  Р2  в  восьмые  сутки". Ниже  приведена  возможная формулировка этого запроса к базе данных, показанной на рис. 23.4.

( SP_DURING WHERE Р# = Р# (‘Р2′)

AND dO8 € DURING ) { S# }

Пояснение. Выражение во внешних круглых скобках сокращает множество кортежей, присутствующих в настоящее время в переменной отношения  SP_DURING, до такого множества кортежей, в котором значение р# равно Р2, а в интервале, представляющем собой значение DURING, содержатся восьмые сутки. Затем к этому множеству кортежей применяется операция проекции по атрибуту s# для получения желаемого результата.

Примечание. На практике применяемое здесь выражение "d08" необходимо было бы заменить соответствующим вызовом селектора DATE.

В качестве второго примера рассмотрим приведенную ниже возможную формулировку запроса: "Определить пары поставщиков, которые были способны поставлять одну и ту же деталь одновременно".

WITH ( SP_DURING RENAME (   S# AS X#, DURING AS XD ) ) AS Tl , ( SP_DURING RENAME (   S# AS Y#, DURING AS YD ) ) AS T2 ,

( Tl JOIN T2 ) AS T3   , ( T3 WHERE XD OVERLAPS YD ) AS T4

,

( T4 WHERE X# < Y# )    AS T5 : T5 { X#, Y# }

Пояснение. Здесь Tl — отношение, которое является текущим значением переменной отношения SP_DURING, за исключением того, что атрибуты S# и DURING переименованы, соответственно, в х# и XD; отношение Т2 является таким же, за исключением того, что в нем новыми именами атрибутов являются У# и YD. Отношение ТЗ является соединением отношений Т1 и Т2 по номерам деталей. Отношение Т4 представляет собой сокращение от ТЗ, в котором присутствуют только такие кортежи, в которых интервалы XD и YD перекрываются (это означает, что поставщики не только были способны поставлять одну и ту же деталь, но фактически были способны поставлять одну и ту же деталь одновременно, что и требовалось определить по условиям запроса). Отношение Т5 является сокращенным обозначением от Т4, в котором присутствуют только те кортежи, где номер поставщика х# меньше номера поставщика Y# (сравните с примером 7.5.5 из главы 7). Заключительная операция проекции пох# и Y# вырабатывает требуемый результат.

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

WITH ( SP_DURING RENAME ( S# AS X#, DURING AS XD ) ) AS Tl , ( SP_DURING RENAME ( S# AS Y#, DURING AS YD ) ) AS T2 , ( Tl JOIN T2 ) AS T3 ,

( T3 WHERE XD OVERLAPS YD ) AS T4 ,

( T4 WHERE X# < Y# ) AS T5 ,

( EXTEND T5 ADD ( XD INTERSECT YD ) AS DURING ) AS T6 : T6 { X#, Y#, P#, DURING }

Пояснение. Отношения Tl, T2, ТЗ, Т4 и Т5 являются точно такими же, как в предыдущем примере. После их получения с помощью оператора EXTEND вычисляются соответствующие интервалы, а завершающая операция проекции  вырабатывает желаемый результат.

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии