Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

предикат тейз реляционный программный

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

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

В последние годы одним из интереснейших направлений в разработке систем ИИ является рассмотрение процессов интеллектуальной деятельности человека во времени. Время не случайно столь приоритетно в исследованиях в области искусственного интеллекта: и в человеческих рассуждениях фактор времени является одним из основополагающих. Образ так называемой «временной оси» глубоко заложен в человеческое понимание окружающего мира. Каждый наверняка замечал, что все наши воспоминания мы строим на воображаемой временной оси, и часто нам приходится восстанавливать произошедшие события в хронологическом порядке. Человеческая способность выстроить события на временной оси очень сильна, и для большинства людей, не обладающих способностями абстрактного мышления, является единственным способом представления происходящих событий.

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

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

1) Необходим язык для описания того, что истинно или ложно в каждый момент времени, что изменяется, а что остается постоянным.

2) Необходимо определение правил «законных изменений» (изменений, подчиняющихся определенному закону) в вышеуказанном языке, учитывающих возможные изменения во времени.

В ИИ можно определить несколько классов задач, при решении которых требуется учет временного фактора, основные из которых можно охарактеризовать следующим образом [1]:

1. Задача предсказания: У нас имеются описания окружающего мира в определенный период времени и правила, которые применяются к ситуациям, возникающим при изменениях окружающего мира (Например, известны траектории движения бильярдных шаров, необходимо предсказать момент их столкновения и его последствия.)

2. Задача объяснения: Пусть дано описание окружающего мира в какой-то период времени, а так же критерии «законных изменений» происходящих процессов. Необходимо дать описание мира в некий момент времени, предшествующий данному, которое привело окружающий мир в текущее состояние. (Например, сидя в бильярдной и услышав громкий шум удара, можно сделать предположение, что в предшествующий момент произошло столкновение двух шаров.)

3. Задача планирования: Пусть дано описание какого-то состояния, в которое необходимо перевести окружающий мир в некоторый момент времени, и описание «законных изменений». Необходимо произвести последовательные действия, переводящие мир в желаемое состояния. (Например, желая забить бильярдный шар в лунку, необходимо ударить по нему другим шаром под определенным углом.)

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

Хотя очевидно, что данные классы задач тесно взаимосвязаны, в ИИ поиск решения подобных проблем привел к возникновению множества различных направлений исследований.

Учитывая важность и перспективность направлений в области ИИ, связанного с учетом фактора времени, в дипломной работе исследуются вопросы представления времени в интеллектуальных системах. Основное внимание уделяется учету временной информации при разработке баз данных, а именно, в работе будет рассмотрена темпоральная (временная) модель данных (ТМД), являющаяся расширением реляционной модели данных на случай оперирования темпоральной информацией, а так же временная алгебра. В качестве модельного примера будет разработана база данных для обслуживания сферы консалтинга, ведущая учет всех компаний-клиентов, сотрудников компаний, проектов, ежемесячной прибыли и доходов, зарплат и должностей. Реализация будет проведена средствами программного обеспечения СУБД MYSQL с использованием удобного инструмента для визуального проектирования БД - My SQL Workbench. Кроме того, для реализации методов темпоральной алгебры будет использован объектно-ориентированный язык программирования Java и фреймворк Hibernate. Он позволяет обращаться с реляционной БД с помощью запросов «Criteria» как с обычными объектами ООП.

Основная сложность в решении поставленной задачи заключается в том, что на сегодняшний день данное направление не является достаточно изученным. Несмотря на многочисленные исследования и разработки таких крупных организаций, как Oracle и Microsoft, еще не появилось коммерческой реализации темпоральной системы управления базами данных (СУБД), однако предложены различные расширения, позволяющие обрабатывать временные данные. Кроме того, ощущается недостаток публикаций по данному вопросу на русском языке.



1. Основные подходы к учету фактора времени при разработке систем ИИ

1.1 Основные свойства времени

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

В памяти человека сведения об окружающем мире и возможных действиях в нем упорядочены не только различными классифицирующими и ситуативными отношениями. Для фиксации соотношений любых отдельных информационных единиц она использует различные шкалы. Так, существуют метрические шкалы (установление количественного соотношения и порядка тех или иных совокупностей информационных единиц), порядковые шкалы (фиксация лишь порядка информационных единиц), оппозиционные шкалы (образуются с помощью пар слов - антонимов) и пр. Важно отметить, что для времени возможны два способа шкалирования. Один из них отражает упорядочение событий на шкале: прошлое - настоящее - будущее, а другой на шкале типа раньше - позже. Каждое событие на первой шкале в процессе эволюции как бы перемещается по ней. Если в какой-то начальный момент оно было расположено в будущем, то изменяясь или приближаясь, возникает в настоящем, а потом уходит в прошлое, оставаясь там навсегда. Если же оно не реализуется в настоящем, то исчезнет из шкалы. На шкалах второго типа (к ним относится подавляющее большинство шкал, используемых для времени) события располагаются в неизменном порядке. Это как бы застывшая шкала «уже произошедшего».

