Основные свойства времени и способы его представления. Временная логика предикатов А. Тейза. Учет временного фактора при разработке баз данных. Разработка концепции базы данных на основе реляционной системы управления. Требования к программному продукту.
Аннотация к работе
В процессе выполнения выпускной квалификационной работы по теме «Исследование и разработка темпоральнои базы данных» получены следующие результаты: 1. Исследованы и проанализированы основные модели представления временного фактора в теории интеллектуальных систем, а именно: темпоральные интервальная (представление времени с помощью временных интервалов) и точечная (использование в качестве базовых элементов временных точек) логики. Идея представления времени с использованием временных интервалов проиллюстрирована на примере темпоральной логики Allen [7], а точечный подход проиллюстрирован на примере темпоральной логики MCDERMOTT [8].
Введение
предикат тейз реляционный программный
В современной науке одним из наиболее перспективных направлений вычислительной техники считается создание систем искусственного интеллекта. Разработка интеллектуальных систем подразумевает не только изучение человеческого интеллекта с использованием идей и методов его мыслительной деятельности, но и создание компьютерного интеллекта, представляющего собой некую аналогию человеческому. Здесь наиболее важным шагом является объяснение принципов мыслительного процесса человека, основных идей и методов, с помощью которых человек производит свои вычисления. Таким образом, под понятие интеллекта подводится принципиально новая теоретическая база, и тот факт, что компьютерные системы искусственного интеллекта находят широкий круг применения, становится очевидным.
Развитие систем искусственного интеллекта тесно связано с расширением пределов возможностей компьютерного обеспечения и компьютерных технологий. Возникающие в данной области исследований проблемы достаточно сложны и интересны, вследствие чего в настоящее время искусственный интеллект является одной из приоритетных областей, в которой занято большое количество специалистов. Таким образом, вполне естественно, что идеи развития искусственного интеллекта перетекли в область компьютерных исследований, и в настоящее время компьютерное моделирование интеллектуальной деятельности человека является весьма актуальным.
В последние годы одним из интереснейших направлений в разработке систем ИИ является рассмотрение процессов интеллектуальной деятельности человека во времени. Время не случайно столь приоритетно в исследованиях в области искусственного интеллекта: и в человеческих рассуждениях фактор времени является одним из основополагающих. Образ так называемой «временной оси» глубоко заложен в человеческое понимание окружающего мира. Каждый наверняка замечал, что все наши воспоминания мы строим на воображаемой временной оси, и часто нам приходится восстанавливать произошедшие события в хронологическом порядке. Человеческая способность выстроить события на временной оси очень сильна, и для большинства людей, не обладающих способностями абстрактного мышления, является единственным способом представления происходящих событий.
Трудно представить существование какой-либо области исследований в искусственном интеллекте, не использующей рассуждения с учетом временного фактора в той или иной интерпретации, будь то системы медицинской диагностики, в которых необходимо определять время попадания вируса в кровеносную систему и период инкубации; системы тестирования электронных систем, в которых необходимо исследовать временной период, в течение которого увеличивается нагрузка конденсатора; системы программирования роботов, в которых необходимо выполнение определенной последовательности заданий в определенное время; базы знаний, в которых знания экспертов и коэффициенты уверенности правил являются результатом воздействия внешней информации и внутренней реакции, а следовательно тоже изменяются с течением времени.
Фактор времени имеет первостепенную важность, поскольку окружающий нас мир изменяется во времени. Если бы мы жили в мире, где какие бы то ни было изменения были невозможны - не существовало бы заражающих кровеносную систему вирусов, изменений электрической нагрузки, не существовало бы даже изменений расположения солнца на небе - не было бы и необходимости учета временного фактора. При исследованиях временного фактора должны учитываться следующие основные моменты: 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] и точечный подход MCDERMOTT [8].
Темпоральная логика, основанная на интервальном представлении времени
Темпоральную интервальную логику предложил Аллен в начале 80-х годов [7]. В качестве временных примитивов в ней используются интервалы, а не временные точки.
Здесь заглавными буквами обозначены предикаты и константы, а строчными переменные. Кроме того, будем использовать набор связок и квантификаторов в их стандартной интерпретации, а именно: & - конъюнкция, ? - дизъюнкция, ? - отрицание, ? - импликация, U - эквивалентность, " - квантор общности, $ - квантор существования, $! - квантор существования и единственности.
Временной интервал 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)
Будет полезно определить предикат, который подытоживал бы отношения, в которых один интервал полностью содержится в другом. Определим IN следующим образом: IN (t1, t2) U (DURING (t1, t2) ? STARTS (t1, t2) ? FINISHES (t1, t2)) (1.3)
Используя это предикат, можно ввести в рассмотрение первое решающее свойство предиката HOLDS: если свойство р сохраняется на интервале Т, то оно сохраняется на всех его подинтервалах интервала Т, т.е.: HOLDS (p, T) U (" t. IN (t, T) ? HOLDS (p, t)). (1.4)
Например, если в течение 2015 года у меня была машина, то, следовательно, я владел машиной в январе 2015, в феврале 2015 и т.д.
На самом деле оказывается, что в дальнейшем нам необходима более сильная аксиома. Она будет представлена ниже (1.5), несмотря на то, что (1.4) может быть выведена из нее и свойств отношения IN.
HOLDS (p, T) U " t. IN (t, T) ? ($ s. IN (s, t) & HOLDS (p, t)). (1.5)
Чтобы записывать сложные логические выражения существует набор функций вида and, or, not, all, exists, соответствующих логическим операторам &, ?, ?, ", $, причем это соответствие можно отразить следующим образом.
Конъюнкция легко может быть определена для предиката HOLDS: HOLDS (and (p, q), t) U HOLDS (p, t) & HOLDS (q, t) (1.6)
Отрицание определяется так: HOLDS (not (p), T) U (" 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) U HOLDS (p, T), (1.9) чего мы и ожидали интуитивно. Отражая аналогичным образом обычное определение дизъюнкции для определения функции «or», т.е., HOLDS (or (p, q), t) ? HOLDS (not (and (not (p), not (q))), t), можно вывести следующее: HOLDS (or (p, q), T) U " 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)).
Отметим, что рассматривается типизированная логика. Так, переменные, начинающиеся с 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)))
Состояния объединяются в т.н. «хронологии». Хронология есть полная возможная история мира, полностью упорядоченное множество состояний, бесконечно расширяющееся во времени.
(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. Множество временных операторов (, ?, ?, И)
3. Множество кванторов (", $)
4. Символ равенства (=)
5. Множество Р глобальных предикатных констант
6. Множество F глобальных функциональных констант
7. Множество Q локальных констант
8. Множество L локальных индивидных констант
9. Множество V глобальных переменных
Эти множества не пересекаются. Каждой функциональной или предикатной константе соответствует некоторое целое неотрицательное число, называемое числом мест или арностью.
Элементы рассматриваемого языка получаются по правилам построения, аналогичным, с одной стороны, правилам построения, применяющимся в логике предикатов, и, с другой стороны, правилам построения, применяющимся во временной логике высказываний: · Термом называется всякая переменная, всякая индивидная локальная константа и всякая функциональная форма
· Функциональная форма представляет собой последовательность символов, состоящую из функциональной константы, скобок и подходящего числа термов. Точнее, если f - (глобальная) функциональная константа с числом мест n и t1, …, tn - термы, то соответствующая форма имеет вид f (t1, …, tn). Если n равно 0, то вместо f() пишут f и говорят о (глобальной) индивидной константе.
· Предикатная форма есть последовательность символов, состоящая из предикатной константы, скобок и подходящего числа термов. Если р - (глобальная) предикатная константа, у которой число мест m, и t1,…, tm суть термы, то соответствующая форма имеет вид p (t1,…, tm). Если т равно 0, то пишут р вместо р() и говорят о (глобальной) пропозициональной константе.
· Атомом называется всякая предикатная форма, всякое локальное высказывание и всякое равенство.
· Равенством называется выражение вида (s = t), где s и t-термы.
· Понятие формулы определяется рекурсивно посредством следующих правил: - атом является формулой;
- если A - формула, то ~A, ? А, ?А и ?А - формулы;
- если А и В-формулы, то (А & В), (А?В), (А?В), (А? В), (А И В) - формулы;
- если А есть формула и х - некоторая переменная, тогда "ХА и $ХА являются формулами.
Отметим, что в той логике, которую мы только что определили, все символы являются глобальными, за исключением некоторых индивидных констант и некоторых высказываний, которые могут быть локальными. Можно было бы ввести локальные элементы всех типов, но мы ограничимся индивидными константами и высказываниями ввиду того, что только эти локальные элементы используются на практике.
Пусть заданы множества глобальных и локальных символов, которые только что были введены. Тогда временной интерпретацией называется пятерка (S, R, D, Ic, Iv), обладающая следующими свойствами.
· (S, R) - линейная временная структура
· D - непустое множество; это область интерпретации.
· Іс - функция интерпретации констант, которая сопоставляет
- каждой функциональной глобальной n-местной константе f I F некоторую функцию Ic(f), действующую из Dn в D;
- каждой предикатной глобальной m-местной константе р I Р некую функцию Ic(p), действующую из Dm в {И, Л};
- каждому состоянию s I S и каждой индивидной локальной константе l I L некоторый элемент Ic (s, l) I D;
- каждому состоянию s I S и каждому локальному высказыванию q I Q некоторое значение истинности Ic (s, q).
· Iv является функцией интерпретации переменных, которая сопоставляет каждой переменной x I V некий элемент Iv(x) I D.
Пусть заданы временная интерпретация J = (S, R, D, Ic, Iv) и состояние s I S, тогда с помощью следующих правил интерпретации можно приписать каждому терму некоторый элемент из D и каждой формуле-некоторое значение истинности.
· Если х-переменная, то J (s, х) = def Iv(x).
· Если l - локальная индивидная константа, то J (s, l) = def Ic(s, l).
· Если f - функциональная n-местная константа и t1,…, tn - термы, то J (s, f(t1,…, tn)) = def Ic(f) (J (s, t1), …, J (s, tn)).
· Если р-предикатная m-местная константа и t1,…, tm суть термы, то J (s, p(t1,…, tm)) = def Ic(p) (J (s, t1), …, J (s, tm)).
· Если q - локальное высказывание, то J (s, q) = def Ic(s, q)
· Если t1 и t2-термы, то J (s, t1 = t2) есть И, если J (s, t1) = J (s, t2), а иначе Л.
· Если А и В формулы, то ~А, (А & В), (А?В), (А?В) и (А ? В) интерпретируются, как формулы.
· Если А и В-формулы, то ? А, А, ? А и (A И B) интерпретируются, как формулы.
· Если А - формула и х-переменная, то J (s, "XA) есть И, если Jx/d(s, А) равняется И для всех DI D, и J (s, $ХА) есть И, если Jx/d (s, А) равняется И хотя бы
Вывод
В процессе выполнения выпускной квалификационной работы по теме «Исследование и разработка темпоральнои базы данных» получены следующие результаты: 1. Исследованы и проанализированы основные модели представления временного фактора в теории интеллектуальных систем, а именно: темпоральные интервальная (представление времени с помощью временных интервалов) и точечная (использование в качестве базовых элементов временных точек) логики. Идея представления времени с использованием временных интервалов проиллюстрирована на примере темпоральной логики Allen [7], а точечный подход проиллюстрирован на примере темпоральной логики MCDERMOTT [8].
2. Исследованы и проанализированы темпоральная модель данных (ТМД) и ее различные модификации и темпоральная логика, служащая основой языка запросов ТМД при построении временной БД.
3. Разработана основная концепция (базовые элементы и связи) ТМД, построена ER-диаграмма для обеспечения области консалтинга
4. Средствами СУБД MYSQL была спроектирована и создана БД для консалтинга. С помощью объектно-ориентированного языка программирования Java с фреймворком Hibernate была разработана темпоральная надстройка над реляционной БД, опирающаяся на основные принципы темпоральной алгебры и транслирующая темпоральные запросы в запросы SQL.
Выпускная квалификационная работа имеет множество путей для дальнейшего развития. В будущем может быть создан интерфейс, реализована поддержка пользователя с всплывающими подсказками. Кроме того, работа является первым шагом в исследовании темпоральных баз данных, ведь сейчас данное направление исследуется многими крупными фирмами-разработчиками, и ведутся попытки реализации темпоральной СУБД, которая будет учитывать все возможности темпоральной поддержки.
Список литературы
1. Yoav Shoham. Reasoning about Change. - The MIT Press Series in Artificial Intelligence, 1988.
2. Е.Ю. Кандрашина, Л.В. Литвинцева, Д.А. Поспелов. - Представление знаний о времени и пространстве в интеллектуальных системах. - М.: Наука, 1989.
3. A. Pnueli. A temporal logic of programs. - Proceedings of 18th FOCS, October 1977.
4. V.R. Pratt. Semantical Considerations on floyd-hoare logic. - Proceedings of 17th FOCS, IEEE, October 1976.
5. H. Nishimura. Descriptevely complete process logic. - Acta Informatica, 1980.
6. J.F. Allen and P.J. Hayes. A commonsense theory of time. - Proceedings of 9th IJCAI, Los Angeles, 1985.
7. J.F. Allen. Towards a general theory of action and time. - Artificial Intelligence, 23 (2), 1984.
8. D. MCDERMOTT. A temporal logic for reasoning about processes and plans. - Cognitive science, 1982.
9. А. Тейз, П. Грибомон. Логический подход к искусственном интеллекту: От модальной логики к логике баз данных: Пер. с франц. - М.: Мир, 1998.
10. Snodgrass R. Developing Time-Oriented Database Applications in SQL - Morgan Kaufmann Publishers, 1999.
11. Jensen C.S., Soo M.D., Snodgrass R.T. Unifying Temporal Data Models Via a Conceptual Model, Information Systems Vol. 19, No. 7, 1994.
12. Пораи Д.С., Соловьев А.В., Корольков Г.В. Реализация концепции темпоральнои базы данных средствами реляционнои СУБД // Документооборот. Концепции и инструментарии: сб. науч. тр. / Ин-т системного анализа РАН; под ред. В.Л. Арлазарова, Н.Е. Емельянова. М.: Едиториал УРСС, 2004.
13. К.Дж. Дейт. Введение в системы баз данных, 7-е издание. Вильямс, 2002.
14. А.Н. Базаркин. Разработка темпоральнои модели данных в медицинскои информационнои системе. тр. Междунар. конф.: ИПС РАН, Переславль-Залесскии, 2006.
15. Нгуен Доан Куонг. Организация доступа, хранения и извлечения знаний в темпоральных базах данных. Санкт-Петербург, 2006.
16. Б.Б. Костенко, С.Д. Кузнецов. История и актуальные проблемы темпоральных баз данных, МГУ, 2007, Эл. ресурс: http://www.citforum.ru/ database/articles/temporal
17. MCKENZIE E., Snodgrass R. Supporting Valid Time in an Historical Relational Algebra: Proofs and Extensions: Technical Report Department of Computer Science, University of Arizona. Tucson, AZ, 1991.