Theoretical and applied aspects of relations and operations for sequences of time intervals
Prombles in programming 2013; 3: 61-68
Збережено в:
| Дата: | 2025 |
|---|---|
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | rus |
| Опубліковано: |
Інститут програмних систем НАН України
2025
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/753 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
Репозитарії
Problems in programming| id |
pp_isofts_kiev_ua-article-753 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/92/caacc13c6babcaa0038f5474578d9e92.pdf |
| spelling |
pp_isofts_kiev_ua-article-7532025-06-21T15:30:49Z Theoretical and applied aspects of relations and operations for sequences of time intervals Теоретический и прикладной аспекты отношений и операций для последовательностей временных интервалов Kudym, K.A. Reznichenko, V.A. Proskudina, G.Yu. Ovdii, О.М. UDC 004.62 УДК 004.62 Prombles in programming 2013; 3: 61-68 Рассмотрены понятия момента времени, временного интервала и временной цепочки ― последовательности интервалов времени. Определены основные отношения и операции над этими объектами. Приведены эффективные алгоритмы для реализации операций над временными цепочками. Рассматривается практическое применение временных цепочек.Prombles in programming 2013; 3: 61-68 Інститут програмних систем НАН України 2025-06-21 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/753 PROBLEMS IN PROGRAMMING; No 3 (2013); 61-68 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 3 (2013); 61-68 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 3 (2013); 61-68 1727-4907 rus https://pp.isofts.kiev.ua/index.php/ojs1/article/view/753/805 Copyright (c) 2025 PROBLEMS IN PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2025-06-21T15:30:49Z |
| collection |
OJS |
| language |
rus |
| topic |
UDC 004.62 |
| spellingShingle |
UDC 004.62 Kudym, K.A. Reznichenko, V.A. Proskudina, G.Yu. Ovdii, О.М. Theoretical and applied aspects of relations and operations for sequences of time intervals |
| topic_facet |
UDC 004.62 УДК 004.62 |
| format |
Article |
| author |
Kudym, K.A. Reznichenko, V.A. Proskudina, G.Yu. Ovdii, О.М. |
| author_facet |
Kudym, K.A. Reznichenko, V.A. Proskudina, G.Yu. Ovdii, О.М. |
| author_sort |
Kudym, K.A. |
| title |
Theoretical and applied aspects of relations and operations for sequences of time intervals |
| title_short |
Theoretical and applied aspects of relations and operations for sequences of time intervals |
| title_full |
Theoretical and applied aspects of relations and operations for sequences of time intervals |
| title_fullStr |
Theoretical and applied aspects of relations and operations for sequences of time intervals |
| title_full_unstemmed |
Theoretical and applied aspects of relations and operations for sequences of time intervals |
| title_sort |
theoretical and applied aspects of relations and operations for sequences of time intervals |
| title_alt |
Теоретический и прикладной аспекты отношений и операций для последовательностей временных интервалов |
| description |
Prombles in programming 2013; 3: 61-68 |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2025 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/753 |
| work_keys_str_mv |
AT kudymka theoreticalandappliedaspectsofrelationsandoperationsforsequencesoftimeintervals AT reznichenkova theoreticalandappliedaspectsofrelationsandoperationsforsequencesoftimeintervals AT proskudinagyu theoreticalandappliedaspectsofrelationsandoperationsforsequencesoftimeintervals AT ovdiiom theoreticalandappliedaspectsofrelationsandoperationsforsequencesoftimeintervals AT kudymka teoretičeskijiprikladnojaspektyotnošenijioperacijdlâposledovatelʹnostejvremennyhintervalov AT reznichenkova teoretičeskijiprikladnojaspektyotnošenijioperacijdlâposledovatelʹnostejvremennyhintervalov AT proskudinagyu teoretičeskijiprikladnojaspektyotnošenijioperacijdlâposledovatelʹnostejvremennyhintervalov AT ovdiiom teoretičeskijiprikladnojaspektyotnošenijioperacijdlâposledovatelʹnostejvremennyhintervalov |
| first_indexed |
2025-07-17T09:43:13Z |
| last_indexed |
2025-07-17T09:43:13Z |
| _version_ |
1838409209629114368 |
| fulltext |
Експертні та інтелектуальні інформаційні системи
© К.А. Кудим, В.А. Резниченко, Г.Ю. Проскудина, О.М. Овдей, 2013
ISSN 1727-4907. Проблеми програмування. 2013. № 3 61
УДК 004.62
К.А. Кудим, В.А. Резниченко, Г.Ю. Проскудина, О.М. Овдей
ТЕОРЕТИЧЕСКИЙ И ПРИКЛАДНОЙ АСПЕКТЫ
ОТНОШЕНИЙ И ОПЕРАЦИЙ ДЛЯ
ПОСЛЕДОВАТЕЛЬНОСТЕЙ ВРЕМЕННЫХ ИНТЕРВАЛОВ
Рассмотрены понятия момента времени, временного интервала и временной цепочки ― последова-
тельности интервалов времени. Определены основные отношения и операции над этими объектами.
Приведены эффективные алгоритмы для реализации операций над временными цепочками. Рассматри-
вается практическое применение временных цепочек.
Введение
Данные в компьютерных системах
так или иначе связаны с различными
событиями, интервалами времени. Отно-
шения и операции над временными интер-
валами определены уже довольно давно и
широко используются [1–3]. В этой работе
исследуются такие структуры времени как
последовательности интервалов времени
или временные цепочки, которые можно
рассматривать как обобщение временных
интервалов. В работе определены отноше-
ния между временными цепочками, их
свойства, а также операции над ними.
Использование временных цепочек про-
иллюстрировано на практических приме-
рах. Разработаны эффективные алгоритмы
для реализации операций над временными
цепочками.
1. Представление времени и вре-
менные последовательности
Понятие времени в компьютерных
системах представляется как правило мо-
ментами времени либо временными ин-
тервалами. В дополнение к этим двум ба-
зовым представлениям введём ещё одно, а
именно временную цепочку или, другими
словами, последовательность временных
интервалов.
Момент времени – точка на оси
времени. Любое событие можно связать с
фактом возникновения, которому ставится
в соответствие момент времени.
Интервал времени – непустой от-
резок временной шкалы. Как правило
интервал времени задается моментами
начала и конца. Некоторое утверждение
или факт в предметной области может
быть действительным в течение опреде-
ленного интервала времени. То есть с ин-
тервалом может быть связан любой факт,
который имеет продолжительность своего
существования.
Временная цепочка – это упорядо-
ченное множество интервалов времени.
Интервал времени является частным слу-
чаем временной цепочки, состоящая лишь
из одного интервала. С помощью времен-
ной цепочки можно выразить, когда имел
место какой-либо факт или, другими сло-
вами, можно выразить истинность неко-
торого факта предметной области во вре-
мени. Например, в предметной области
«Отдел кадров» фиксируется факт «Чело-
век работает в отделе». Из приведенной
далее таблицы видно, что И.В. Петров ра-
ботал в отделе B1 два интервала времени,
т. е. можно сказать, что с этим фактом свя-
зана временная цепочка.
ФИО Отдел Дата
начала
Дата
конца
Петров
И.В
В1 22.06.2009 03.09.2010
Петров
И.В
В3 03.09.2010 01.02.2011
Петров
И.В
В1 01.02.2011 01.01.2013
Далее рассмотрим более формально
упомянутые выше базовые конструкции
времени.
Експертні та інтелектуальні інформаційні системи
62
2. Определения, отношения и
операции над элементами времени
2.1. Точка
Определение. Пусть P – дискрет-
ное линейно упорядоченное множество.
Назовём элементы данного множества
точками. Это могут быть: моменты време-
ни, целые числа и др. Точки будем обозна-
чать строчными буквами латинского алфа-
вита a, b, c, …
Отношения. a < b, a = b, a b …
Операции.
Сдвиг точки на n единиц: a + n.
2.2. Интервал
Определение. Пусть a, b ϵ P, тогда
если a < b, то
[a,b] = {x ϵ P: a≤x≤b};
[a,b) = {x ϵ P: a≤x<b};
(a,b] = {x ϵ P: a<x≤b};
(a,b) = {x ϵ P: a<x<b} ― интервалы.
Из данного определения видно, что
интервал может как включать, так и не
включать начальный и конечный момен-
ты времени, являясь таким образом закры-
тым [a,b], открытым (a,b), закрыто-откры-
тым [a,b) или открыто-закрытым (a,b] ин-
тервалом.
Интервал, не содержащий ни одной
точки, назовём пустым и обозначим [).
Множество интервалов обозначим R. Ин-
тервалы будем обозначать прописными
буквами латинского алфавита A, B, C, ....
Длина интервала ― это количество
точек, содержащихся в интервале либо ко-
личество единичных интервалов, состав-
ляющих интервал, и задается операцией:
length([a,b)) = b – a.
Определим операции для нахожде-
ния граничных точек.
Начало интервала: begin(A) = a, где
A=[a,b] ∨ A=(a,b] ∨ A=[a,b) ∨ A=(a,b).
Конец интервала: end([a,b)) = b, где
A=[a,b] ∨ A=(a,b] ∨ A=[a,b) ∨ A=(a,b).
Далее, для простоты изложения, мы
ограничимся только закрыто-открытым
интервалом A: [a,b) = {x ϵ P: a≤x<b}.
Отношения. Определим ряд полез-
ных отношений между точкой и интерва-
лом и между двумя интервалами.
Точка-интервал
1. Точка x находится до интервала
А: x < A ⇔ x < begin(A).
2. Точка a – начальная точка интер-
вала A: Begin(A, a) ⇔ begin(A)=a.
3. Точка b – конечная точка интер-
вала A: End([A,b) ⇔ end(A)=b.
Интервал-интервал
Дж. Аллен показал [1–2], что между
двумя непустыми интервалами времени
существует 13 основных бинарных отно-
шений или предикатов взаимного распо-
ложения интервалов друг относительно
друга, которые сейчас так и принято назы-
вать отношениями Аллена.
1. Интервал А находится перед ин-
тервалом B:
A before B ⇔ A < B ⇔ end(A) < begin(B).
Из этого отношения вытекает сле-
дующее свойство:
A before B ⇒ ∃C ϵ R, C ≠
≠ [):A meets C meets B.
2. Интервал A находится после ин-
тервала B:
A after B ⇔B before A ⇔B < A ⇔
⇔ end(B) < begin(A).
3. Интервал A равен интервалу B:
A equals B ⇔ A = B ⇔
⇔ begin(A) = begin(B) & end(A) = end(B).
4. Интервал B следует непосред-
ственно за A (или: интервал B касается ин-
тервала A справа):
A meets B ⇔ end(A) = begin(B).
Експертні та інтелектуальні інформаційні системи
63
5. Интервал A следует непосред-
ственно за B (или: интервал A касается ин-
тервала B справа):
A met_by B ⇔B meets A ⇔ end(B) =
= begin(A).
6. Интервал B перекрывает интер-
вал A:
A overlaps B ⇔
⇔ begin(A) ≤ end(B) & begin(B) ≤ end(A).
7. Интервал A перекрывает интер-
вал B:
A overlapped_by B ⇔ B overlaps A⇔
⇔ begin(B) ≤ end(A) & begin(A) ≤ end(B).
8. Интервал A находится в интерва-
ле B (или интервал В содержит интервал
А):
A during B ⇔ A ⊆ B ⇔
⇔ begin(B) ≤ begin(A) & end(A) ≤ end(B).
9. Интервал B находится в интерва-
ле A (или интервал A содержит интервал
B):
A contains B ⇔ B during A ⇔ B ⊆ A.
10. Интервал A начинается одно-
временно с интервалом В:
A starts B ⇔ begin(A) = begin(B).
11. Интервал В начинается одно-
временно с интервалом А:
A started_by B ⇔ begin(B) = begin(A).
12. Интервал A заканчивается од-
новременно с интервалом В:
A finishes B ⇔ end(A) = end(B).
13. Интервал В заканчивается од-
новременно с интервалом А:
A finished_by B ⇔ end(B) = end(A).
Перечисленные отношения для
удобства можно комбинировать. Напри-
мер, часто используют следующее отно-
шение.
Два интервала либо соприкасаются
либо пересекаются:
Merges(A,B) ⇔ ¬(A before B) & ¬(B before A) ⇔
⇔ ¬(A < B) & ¬(B < A) ⇔
⇔ ¬(end(A) < begin(B))&¬(end(B) <
begin(A)) ⇔
⇔ begin(B) ≤ end(A) & begin(A) ≤ end(B).
Операции над интервалами. Вы-
ше были приведены операции для нахож-
дения длины интервала и нахождения гра-
ничных точек. Часто для интервалов также
используются операции объединения, пе-
ресечения, разности и сдвига:
1. Объединение двух интервалов:
A∪B=[min(begin(A),begin(B)),
max(end(A),end(B))), если Merges(A,B), в
противном случае не определено.
2. Пересечение двух интервалов:
A ⋂ B=[max(begin(A),begin(B)),
min(end(A),end(B))), если A overlaps B; в
противном случае не определено.
3. Разность двух интервалов A – B
равна:
[begin(A), min(begin(B), end(A))),
если begin(A)<begin(B) & end(A) ≤ end(B);
либо равна:
[max(end(B), end(A)), end(A))),
ли begin(A) ≥ begin(B) & end(A) > end(B),
в противном случае не определено.
4. Сдвиг интервала:
A + n = [begin(A)+n, end(A)+n).
Однако, рассматриваемые операции
не являются замкнутыми относительно ин-
тервалов времени. Объединение двух не-
пересекающихся интервалов возвращает
два интервала. Разность двух интервалов
может возвратить пустое множество, один
или два интервала.
Експертні та інтелектуальні інформаційні системи
64
2.3. Цепочка
Определение. Последоватьльность
непустых интервалов назовём цепочкой,
если для любых двух соседних её интерва-
лов найдётся непустой интервал, лежащий
между ними. Формально:
α = <A1, ..., An>, где Ai ϵ R, Ai ≠ [), и для
i=1…n-1 Ai before Ai+1.
Цепочку, не содержащую ни одного
интервала, назовём пустой и обозначим <>.
Множество всех цепочек обозначим C.
Отношения. Пусть α и β цепочки,
A, Ai ,B ,Bi непустые интервалы, a точ-
ка. Введем следующие отношения:
1. Интервал в цепочке:
A ϵ α ⇔ α=<A1,...,An> & ∃i: A = Ai
2. Точка принадлежит цепочке:
a ϵ α ⇔ ∃A ϵ α: a ϵ A
3. Первый интервал цепочки:
First(α, A) ⇔ α=<A, B1,...,Bn>
4. Последний интервал цепочки:
Last(α, A) ⇔ α=<B1,...,Bn, A>
5. Цепочка α предшествует цепочке β:
α < β ⇔ last(α) < first(β)
6. Интервал B входит в цепочку α:
B⊆<A1,A2,..An> ⇔ B⊆A1 ∨ B⊆A2 ∨ ...
∨ B⊆An
7. Цепочка β=<B1,...,Bn-1> дополняет цепочку
α=<A1,...,An> ⇔ A1 meets B1 meets A2 meets B2
meets ... meets Bn-1 meets An
Свойство: β дополняет α ⇒
α+β=<A1+B1+A2+B2+...+Bn-1+An>
8. Цепочка β входит во все интервалы цепочки
α: B1⊆<A1 & B2⊆A2 &.. & Bn⊆An
9. Цепочка β перекрывает все промежутки це-
почки α: A α, B β: A overlaps B
α
A
α
a
α
A
α
A
α
β
α
B
α
β
α
β
α
β
Експертні та інтелектуальні інформаційні системи
65
Далее определим ряд полезных от-
ношений для цепочек:
Операции над цепочками
1. Возвращает первый интервал це-
почки:
first(α) = A: First(α, A).
2. Возвращает последний интервал
цепочки:
last(α) = A: Last(α, A).
2a. Мощность:
cardinality(α) = n для α = <A1,...,An>.
2b. kth(α,k) = Ak для
α =<A1,...,Ak,...,An>, если 1 ≤ k ≤
length(α);
в противном случае не определено.
2c. Протяжённость цепочки:
length(α) = length(Ai).
2d. Охват цепочки или общая длина
от начала первого интервала до конца по-
следнего:
coverage(α) = end(An) ― begin(A1).
3. Объединение цепочки с пустой
цепочкой: α ∪ <> = α.
3a. <[)> = <>.
4. Объединение двух цепочек, одна
из которых состоит из одного интервала:
<A1,...,An> ∪ <B> =
=<A1,...,Ak,[min(begin(Ak+1),begin(B)),
max(end(Al―1),end(B))],Al,...,An>,
где k=argmax[Ai<B](end(Ai)),
l = argmin[B<Ai](begin(Ai)).
5. Объединение двух цепочек:
α ∪ <B1, B2, ..., Bn> = (α ∪ <B1>) ∪
∪ <B2,..., Bn>.
Свойство: α∪α = α.
6. Пересечение цепочки с элемен-
тарной цепочкой:
<A1,...,An>∩<B> = <A1∩B> ∪ ...
... ∪ <An∩B>.
7. Пересечение двух цепочек:
α∩<B1,...,Bn> = (α∩B1)∪...∪(α∩Bn).
8. Разность цепочки и элементарной
цепочки:
<A1,...,An> ― <B> = <A1 ― B> ∪ ...
... ∪ <An ― B>.
9. Разность двух цепочек:
Α ― <B1,...,Bn> = (α ― B1)∪...∪(α ― Bn).
10. Сдвиг цепочки:
α + n = <A1 + n, ..., An + n>
11. Периодическая цепочка:
(α,n)* = ... ∪(α-2n)∪
∪ (α-n)∪α∪(α+n)∪(α+2n)+...
Из приведенных определений сле-
дует, что все рассматриваемые операции
относительно цепочек, в отличие от ана-
логичных операций относительно интер-
валов, являются замкнутыми, т. е. в ре-
зультате дают цепочку.
3. Примеры использования
цепочек данных
Представим факт «Человек работает
в отделе» из приведенного выше примера
(см. раздел 1.) в виде цепочек интервалов.
ФИО Отдел Время работы
Петров
И.В.
В1 <[1998,2001), [2010,2012)>
Петров
И.В.
В3 <[1996–1998), [2002–
2006), [2007–2010)>
Иванов
И.И.
В1 <[1996,2000)>
Приведем примеры операций над
цепочками данных, дающих ответы на со-
держательно сформулированные запросы с
использованием этой структуры данных.
1. Когда Петров работал в отделе
В1?
α = <[1998,2001), [2010,2012)>.
2. Когда Петров не работал в отде-
ле В1?
α=<[1800,2013)> - <[1998,2001), [2010,2012)>=
= <[1800,1998), [2001,2010), [2012,2013)>.
3. Когда Петров и Иванов работали
вместе в отделе В1?
α=<[1996,2000)>∩<[1998,2001),[2010,2012)>=
= <[1998,2000)>.
4. Когда Петров или Иванов рабо-
тал в отделе В1?
α=<[1996,2000)>∪<[1998,2001),[2010,2012)>=
Експертні та інтелектуальні інформаційні системи
66
= <[1996,2001), [2010,2012)>.
Другой пример использования це-
почек: регистрация факта пребывания
пользователя на сайте Х.
α=<[2013-04-14 09:02:33, 2013-04-14 12:22:35),
[2013-04-15 16:02:33, 2013-04-15 16:22:35),
[2013-04-15 18:12:33, 2013-04-15 18:32:33)>
В этом случае, используя операцию
протяженности цепочки length(α), можно
легко ответить на следующий запрос:
Cколько Сидоров провел времени
на сайте Х?
4. Алгоритмы операций над це-
почками
Цепочку <A1,...,An> представим
массивом M[1..n]. Интервал A представим
парой целых чисел [A.begin, A.end). Q –
большое число.
На рис. 1, 2, 3 соответственно по-
казаны алгоритмы выполнения операций
объединения, пересечения и дополнения
данных, имеющих тип цепочка.
Сложность алгоритма линейная: если
C1.length = n, C2.length = m, то сложность
алгортима O(n+m).
CHAIN_UNION(M1, M2, M)
i ← 1
j ← 1
k ← 0
in1 ← false
in2 ← false
while true
do if i ≤ M1.length
then A1 ← M1[i]
else A1.begin ← Q, A1.end ← Q
if i ≤ M2.length
then A2 ← M2[i]
else A2.begin ← Q, A2.end ← Q
if A2.begin = Q and A1.begin = Q
then return
if in1 and in2
then if A1.end ≤ A2.end
then in1 ← false, B.end ← A1.end, i ← i+1
if A2.end ≤ A1.end
then in2 ← false, B.end ← A2.end, j ← j+1
if A1.end = A2.end
then k ← k+1, M[k] ← B
else if in1 and not in2
then if A1.end ≤ A2.begin
then in1 ← false, i ← i+1, k ← k+1, M[k] ← B
if A2.begin ≤ A1.end
then in2 ← true
else if not in1 and in2
then if A1.begin ≤ A2.end
then in1 ← true
if A2.end ≤ A1.begin
then in2 ← false, j ← j+1, k ← k+1, M[k] ← B
else if not in1 and not in2
then if A1.begin ≤ A2.begin
then in1 ← true, B.begin ← A1.begin
if A2.begin ≤ A1.begin
then in2 ← true, B.begin ← A2.begin
M.length = k
Рис. 1. Алгоритм объединения двух цепочек
Експертні та інтелектуальні інформаційні системи
67
CHAIN_INTERSECTION(M1, M2, M)
i ← 1
j ← 1
k ← 0
in1 ← false
in2 ← false
while true
do if i ≤ M1.length
then A1 ← M1[i]
else A1.begin ← Q, A1.end ← Q
if i ≤ M2.length
then A2 ← M2[i]
else A2.begin ← Q, A2.end ← Q
if A2.begin = Q and A1.begin = Q
then return
if in1 and in2
then if A1.end ≤ A2.end
then in1 ← false
i ← i+1, B.end ← A1.end
if A2.end ≤ A1.end
then in2 ← false
j ← j+1, B.end ← A2.end
k ← k+1, M[k] ← B
else if in1 and not in2
then if A1.end ≤ A2.begin
then in1 ← false, i ← i+1
if A2.begin ≤ A1.end
then in2 ← true, B.begin ← A2.begin
else if not in1 and in2
then if A1.begin ≤ A2.end
then in1 ← true, B.begin ← A1.begin
if A2.end ≤ A1.begin
then in2 ← false, j ← j+1
else if not in1 and not in2
then if A1.begin ≤ A2.begin
then in1 ← true
if A2.begin ≤ A1.begin
then in2 ← true
if A1.begin = A2.begin
then B.begin ← A1.begin
M.length = k
Рис. 2. Алгоритм пересечения двух цепочек
CHAIN_COMPLEMENT(M1, M2, M)
i ← 1
j ← 1
k ← 0
in1 ← false
in2 ← false
while true
do if i ≤ M1.length
then A1 ← M1[i]
else A1.begin ← Q, A1.end ← Q
if i ≤ M2.length
then A2 ← M2[i]
else A2.begin ← Q, A2.end ← Q
if A1.begin = Q and A2.begin = Q
Експертні та інтелектуальні інформаційні системи
68
then return
if in1 and in2
then if A1.end ≤ A2.end
then in1 ← false, i ← i+1
if A2.end ≤ A1.end
then in2 ← false, j ← j+1, B.begin ← A2.end
else if in1 and not in2
then if A1.end ≤ A2.begin
then in1 ← false, i ← i+1, B.end ← A1.end
if A2.begin ≤ A1.end
then in2 ← true, B.end ← A2.begin
k ← k+1, M[k] ← B
else if not in1 and in2
then if A1.begin ≤ A2.end
then in1 ← true
if A2.end ≤ A1.begin
then in2 ← false, j ← j+1
if A1.begin = A2.end
then B.begin = A1.begin
else if not in1 and not in2
then if A1.begin ≤ A2.begin
then in1 ← true, B.begin ← A1.begin
if A2.begin ≤ A1.begin
then in2 ← true
M.length = k
Рис. 3. Алгоритм дополнения двух цепочек
Заключение
Использование временных интерва-
лов в программировании достаточно под-
робно изучено. Временные цепочки можно
рассматривать как обобщение временных
интервалов. В работе определены отноше-
ния между временными цепочками, их
свойства, а также операции над ними. В
работе показано, что в отличии от опера-
ций над интервалами операции над цепоч-
ками замкнуты, что снимает ряд ограниче-
ний и тем самым упрощает их использова-
ние. Разработаны эффективные алгоритмы
для реализации операций над временными
цепочками. Рассмотрены примеры их
практического использования. Таким обра-
зом предложена эффективная структура
для хранения и манипулирования темпо-
ральными данными.
1. James F. Allen Maintaining knowledge about
temporal intervals // Communications of
ACM. – 1983. – Vol. 26. – N 11.
2. James F. Allen Towards a General Theory of
Action and Time // Artificial Intelligence. –
1984. – N 23. – P. 123–154.
3. Richard Snodgrass. Developing Time-
Oriented Database Applications in SQL,
Morgan Kaufmann, 1999.
Получено 10.01.2013
Об авторах:
Кудим Кузьма Алексеевич,
младшний научный сотрудник,
Резниченко Валерий Анатольевич,
ведущий научный сотрудник,
Проскудина Галина Юрьевна,
научный сотрудник,
Овдей Ольга Михайловна,
младший научный сотрудник.
Место работы авторов:
Институт программных систем
НАН Украины,
03187, Киев-187,
Проспект Академика Глушкова, 40.
Тел. +38(044)526 6033
е-mail: reznich@isofts.kiev.ua
kuzmaka@mail.ru
gupros@isofts.kiev.ua
olga.ovdiy@gmail.com
|