По тому, как события отражены на шкалах, мы будем различать два типа временных систем: А-система и В-систем. Обе они должны быть реализованы в интеллектуальных системах. Логики времени, связанные с ними, несколько различаются.

Перейдем к основным свойствам времени, используемых в теории интеллектуальных систем для осуществления взаимодействия системы с окружающим миром [2].

1. Направленность

Основное назначение времени, реализуемое в А-системах - фиксация направления его изменения из прошлого через настоящее в будущее, ориентация течения событий, процессов, действий или замещающих их «кусков времени» - ТЕМПОРов. Время в В-системах также фиксирует направление, определяющее семантику отношений следования для ТЕМПОРов или тех элементов, которые они замещают.

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

2. Линейность

Чаще всего время представляется в виде некоего множества (на котором задано отношение нестрогого порядка), обуславливающего справедливость отношения транзитивности для ТЕМПОРов и замещаемых ими элементов. В основном в литературе рассматриваются логики, для которых выполняется свойство линейности.

Однако, можно представить себе и такие модели времени, в которых свойство линейности нарушается. Например, трактуя в А-системах будущее развитие интересующих нас событий, можно исследовать различные альтернативные последовательности их реализации или в более общем случае ТЕМПОРов. Ибо будущее еще не наступило и оно носит модальный характер. Будущее время как бы ветвится по альтернативным последовательностям событий или ТЕМПОРов. Конечно, свойство транзитивности здесь может нарушаться. Такое «ветвление» характерно, например, для моделей психологического времени.

3. Непрерывность

Стало стандартом представлять время в виде одномерного континуума, геометрическим образом которого служит прямая. Фундаментальное свойство, вытекающее из непрерывности, заключается в том, что для любых двух ТЕМПОРов или замещаемых ими элементов, строго упорядоченных в одномерном континууме, всегда найдется ТЕМПОР, который будет лежать (с точки зрения строгой упорядоченности) между этими двумя ТЕМПОРами.

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

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

4. Неоканчиваемость

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

5. Гомогенность

Для человека время, как таковое, обладает свойством однородности. Любой момент времени, любой его интервал, любая цепь из точек и интервалов времени (т.е. любой ТЕМПОР) никак не меняются, если их перемещать по шкале времени. Однако, гомогенность времени нарушается в системах с датированием, где отдельные участки временной шкалы снабжаются маркерами - датами, различными для разных участков шкалы. Учитывая важность систем датирования, в дальнейшем мы будем использовать свойство гомогенности времени в ограниченном понимании и только в случаях, когда временные рассуждения не опираются на какие-либо маркеры (в частности даты) на временной шкале. Особенно сильно свойство гомогенности нарушается в моделях психологического времени.

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

Процесс разработки альтернативных логик аналогичен процессу построения моделей в геометрии. Отказ от знаменитого пятого постулата Евклида привел к геометриям Лобачевского и Римана. Отказ от того или иного свойства времени приводит к временной логике с новыми свойствами. И как геометрия Лобачевского оказалась способной отразить особенности пространства в пределах космоса, так и временные модели, свойства которых кажутся нам неестественными (например, время, как оно представляется в теории относительности), могут описывать некие свойства действительности или субъективного мира человека.

1.2 Способы представления времени

Предположим, что мы хотим представить каким-то образом информацию о том, что конкретный дом, например ДОМ17 был КРАСНОГО цвета в момент времени t. В связи с этим возникает несколько вопросов.

Первым необходимо решить вопрос о том, что на самом деле представляет собой t: это временная точка, интервал времени или, может быть, некая более сложная сущность? Существуют различные виды утверждений, некоторые из которых интерпретируются с помощью временных точек, другие - с помощью временных интервалов, иные - с помощью наборов непересекающихся интервалов и т.д. В исследованиях по ИИ можно найти ответ на этот вопрос. В изначально предложенной A. Pnueli [3] формализации модальной временной логики и предложенной V. Pratt [4] динамической логики утверждения интерпретировались с помощью временных точек. Позднее появилось несколько обобщений подобных систем (Nisihmura [5]), в которых использовались оба понятия: «утверждения с временными точками» и «утверждения с временными интервалами». В последнее время в ИИ наблюдается определенное движение в сторону более однородных логик, основанных на понятии интервала. В ИИ можно обнаружить системы всех 3-х типов: основанные на понятии точки, интервала и смешанные.

Возникает еще один вопрос: что выбрать в качестве основного темпорального элемента в наших рассуждениях о сущности времени. Можно, конечно, рассматривать различные возможности, но все же основными являются интервалы и точки. Интервалы могут считаться примитивными объектами, связанными между собой различными способами: «I1 полностью перед I2», «I1 граничит с I2», «I1 и I2 перекрываются» и т.п. Если принимается данный способ представления, все еще возможно говорить о временных точках, представляя их с помощью примитивных объектов, а именно определяя временную точку как результат некой операции над интервалами, например, пересечение бесконечного множества интервалов [6]. В качестве альтернативы предыдущему способу представления можно взять за примитивные объекты точки, причем единственным возможным отношением между двумя точками (кроме идентичности) может быть следующее: «P1 предшествует Р2». В данном случае интервал можно представить с помощью упорядоченной пары точек (начальная и конечная точки), такой, что первая точка либо предшествует второй, либо совпадает с ней (таким образом, точка Р представляется с помощью интервала {Р, Р}). Сторонники выбора в качестве основного примитивного элемента интервала, а не точки, основываются на интуитивных соображениях о несколько искусственной природе точек и более естественной для человека природе интервалов.

Еще один важный вопрос, который возникает в связи с проблемой представления времени, - существует ли какая-либо связь между истинностью утверждения на интервале и его истинностью на отдельных участках интервала. Обычно задается вопрос о том, являются ли интервалы «открытыми» или «закрытыми». На самом деле, такой вопрос не имеет смысла. Если интервал определяется как упорядоченная пара точек, а не множество точек, то нет смысла спрашивать о том, является ли Р1 элементом {Р1, Р2}. Далее возникает вопрос: является ли сделанный нами вывод действительно корректным, распространяются ли принимаемые на интервале истинностные значения на все подинтервалы данного интервала? Перенесение истинностных значений с интервала на его подинтервалы в утверждениях типа «ДОМ17 красного цвета» кажется абсолютно логичным, однако, оно оказалось бы неприемлемым для следующих утверждений: «я пробежал более пяти миль», «робот выполнил процедуру поиска от начала до конца». Самым популярным подходом к разрешению подобных недоразумений считается различение разных типов сущностей: первое утверждение представляло собой «факт» или «свойство», а другие являлись «событиями».

Таким образом, при разработке новых формализмов для интерпретации времени возможно использование любой комбинации признаков в зависимости от цели разработки того или иного формализма.

Итак, рассмотрим более подробно два наиболее распространенных в настоящее время в ИИ формализма: интервальный подход Allen [7] и точечный подход MсDermott [8].

Темпоральная логика, основанная на интервальном представлении времени

Темпоральную интервальную логику предложил Аллен в начале 80-х годов [7]. В качестве временных примитивов в ней используются интервалы, а не временные точки.

Здесь заглавными буквами обозначены предикаты и константы, а строчными переменные. Кроме того, будем использовать набор связок и квантификаторов в их стандартной интерпретации, а именно:

- конъюнкция, ? - дизъюнкция, ? - отрицание, - импликация, - эквивалентность, - квантор общности, - квантор существования, ! - квантор существования и единственности.

Временной интервал X - это упорядоченная пара (X-, X+), такая что, X- < X+, где X- и X+ рассматриваются как моменты времени (например, на вещественной оси). Структура времени может быть любая (необходимая в конкретной ситуации). Временные точки рассматриваются как очень маленькие временные интервалы. Построены варианты этой логики с ветвящейся структурой времени [Reich A., 1994].

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

Рассматриваемая логика является типизируемой логикой исчисления предикатов первого порядка, в которой термы подразделяются на множество категорий. В настоящий момент рассмотрим три из этих категорий:

- термы типа TIME-INTERVAL, обозначающие интервалы времени

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

- термы, соответствующие объектам в домене.

Мы так же рассмотрим несколько предикатов. Одним из наиболее важных является предикат HOLDS, который отражает утверждение о том, что некоторое свойство сохраняется (т.е. является истинным) на определенном временном интервале. Таким образом, HOLDS (p, t) истинен в том и только том случае, если свойство р сохраняется на временном интервале t. Следствием этого является аксиома о том, что свойство р сохраняется также и на каждом подинтервале интервала t.

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

Рассмотрим пример. DURING (t1, t2): временной интервал t1 полностью содержится внутри временного интервала t2, STARTS (t1, t2): временной интервал t1 начинается тогда же, когда и временной интервал t2, однако заканчивается раньше, чем заканчивается t2 и т.д.



Табл.1. Множество базовых интервальных отношений

Теперь имея вышеуказанные предикаты, необходимо отметить, что существует ряд аксиом, определяющих их поведение. Во-первых, имея интервал I, можно сказать, что существуют интервалы, связанные с I каждым из вышеперечисленных отношений. Мы также располагаем аксиомами, утверждающими, что каждое из отношений является взаимно исключающим все остальные, а также большим набором аксиом, описывающих транзитивность поведения. Приведем пример:

BEFORE (t1, t2) BEFORE (t2, t3) BEFORE (t1, t3) (1.1)

MEETS (t1, t2) DURING (t2, t3) (OVERLAPS (t1, t3) ?

DURING (t1, t3) ? MEETS (t1, t3)) (1.2)

Будет полезно определить предикат, который подытоживал бы отношения, в которых один интервал полностью содержится в другом. Определим IN следующим образом:

IN (t1, t2) (DURING (t1, t2) ? STARTS (t1, t2) ? FINISHES (t1, t2)) (1.3)

Используя это предикат, можно ввести в рассмотрение первое решающее свойство предиката HOLDS: если свойство р сохраняется на интервале Т, то оно сохраняется на всех его подинтервалах интервала Т, т.е.:

HOLDS (p, T) ( t. IN (t, T) HOLDS (p, t)). (1.4)

Например, если в течение 2015 года у меня была машина, то, следовательно, я владел машиной в январе 2015, в феврале 2015 и т.д.

На самом деле оказывается, что в дальнейшем нам необходима более сильная аксиома. Она будет представлена ниже (1.5), несмотря на то, что (1.4) может быть выведена из нее и свойств отношения IN.

HOLDS (p, T) t. IN (t, T) ( s. IN (s, t) HOLDS (p, t)). (1.5)

Чтобы записывать сложные логические выражения существует набор функций вида and, or, not, all, exists, соответствующих логическим операторам , ?, ?, , , причем это соответствие можно отразить следующим образом.

Конъюнкция легко может быть определена для предиката HOLDS:

HOLDS (and (p, q), t) HOLDS (p, t) HOLDS (q, t) (1.6)

Отрицание определяется так:

HOLDS (not (p), T) ( t. IN (t, T) ?HOLDS (p, t)). (1.7)

Последнее отличается от ?HOLDS (p, Т), что по аксиоме (1.4) эквивалентно следующему:

?( t. IN (t, T) HOLDS (p, t)),

что, в свою очередь, эквивалентно следующему:

t. IN (t, T) ?HOLDS (p, t).

Таким образом, последнее означает, что существует по крайней мере один подинтервал, на котором р не сохраняется, в то время как предыдущее означает, что р не сохраняется ни на одном из подинтервалов Т.

Используя вышеприведенные определение, мы можем доказать следующее:

HOLDS (not (p), T) ?HOLDS (p, T). (1.8)

Также, используя (1.4) и (1.2), можно вывести следующее:

HOLDS (not (not (p)), T) HOLDS (p, T), (1.9)

чего мы и ожидали интуитивно. Отражая аналогичным образом обычное определение дизъюнкции для определения функции «or», т.е.,

HOLDS (or (p, q), t) ? HOLDS (not (and (not (p), not (q))), t),

можно вывести следующее:

HOLDS (or (p, q), T) t. IN (t, T) ( s. IN (s, t) (HOLDS (p, s) ? HOLDS (q, s))). (1.10)



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

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

В дальнейшем на основных принципах описанной темпоральной логики могут быть представлены события и действия.

Темпоральная логика, основанная на точечном представлении времени

В данном разделе мы кратко остановимся на основных понятиях темпоральной логики, использующей подход предложенный McDermott [8].

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

Для отражения вышеуказанных основных идей рассматривается бесконечный набор состояний окружающего мира. Состояние представляет собой моментальный «слепок» окружающего мира. Состояния представляются частично упорядоченными с помощью отношения «=<». Для обозначения того факта, что состояние s1 было раньше состояния s2 или идентично ему будем использовать запись вида: (=< s1 s2). Для написания логических формул используется т.н. «польская нотация». Каждый терм, атомарная формула или их комбинация записываются в виде (р…), где р есть предикат, функция или связка. Оставшаяся часть формулы (после р) есть аргументы или другие составные части. Если р - квантор существования или общности, то в качестве составных частей выступают список переменных и формула:

(forall (-vars-) fmla)

(exists (-vars-) fmla)

Для других связок составные части формул можно отразить в следующем виде:

(not fmla)

(if fmla1 fmla2)

(and fmla1 fmla2…)

(or fmla1 fmla2…)

(iff fmla1 fmla2)

Если р - бинарное транзитивное отношение, то (p w x y … z) есть сокращенная запись для (and (p w x) (p x y) … (p … z)).

Аксиома 1: (iff (and (=<? s1? s2) (=<? s2? s1)) (=? s1? s2))

(iff (<? s1? s2) (and (=<? s1? s2) (not (=? s1? s2))))

Если (=< s1 s2) и s1, s2 различны, будем писать (< s1 s2).

Аксиома 2: (Плотность)

(forall (s1 s2) (if (< s1 s2) (exists (s) (and (< s1 s) (< s s2)))))

Аксиома 3: (Транзитивность)

(forall (s1 s2 s3) (if (and (=< s1 s2) (=< s2 s3)) (=< s1 s3)))

Отметим, что рассматривается типизированная логика. Так, переменные, начинающиеся с s, означают состояния. Это означает, что (forall (x) p), где x - типизированная переменная, есть сокращенная запись для:

(forall (x) (if (is sort x) p)),

sort - так называемый sort или «тип данных». По сути дела они не слишком важны, а лишь помогают сохранить определенную «типизацию» структуры. Мы можем читать запись вида: (forall (s)…) как «для всех состояний…», не упоминая явно, что условия, что s является состоянием (is STATE s).

Неограниченные переменные (пишутся с? в начале) универсально квантифицируемы, т.е. их действие распространяется на всю формулу.

Каждое состояние имеет время происхождения, обозначаемое действительным числом и называемое датой. Функция d возвращает дату состояния, как, например, в формуле (= (d s1) D1). Любое действительное число является корректной датой: время же по своей сути бесконечно и не имеет циклов. Это означает, что 2 состояния будут иметь сравнимые даты, даже если они не являются связанными отношением =<. Будем использовать =< и < для обозначения обычного числового упорядочения, а также частичного упорядочения состояний, поскольку используемые sorts устраняют всякую двусмысленность в данном вопросе. Переменные, начинающиеся с «r» или «t» означают действительные числа.

Два вида упорядочения сравнимы:

Аксиома 4: (if (< s1 s2) (< (d s1) (d s2)))

Состояния объединяются в т.н. «хронологии». Хронология есть полная возможная история мира, полностью упорядоченное множество состояний, бесконечно расширяющееся во времени.

Аксиома 5: (Определение хронологии)

(iff (if CHRONICLE? x)

(and; множество состояний

(forall (y) (if (elt y? x) (is STATE y)))

; полностью упорядочено

(forall (s1 s2) (iff (and (elt s1? x) (elt s2? x))

(or (< s1 s2) (> s1 s2) (= s1 s2))))

; бесконечно во времени

(forall (t) (exists(s) (and (elt s? x) (= (d s) t))))))

(elt a x) означает, что а является элементом множества х. Прямым следствием аксиомы 5 является тот факт, что хронология является «выпуклой»:

(if (is CHRONICLE? x)

(forall s1 s2) (if (and (elt s1? x) (elt s2? x))

(forall (s) (if (< s1 s s2) (elt s? x)))))

Определив хронологию х (is CHRONICLE x), мы можем объявлять переменные, начинающиеся с «ch» переменными sort «CHRONICLE».

Хронология есть способ возможного развития событий. Согласно нашей логике, может быть несколько возможных путей развития событий (Рис. 1).

Каждое состояние входит в какую-то хронологию. Действительно:

Аксиома 6: (if (=<? s1? s2) (exists (ch) (and (elt? s1 ch) (elt? s2 ch))))

где, согласно свойству «выпуклости», каждое состояние между? s1 и? s2 входит в хронологию ch.

Рис. 1. Дерево хронологий

Подразумевается ветвление хронологий лишь в будущее (Рис. 1).

Аксиома 7: (if (and (=<? s1? s) (=<? s2? s))

(or (=<? s1? s2) (=<? s2? s1)))

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

Состояния и хронологии особенно важны потому, что они являются определенной стадией рассмотрения фактов и событий [8].

1.3 Временная логика предикатов А. Тейза

Линейную временную логику предикатов представил в своих работах А. Тейз путем обобщения временной логики высказываний и введения переменных, функций и предикатов [9]. Выразительные возможности при этом значительно возросли, как и в классической логике. На данный момент временная логика предикатов активно используется в исследовании систем, связанных с параллельными процессами.

При построении языка линейной временной логики предикатов используются символы двух видов: одни обозначают «глобальные объекты», другие - «локальные объекты». Интерпретация глобальных объектов не зависит от заданного момента времени. Например, глобальным объектом является некоторый субъект; символ, обозначающий его, сохраняет одно и то же значение во всех состояниях. Примером локального объекта служит обладатель некоторой должности. Эту должность могут последовательно занимать разные лица, поэтому, символ, обозначающий лицо, занимающее данную должность, в разных состояниях представляет разных людей.

Язык линейной временной логики предикатов (или язык первого порядка) строится на основе множеств символов:

1. Множество логических связок (?, , ?, ? и ?)

2. Множество временных операторов (, ?, ЃZ, И)

3. Множество кванторов (, )

4. Символ равенства (=)

5. Множество Р глобальных предикатных констант

6. Множество F глобальных функциональных констант

7. Множество Q локальных констант

8. Множество L локальных индивидных констант

9. Множество V глобальных переменных

Эти множества не пересекаются. Каждой функциональной или предикатной константе соответствует некоторое целое неотрицательное число, называемое числом мест или арностью.

Элементы рассматриваемого языка получаются по правилам построения, аналогичным, с одной стороны, правилам построения, применяющимся в логике предикатов, и, с другой стороны, правилам построения, применяющимся во временной логике высказываний:

· Термом называется всякая переменная, всякая индивидная локальная константа и всякая функциональная форма

· Функциональная форма представляет собой последовательность символов, состоящую из функциональной константы, скобок и подходящего числа термов. Точнее, если f - (глобальная) функциональная константа с числом мест n и t₁, …, t_n - термы, то соответствующая форма имеет вид f (t₁, …, t_n). Если n равно 0, то вместо f() пишут f и говорят о (глобальной) индивидной константе.

· Предикатная форма есть последовательность символов, состоящая из предикатной константы, скобок и подходящего числа термов. Если р - (глобальная) предикатная константа, у которой число мест m, и t₁,…, t_m суть термы, то соответствующая форма имеет вид p (t₁,…, t_m). Если т равно 0, то пишут р вместо р() и говорят о (глобальной) пропозициональной константе.

· Атомом называется всякая предикатная форма, всякое локальное высказывание и всякое равенство.

· Равенством называется выражение вида (s = t), где s и t-термы.

· Понятие формулы определяется рекурсивно посредством следующих правил:

- атом является формулой;

- если A - формула, то ~A, ? А, ?А и ЃZА - формулы;

- если А и В-формулы, то (А В), (А?В), (А?В), (А? В), (А И В) - формулы;

- если А есть формула и х - некоторая переменная, тогда хА и хА являются формулами.

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

Пусть заданы множества глобальных и локальных символов, которые только что были введены. Тогда временной интерпретацией называется пятерка (S, R, D, I_c, I_v), обладающая следующими свойствами.

· (S, R) - линейная временная структура

· D - непустое множество; это область интерпретации.

· Iс - функция интерпретации констант, которая сопоставляет

- каждой функциональной глобальной n-местной константе f F некоторую функцию I_c(f), действующую из Dⁿ в D;

- каждой предикатной глобальной m-местной константе р Р некую функцию I_c(p), действующую из D^m в {И, Л};

- каждому состоянию s S и каждой индивидной локальной константе l L некоторый элемент I_c (s, l) D;

- каждому состоянию s S и каждому локальному высказыванию q Q некоторое значение истинности I_c (s, q).

· I_v является функцией интерпретации переменных, которая сопоставляет каждой переменной x V некий элемент I_v(x) D.

Пусть заданы временная интерпретация J = (S, R, D, I_c, I_v) и состояние s S, тогда с помощью следующих правил интерпретации можно приписать каждому терму некоторый элемент из D и каждой формуле-некоторое значение истинности.

· Если х-переменная, то J (s, х) = _def I_v(x).

· Если l - локальная индивидная константа, то J (s, l) = _def I_c(s, l).

· Если f - функциональная n-местная константа и t₁,…, t_n - термы, то J (s, f(t₁,…, t_n)) = _def I_с(f) (J (s, t₁), …, J (s, t_n)).

· Если р-предикатная m-местная константа и t₁,…, t_m суть термы, то J (s, p(t₁,…, t_m)) = _def I_с(p) (J (s, t₁), …, J (s, t_m)).

· Если q - локальное высказывание, то J (s, q) = _def I_c(s, q)

· Если t₁ и t₂-термы, то J (s, t₁ = t₂) есть И, если J (s, t₁) = J (s, t₂), а иначе Л.

· Если А и В формулы, то ~А, (А В), (A?В), (А?В) и (А ? В) интерпретируются, как формулы.

· Если А и В-формулы, то ЃZ А,  А, ? А и (A И B) интерпретируются, как формулы.

· Если А - формула и х-переменная, то J (s, xA) есть И, если J_x/d(s, А) равняется И для всех d D, и J (s, хА) есть И, если J_x/d (s, А) равняется И хотя бы для одного d D. Запись J_x/d означает некую интерпретацию, совпадающую с J всюду, за исключением переменной х, для которой I_v(х) = d.

Отметим, что можно ограничиться случаем, когда S есть множество неотрицательных целых чисел, a R-функция следования. Тогда временная интерпретация представляется в виде бесконечной последовательности классических интерпретаций, в которых глобальные символы интерпретируются единообразно. Подчеркнем тот факт, что временной аспект этой логики не меняет роли переменных. В частности, их можно квалифицировать как свободные или связанные.

Эффективное использование временной логики первого порядка для формализации рассуждений практически возможно только при наличии некоторой аксиоматической системы.

Естественная идея состоит в комбинировании аксиоматической системы для классической логики первого порядка с той системой, которая построена для временного исчисления высказываний. Однако следует проявлять осторожность. Прежде всего схема

xА (x) ? А (t),



общезначимая в классической логике, общезначима во временной логике тогда и только тогда, когда замена переменной х термом t не вводит локальную константу в область действия некоторого временного оператора. Если это условие соблюдается, то говорят, что терм t заменяем на х в А.

Следует также уточнить связи между временными операторами и кванторами. Имеют место соотношения

xЃZА ? ЃZxА

xА ? xА

Аксиоматическая система, которую мы используем, содержит (рекурсивное) множество аксиом, определяемых следующими правилами.

1) Любая конкретизация схемы общезначимой формулы временной логики высказываний является аксиомой.

2) Если А - формула, не содержащая локальных объектов, то импликация (А ?ЃZА) является аксиомой.

3) Если х - глобальная переменная, А(х) - формула и t - терм, заменяемый на х в А (х), то импликация (x A(x) ?A(t)) есть аксиома.

4) Если А - формула и x-глобальная переменная, то формула (х~А ? ~хА) является аксиомой.

5) Если A - формула и х-глобальная переменная, то импликация (хЃZА ? ЃZхА) есть аксиома.

Принимаются следующие правила вывода.

• Если А и А? В-теоремы, то В является теоремой.

• Если A - теорема, то А является теоремой (Необходимость).

• Если А не содержит свободных вхождений глобальной переменной х и А ? В-теорема, то импликация А?х В является теоремой (Обобщение).

В противоположность классическому исчислению предикатов временное исчисление предикатов не допускает полную аксиоматизацию. Тем не менее представленная аксиоматическая система позволяет осуществлять вывод многочисленных полезных теорем.



2. Учет временного фактора при разработке баз данных

Традиционные реляционные модели данных способны хранить лишь последнюю информацию об объектах предметной области, или, в терминах баз данных: предоставлять моментальные снимки данных на текущий момент времени. Изменения объекта или атрибутов объекта приводит к тому, что предыдущее состояние становится неизвестным, и невозможно что-либо сказать об этом объекте в прошлом. Что касается темпоральных моделей данных, они позволяют хранить историческую информацию об объектах: если объект начал свое существование в момент времени Т1, а закончил в момент времени Т2, то нам будут известны все его состояния на промежутке времени [Т1, Т2].

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

В настоящее время еще не разработана СУБД, поддерживающая все темпоральные возможности. Для их осуществления в пределах информационной системы (ИС) разработчикам приходится создавать новые средства дополнения и расширения реляционных моделей. Наиболее популярной проблемой создания подобных приложений считается непонимание уровня и способа осуществления поддержки темпоральности в базах данных.

2.1 Темпоральная модель данных

В теории темпоральных БД существует понятие темпоральной модели данных (ТМД) [10]. Это модель данных, которая ориентирована на хранение и обработку темпоральных данных, все ее аспекты также являются темпоральными. В традиционной модели выделяют три компоненты М=(DS, OP, C), где DS - структура данных, OP - операции, С - ограничения целостности. Темпоральная же модель MT=(DST, OPT, CT) поддерживает понятия трех компонент с учетом данных, изменяющихся во времени. Структура модифицируется для осуществления хранения временных данных. Алгебра и операции изменения переопределяются с помощью темпоральной семантики. Кроме того, во временной модели должны поддерживаться аналоги нетемпоральных ограничений. Семантика темпоральных ограничений целостности также должна быть переопределена.

Рассмотрим данные в БД, как отражение окружающего мира в определенный момент времени, а каждую запись, как факт, являющийся истинным на интервале или в данный момент времени. При переходе к темпоральной БД, необходимо указывать интервалы времени, когда каждый из фактов был истинным в описываемом мире. Данное представление времени, когда к данным привязывается промежуток их истинности, называется модельным, или действительным (valid time). Например, фраза «Семья Н. Проживала по этому адресу в период с 11.12.1998 по 30.10.2007» говорит нам о том, что информация о проживании этой семьи по данному адресу верна лишь в заданный период времени и ни днем больше.

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

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

Рассмотрим пример того, как сопоставляются друг другу действительное и транзакционное время. Допустим в организации имеется таблица с зарплатами сотрудников на данный момент (Табл.2).

Табл. 2 Таблица зарплат без темпоральных расширений

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

Табл. 3. Таблица зарплат с поддержкой действительного времени

Если таблица обладает поддержкой транзакционного времени, можно проследить в какой момент в базу было внесено новое значение (Табл.4).

Табл.4 Таблица зарплат с поддержкой транзакционного времени



Однако самый широко используемый вариант представления данных в таблицах БД - это использование двух типов времени (Табл.5). В этом случае появляется возможность отслеживать, когда были внесены некорректные данные, когда они были исправлены и исключается случай использования неактуальной на данный момент информации.

Табл.5. Таблица с поддержкой обеих линий времени

2.2 Методы представления данных

Для реализации темпоральной поддержки данных в реляционных моделях требуется изменение моделей данных на уровне СУБД, но этот способ достаточно трудоемкий и не всегда является возможным. На практике применяются два основных метода реализации поддержки темпоральной функциональности: реализация ТМД на уровне приложения и расширение нетемпоральной модели данных до темпоральной [14]. Однако первый метод не является универсальным, так как в случае изменения части кода в приложении каждому разработчику приходится проектировать временную семантику заново. Вторая схема - расширение реляционной модели до темпоральной широко используется программистами ТБД, поскольку подразумевает собой модификацию отдельных составляющих модели, таких как ограничение целостности или языка запросов. Структура данных и способ доступа к информации остаются прежними.

Существуют различные ТМД основанные на последнем подходе. Их различие заключается в следующих значимых критериях:

· Тип темпоральных данных (интервальная или точечная интерпретация времени)

· Поддержка темпоральности на уровне кортежа или конкретного атрибута

Как уже было рассмотрено ранее, временные данные в БД могут быть представлены и в дискретном, и в интервальном виде. Точечное представление имеет преимущество в связи с тем, что оно поддерживается стандартом SQL-92. Однако использование лишь одного атрибута времени усложнит запросы и обработку данных, поэтому реализация модели с интервальным представлением времени в этом плане имеет преимущество.

По второму критерию разделяются следующие темпоральные модели данных [11].

1. Темпоральная модель данных, разработанная Р. Снодграсом.

В битемпоральном отношении R содержится набор следующих атрибутов (A1,…, An, T), где Т - определенный на множестве битемпоральных элементов атрибут. Теперь R перепишем следующим образом: R = (A1,…, An, Ts, Te, Vs, Ve). Новые атрибуты Ts, Te, Vs, Ve - это атомарные временные атрибуты, первые два из которых содержат даты начала и конца транзакционного времени (transactional start, end), вторые - действительного времени (valid strart, end). Этот способ представления временных атрибутов является наиболее естественным и часто используемым.

2. Темпоральная модель данных, разработанная К. Дженсеном.

Идея этого представления заключается в том, что исторические кортежи не изменяются, соответственно их можно лишь прочитать. Данная модель данных наилучшим образом подходит для хранения битемпоральных отношений, основанного на архивах. Битемпоральное отношение R с тем же набором атрибутов A1,…, An представим в таком виде: R = (A1,…, An, Vs, Ve, T, Op). Здесь Vs, Ve - также являются датами начала и окончания истинности факта в моделируемом мире, T - время занесения кортежа в базу, а атрибут Op отвечает за создание (I - insert) или удаление (D - delete) кортежа из БД. Изменение записи возможно путем выполнения двух запросов - удаление и создание новой записи с таким же атрибутом Т.

3. Темпоральная модель данных, разработанная С. Гадией.

Данный метод подразумевает, что каждый атрибут, входящий в кортеж, имеет битемпоральные метки. Благодаря этому возможно более гибкое моделирование в реальном мире. В битемпоральном отношении R содержится набор следующих атрибутов (A1,…, An, T), где Т - определенный на множестве битемпоральных элементов атрибут. Далее можно представить отношение R, как отношения, в которых каждому атрибуту сопоставляется собственная темпоральная метка: R=({([Ts, Te] [Vs, Ve] A1)},…, {([Ts, Te] [Vs, Ve] An)}). В каждом кортеже содержится n элементов, представляющих собой набор из трех значений: транзакционное время атрибута [Ts, Te], действительное время [Vs, Ve] и само значение атрибута Ai.

4. Темпоральная модель данных, разработанная E. МакКензи.

Здесь в качестве битемпорального отношения выступает ряд состояний в действительном времени, а вместо индексов записывается транзакционное время. В кортежах с действительным временем атрибутам сопоставляются темпоральные метки. Битемпоральное отношение R, имеющее ряд атрибутов A1,…, An, выражается как отношение, где атрибуты помечены временными метками: R = (VR, T), где VR - отношение в действительном времени; Т - транзакционное время. Модель отношения действительного времени выглядит так: VR = (A1V1,…, AnVn), где A1,…, An - атрибуты, а Vi - атрибут действительного времени, относящийся к каждому атрибуту Ai и отражающий время актуальности этого атрибута в моделируемом мире.