автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Временная модель данных

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА, ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ, ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ Государственный университет им. М. В Ломоносова

■Хи^/льтет вычислительной магематигл и кибернетики

На прагах рукописи УДК 519.688

Нанукян Манук Гарпупгзвич

ВРЕМЕННАЯ МОДЕЛЬ ДАННЫХ

Специальность 05.13.11 - математическое и лрограммное обеспечение вычислительных машин, комплексоп, систем и сетей

Автореферат диссертации на соискание ученой степени кандидата физико - математических наук

МОСКВА - 1930

Работы выполнена на кафедре Автоматизации систем вычислительных - комплексов факультета Вычислительной ышематики и кибернетики МГУ им. №. В. Ломоносова.

Научный руководитель: доктор - физико математических паук Д А. Калиниченко.

Официальные оппоненты: доктор' технических наук, профессор А. Л. Щерс. • кандидат физико - математических наук С. Д. Кузнецов.

Ьедушл организации: Вычислительный центр АН СССР.

Защита состоится в 4.4, час. ОО мин. на заседании специализированного совета Д. Оьй. 05. да N 4 при Московском Государственном Университет! имени М. В. Ломонссока но адресу 119Я99, ГСП, Шскьа, Ленински* Горы, МГУ, факультет Вычислительной математики и кибернетики,

О диссертацией мо.чло ознакомится в библиотеке факультет. РМиК МГУ.

аул

Учений секретарь профессор

Актуальность темя. За период, прошедший с момента опубликования рёшшш работ Э. Кодда был выполнен больной с.6ъ?и исследований КЗк^йЬбласти моделей данных(МД) в целом, так и применительно к реТТЦшннш моделям в частности. Результатом этих ::селс'Довдний являются концептуальны? МД, б которых поддерживается рпзгитый де:сларативный и/или процедурный аппарат для моделирования данных. Однако, проблемы эффэктивной организаций данных и манипулирования ими не исчерпивают весь спектр задач в теории Саз данных (БД). Особую значимость приобретают вопросы концептуального моделирования категории времени в Сазах дшшых(КВЕД). Предпосылки для таких исследований заключаются в тон. что в рампах традиционных МД можно представить в БД только единственной состояние моделируемого обмета. Это приводит к потере информации, которая необходима для принятия того или иного решения. Таким образом, целью поддердки КББД является представление в них информации об эволюции объектов реального мира. Следует отметить, что вопросы моделирования времени не являются прерогативой только лишь систем обработки информации. В научной периодике известны работы в области исскуствэнчого интеллекта, логики. лингвисткют и т. д.

Явное представление временного контекста и отражение его в конструкциях информационных систем предполагает разработку специальных языковых средств, поскольку временное измерение, временные атрибуты отношений БД имеют особую семантику. В последнее время, работы, ориентированные на поддержу КВБД в МД, интенсивно развиваются. ДЪетатевдо отметить, что за рубежом существуют 25 научно - исследовательских групп, которые изучают проблема концептуального моделирования КВВДг Такие исследования вызваны, с одной стороны, необходимостью дальнейшего развития концептуальных МД для решения практических задач, а с другой -тем, что с появлением более дешевых сред хранения (наорич-Ф, оптических дисков) становится реальной практическая реализация временных БД. Поэтому обычно целью концептуализации категории времени является преяде всего создание ЫД и универсальных СУБД, обеспечивающих явную поддержу информационной динамики. Одному из подходов концептуального моделирования КВБД посвяшена настоящая работа.

Цель работы. Целью диссертационной работы является исследование и разработка языковых средств для концептуального моделирования КВБД в рамках унифицированной концептуальной модели данных( УКМД) Систеш интеграции неоднородных баз данных.

Поставленная цель предполагает решение сле,;ушцх задач:

1. Анализ языковых средств поддерлки категории времени в базах данных.

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

3. Формальное определение семантики языковых средств с целью:

- разработки спецификаций при реализации языковых средств;

1. Snott(jrass R. Research concerning tin» in. databases. Project suiraari»3// SJGMOD Record. 1986. v. IS, H-4. p. 10 •• 39.

- доказательства корректности преобразований временных предикатов.

4. Иоддергика языковых средств временной МЦ: '

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

- разработка алгоритмовли программ для поддержки временных предикатов и опреаций-над АТД-.

Методы исследования. Проведенные исследования базируются на '' аппарат формальной логики и теории множеств.

Научная новизна полученных результатов: - предложено развитие языковых средств для концептуального моделирования КВБД с целью обеспечения интерфейса высокого уровня для конечного пользователя;

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

Практическая ценность. Разработанное программное обеспечений для поддержи виртуальных отношений в БД внедрено в системе интеграции неоднородных баз данных и знаний1. Внедрение подтверждено актом.

Апробация работы. Результаты диссертационной работы докладывались на конференциях молодых ученых факультета ШиК МГУ в , 1986 - 1987 г.г., обсуждались на научных семинарах кафедры АСВК Факультета ШиК МГУ под руководством чл. корр. АН СССР Королева А Н. в 1365 - 1987 г. г. , на всесоюзном семинаре "Распределенная обработка данных и локальные сети ЭВМ" в МДНГП в 1987 г., на конференциях профессорско - преподавательского состава и научных работников ЕрГУ в 1988 - 1989 г. г.

Публикации. По материалам диссертации опубликовано пять печатных работ.

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

Содержание работы

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

В существующих работах можно выделить два основных подхода к моделированию временных БД. Один из них заключается в прямом включении семантики времени в реляционную Щ Другой подход, которому следует подавляющее большинство исследований, заключается во включении временного или временных атрибутов в отношения БД. Предлагаемые МД прежде всего существенно различаются однородностью представляемой временной информации относительно свойств объекта. Согласно однородной модели, периоды времени, в течение которых значения свойств объекта остаются достоверными, одинаковы для всех значений атрибутов одного кортежа отношения. Противоположностью этой модели является неоднородная модель, в которой каждое свойство обгекта в кортеже имеет собственную

г. Временной атрибут трактуется как абстрактный тип данных(ЛТ}

3. Разрабатывается по научно - технической программе 0.80.01 ГКНГ СССР.

временную характеристику. Существуют«такте и промежуточные варианты представлений, в которых однородность требуемся для подмножеств свойств в кортеже отношения. При допущении однородности моделирование в БД временного аспекта достигается посредством двух временных атрибутов. Первый атрибут определяет временной интервал существования, в течение которого соответствуйте! кортежу объект предметной области (или Факт) по мнению пользователя существует (имеет место). Второй атрибут - атрибут доверия имеет значениями временные интервалы, в течение которых система "верит" в существование объекта (в достоверность факта). Значения атрибута существования задазгст пользователем при помещении кортегл в БД или при его изменении. Значение атрибута доверия устанавливается системой так, что начальный момент временного интервала совпадает с временем транзакции, обеспечивающей помещение нового или образование измененного кортегл, а конечный момент - с временем транзакции, обеспечивающей удаление кортежа из БД, или его модификацию. При образовании нового кор-то .та значение конечного момента времени атрибута доверия равно бесконечному моменту времени в будущем.

Введение временных КЯ означает необходимость сохранения в БД значений свойств и отношений объектов, которые более не являются достоверным:;. При этом классическая трактовка операция сб-иовлепия БД поменяется: любая аетуалнзашя БД рассматривается как включение в нее новых данных при сохранении информации, заключенной в предыдущем с-о состоянии. С целью элективной организации дачных целесообразно отдельное хранение исторической БД Таким образом, изменение семантики операторов UPDATE и DELETE вытекает из природы временных ЕЛ.

Обычно МЯ опираются на концепцию непротиворечивости БД. означающую недопустимость представления в ней одновременно некоторого факта и его отрицания. Эта концепция при поддержке КВГД голята быть расширена возможность" представлен;;" состояний БД, относящихся к различным дискретным момента»,! времени( ДМВ). В каждом из таглх состояний традиционные инварианты БД выполняются. Необходимы, однако, дополнительные средства задания инвариантов БД. учитивахюях категорию времени. Для образования временных срезов отношений в заданные периоды времени обычно вводятся бинарные временные предиката

При выполнении операций реляционной алгебры значения временных атрибутов двух текущих кортежей отношений - операндов one-раций подвергается особым преобразованиям для вь-числения временных атрибутов кортэгай результирующих отнопений. Рассматриваются функции преобразования для некоторых операций реляционной алгебры. Существенно зависит от временного аспекта трактовка агрегатных функнлй. Та:, функции МАХ n MIN становятся в общем случае многозначными: в различные периоды времени максимальные а минимальные значения атрибута - аргумента функции могут Снть различными. . Значением таких фунэд'й могло бы быт» распределение максимума (минимума) значений аргумента функции во времени. Поэтом, в действительности следует иметь по крайней мере два различных варианта такчх функций: одну - для определения указанного распределения, а другую - для определения единственного наибольшего (наименьшего) значения аргумента Функции во все времена Аналогично функции TOTAL. AVERAGE и COUNT также производят уяе ке одиночные значения, а распределение значений во времени. Могут быть введены.специальные функции, выраСзтывз-

ющие уникалыше среднее, суммарное и общее число различных значений.

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

В первой главе приводится формальное определение языковых средств УКВД. Определен семантика операций реляционной алгебры и языка фильтров1». Анализу подвергаются языковые средства концептуального моделирования данных б БД. Рассматриваются 1сак процедурные, таи и декларативные средства поддержки виртуальных отношений. Декларативными средствами являются абстракции обобщения, разности и соединения.

Пусть виртуальное отношение является обобщением по категории Ci отношении Ri.R-t..... R,*, по категории отношений Ri, Rjf,

....R,^ и наконец по категории Сж отношений'R*, R|\... Тогда

R(, - ША] I (г fc Rj.) У (г£ r£) V . - Vir £ R^)> (J

(rCAJ I (r£ Ri) V (г С RJ)V- .-V (г £ Rn4)> U... U {паз ! (г £ R*)V (г t r") v...v (г £

где А- множество атрибутов отношения R^ , ш $ 1, r»ü?l, 1 £ i $ nv

Пусть виртуальное отношение является разностью отношений R и Q, а L - список атрибутов, на которых образуется абстракция разности. Тогда

R = <r I (г t R) & (rCU^qtU) & (q £ Q)>.

Пусть Ai. ~ (К,а'ц> - множество атрибутов отношения R£, а К -множество атрибутов на которых образуется абстракция - соединения. Пусть далее виртуальное отношение Rj является соединением отношений R^ , Rjl ,... , Rn , n ^ 2. Тогда

Rj = <r(A) 1 (Vm)(l<m^n)(r[An) -rmCA,]) 8, &

(VD(li Un)(l f ni)(rm[Kl = rJKJ) & (rttR()>,

и

где А = U A-l.

L'i.

Отметим, что в схемах каждого фрагмента требуется наличие функциональной зависимости остальных атрибутов от атрибутов, на которых образуется абстршщия - соединения или разности-*. Рассматриваются вопросы ограничения целостности БД. С целью иллюстрация полученных результатов построен пример виртуальной БД.

Во ьторой главе описывается подход концептуального моделирования КВБД, основанный на использовании аппарата исчисления предикатов первого порядка и теории множеств. В рамках УКМД принята однородная модель представления времени п отношениях.

4. основан па многосортном исчислении предикатов первого порядка.

5. Пусть Z « XUY - сх»ма 'некоторого отношения R. В'/ .'уа-.ст-вует функциональная зависимость X - -• Y. если для j^ccvo цс и, г. с R, если гЛХ) -- г„ 1 л]. тогда r-, I V! ■ )\,!'П.

Моделирование в БД временного аспекта достигается посредством двух атрибутов. Имена этих атрибутов зарезервированы и в схемах всех отношений являются одинаковыми. Имя атрибута существования есть VALID, а атрибута доверия - BELIEF. «

Определение. Пусть Т - многлство дав, и на Т задан строгий порядок. Пусть Т и tt& Т, тогда объест

[tt, tt] - It £ Т : tx < t < tj,> U <tt> U <tb>

называется временньв.» отрезков ВО).

Определение. Пусть S=<A,K> является схемой временного отношения T_R, где А - iAL, Aj., ... , А„.VALID,BELIEF) - множестзо

атрибутов временного отношения, а К = 4AU, Atl......VLm ,

EELIEF> - мноязство атрибутов, составляющих главный ключ, 1 с-i-e.5 n, 1 й L Sm. Тогда Sj_ = <A,Ki >, Si. = <А,К>, Sj = <Л,К> -схемы интерпретирующих T_R относений R, S_R и G_R. Здесь (К\ BELIEF}, VALID и BELIEF временные атрибуты , интерпретируемые гак АТД, представляющее ЕС. Отношения R ,S_R и 3_R имеют, следующий содержательный еадюл: г

- R представляет текущее состояние БД 1 *,

- S_R предназначено длл хранения гех кортекэй R, которые подвергались изменению;

- G_R лвляетсл а0стршац!ей-обо51гзнием отношений R и S_R.

Базовыми конструкциями для моделирования времени яелягтсл

АТД DATETHE (ДМВ) и INTERVAL (интервал).

Представление значений АТД DATETII.C могет иметь пид под-кяогвсгва нитаследуюсих смегаь':: ползи: YY : год

МО : месяц а пределах года ГО : день з пределах мосяцз !"! : час в пределах дvn Ш : кинута в пределах часа SS : секунда в пределах ismyrtj FF( n) : доли секунды

Представление значений ЛТД INTERVAL язляетса г.одмгогест-пом смеяапс полэй:

YY : год 1X3 : кесяц

пли .

Ш : день НН : чае Ш : кинута

SS : секунда . • • '

■ FF(n) : доли секунда Конкретная совокупность по.гэл глк в случае АТД DATETIME. тзк и ЛТД INTERVAL задается с поиопгп временного списаюля. АТД DATETIIE и INTERVAL является пграмэтризовшипдая (родопияи) типами. Временной описатель трактуется isn: параметр о того типа. АТД предстаэллется 'совокупностью полинорф.чых функций. Six формальные параметры кткт родопой iris, а фактические гаппметры являются значениями конкретизации этого рслозого типа, осуществляемой • при подстановке параметра. Технически конкретизация осуирствлйотся передачей кс!:::к-етЕого значения аре»»икого опися-

0. Множество коргелей, времени атрибута доверия будущем.

в которых значение конечного мо'.гента раглю Сескинечнсму моменту времени в

- 8 -

геля - параметра родового типа.

Пусть Т - множество ДМВ со структурой АТД DATETIbE, I - множество интервалов со структурой АТД INTERVAL, N = (0,1,2,...}, Е - множество целых чисел, a S - множество ВО.

Дункнии ввода - вывода. Функция INPUT предназначена для преобразования временного литерала во внутреннее представление, а - OUT! UT выполняет обратное преобразование.

Функции преобразовании, функция CURRENT обеспечивает доступ к часам ЭЬЯ ЗначешшйПфункшш CURRENT является текущий ДМВ с точиости> /Y ТО FF( 3). Если аргументом функции CURRENT является временной описатель, тогда значением этой функции является ДМВ, совокупность полей которого задает временной описатель - аргумент функций.

Если аргументом функции EXTEND является только ДМВ, тогда её значением является этот же ДМВ с точностью YY ТО FF(3). Если аргументами функции EXTEND являются ДМВ и временной описз- . тель,тогда ее значением является этот же ДИВ с точностью, определяемой лременным описателем - аргументом функции. На функцию EXTEND накладываются следующие ограничения:

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

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

- если значение функции содержит поля, лежащие правее полей входящих в аргумент функции, то эти добавляемые поля отождествляются с нулем для полей НН, MI, SS и FF(n) и с единицей для полей Mû, DD.

Пусть f одна из функций YEAR, MJNTH, DAY, HOUR, MINUTE, SECOND, FRACTION. Тогда Г определяет следующие отображения:

Г : Т —> N ,f является полной функцией.

f : 1 —> Е ,f является частичной функцией.

функция DAï_0F_>EEK является полной функцией и задает следующее отображение:

DAY_OF _V££K : Т -'--> DOV , где

DOW - ('понедельник', 'вторник', 'среда',...}.

Функция LENQTH является полной функцией и определяет длину

ВО:

LENGTH : S — > I

Функция I„CONVERT является частичной функцией и преобразует аргумент функции на целое число в единицах конечного поля временного описателя аргумента*

I.CONVERT : ! ---> Е '

Пусть Q - <<YY,YY>, <Ю,Ю>, <DD,№>, <НН,НН>, <М!,М1>, <55, ■ SS>, <FF,FF>) -множество временных описателей. функций

SP_CONVERT и SI_CONVERT являются частичными функциями и определяют следующие отображения:

SP_CONVERT : N * Q —> Т SI.CONVERT : Е * Q —-> I

Значением функции NJNTERVAL является значение аргумента функции (значения типа АТД INTERVAL) со знаком минус.

Функций UNION, INTERSECT. IN IT и FIN являются полными функциями и определяют следующие отображения:

INTERSECT : S х S ---> S, определяет пересечение Ю. UNION : S * S —> S, определяет объединение ВО. UNION : Т Т —> S

IHIT : S —> Т, определяет начало ВО. FIN : S ---> Т, определяет конец ВО.

Арифметические функции очевидны: ADD - временное сложение, MINUS -временное вычитание, MULT - временное умножение, DIV - временное деление. Эти функций являются частичными функциями и определяют следующие отображения:

ADD T Я I — > T

ADD I X I — > 1

MINUS T I — > T

MINUS T X T — > I

MINUS 1 A I --- > I

MULT I я N — > I

DIV I К N --- > I

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

Предикаты. Пусть Г одна из функций GE, GT, LE, LT, EQ, НЕ. Тогда Г является частичной функцией и задает следушре отображение:

Г : 1 « I ---> (TRUE, FALSE)

Временные предикаты. Пусть X и Y задают ДМВ или ВО. Перечисленные ниже временные предикаты позволяют определить отношения ыеиду ДИВ и ВО. Предикаты истинны при указанных условиях.

- BEFOREf X,Y) : ДМВ X предшествует ДЬ® Y, или ДЫВ X предшествует ВО Y, или ВО X и Y не перс-крываются и X предшествует Y;

- EQUALS( X, Y) : X и Y одни и те же ДМВ или одни и те яи Ю;

- AFTER( X, Y) : ДОВ X следует после ДМВ Y, или ДИН X встре-'иется позже ВЭ Y, или Ю X и Y но перекрываются и X встречается позде Y;

- DURINGK X, Y) : DO Y включает ДЫВ X, или В.) Y включает BO X (включение понимается при этом так, что начала и конш) ВО X и Y не совпадают);

- STARTS( X, Y) : ДЫВ X совпадает с началом BO Y, или Во X, Y стартуют одновременно и конец X содержится в Y;

- FINI2HE5(X, Y) : конец ВО Y совпадает с ДМВ X, или концы ВО X,Y совпадают и начало X содержится в Y;

- МЕЕТЗ( X,Y) : BO X стартует раньше ВО Y и конец X совпадает с началом Y;

- OVERLAPS X. У) : ВО X стартует раньво конца BO Y и ВО Y стартует раньше конца BO X;

- BEFORE.5T,\RTS(X,Y) : ВО X встречается раньш Ю Y (ВО могут при этом перекрываться);

- BEF0RE_END3( X,Y) : конец ВО X встречается раньше конца Ю Y (Ю могут при этом перекрываться).

С помощью введенных предикатов можно конструировать более сложные предикаты, например, на языко ПРОЛОГ:

Hf(X,Y) :- STARTS(X.Y) ; DURIMG(X.Y) ; FINI5HES(X, Y).

Исходя из временной аксиоматики Аллена* предложено формальное определение семантики временных предикатов с помощью предиката MEETS. Отметим, что формальное определение временных предикатов с помощью предиката MEETS имеет важное практическое значение, поскольку по существу их реализация сводится реализацию предиката KEETS.

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

1) для операц)!и естественного соединения: Т I ill ERSECTC Т А, TäJ для каждой пары соединяемых кортежей. . Если результат пересечения пустой, то соединенный кортеж не попадает в результирующее отношение;

' 2) для операции пересечения отнесений действуют те хз правила; .

3) для операция декартова произведения: Т - UNI0N(TifT.);

4) для операции разности отнооекий.функция преобразования несколько сложнее:

Вначале для каждой пары одинаковых (без'учета временных атрибутов) кортежей определяется t = HITERSECT(Ti,Tj,).

Если t пусто, первый кортеж попадает в результирующее отношение. В противном случае возможны два исхода. Если выполняется durwgct.Ti), то в результирующее othoeshks попадает два одинаковых кортежа, различающихся значениями временных атрибутов. В первом кортеже зто значение равно ВО UNI0N( INIT(Ti), INIT(Tju)) ,а во втором кортеже - UNI0N(FIM(Т^).FIMCTj)). Если DURING не выполняется, в результирующее'отношение попадает один кортеж, значение временного атрибута которого есть ЕО UIII0M( И.'ЩТО, IМITCTi)) или ВО UHION(FIH{Tj.) ,FIM(T.J). 0гкат1И, что в результирующее отношение попадает и те кортежи первого операнда,которые (без учета временных атрибутов) не совпадает с _кортежами второго операнда.

Временная привязка фильтра. Для задания временных срезов на . •

7. Allen J. F. , Hayes P. J. A common - sense theory of tirvj// In proc. or' tie ninth International joint conference cn artificial intelligence, Los Angeles, 19S5. p. 528 - 531.

' - 11 -

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

<временное селектирующее выражение:»::« «селектирующее

выражзние> [ON <селектср>3 t AG ОР<селектор>] «селектор;-: :.= «временная константа> ! <переменная> I

«временная функция> «временная функциям = YEAR ! MONTH ■ DAY ! HOUR I MINUTE I SECOND ! FRACTION ! INIT I FIN ! INTERSECT I UNION I EXTEND I SP_CONVERT

Конструкция ON задает временной срез по атрибуту существования VALID, конструкция AS OF - по атрибуту доверия BELIEF. Селектор задает значение временной константы - ВО или ДМВ.

Конструкций ON и AS OF действуют таким образом, что в тех формулах селектирующего выражения, где не заданы временные предикаты относительно атрибута существования или атриоута доверия, подразумевается предикат ЩVALID,<селектор>) или IN(BELIEF,<селектор>), если селектор задан в виде ВО, или предикат Щ«селектор>,VALID) или 1Н(<селёктор>,BELIEF), если селектор представляет собой константу ДШЗ. Ib умолчанию предполагается селектор равным CURRENT как для AS OF так и для ON.

Агрегатные функций. Введение категории времени позволяет разработать специальные виды агрегатных функций, учитывающих временные аспекты БД. Пусть Г(х, у) - некоторое селектирующее выражение с двумя свободны),m переменными х и у, причем х - аргумент функции.

Функция ASC. Пусть формула имеет вид ASC(x,f(x,y)). Содержательный смысл этой формулы в том, что из множества истинности селектирующего выражения Их,у) выбираются значения у такие, что все значения х, удовлетворяющие вместе с данным значением у селектирующему выражению f(x,y) и упорядоченные хронологически, образуют монотонно возрастающую последовательность.

Функция DESC. Пусть формула имеет вид DESC(x,t"(x,y)). Содержательный смысл этой формулы в том, что из множества истинности селектирующего выражения Г(х,у) выбираются значения у такие, что все значения х, удовлетворяющие вместе с данным значением у селектирующему выражению f(x,y) и упорядоченные хронологически, образуют монотонно убывающую последовательность.

Функция CONST. Пусть формула имеет вид CONSTC х, f"( х,у) ). Содержательный смысл этой формулы в том, что из множества истин -ности селектирующего выражения f(x,y) выбираются у такие, что все значения х, удовлетворяющие вместе о даннйм значением у селектирующему выражению f(x,y), не изменяются во времени.

Сункцйя Т_МАХ. Пусть формула имеет вид T_MAX(x,f(x,y)) ОТ 20. Множеством истинности этой формулы является нормализованное отношение, областями определения которого является t и у. Значением t в каждом кортеже такого отношения является величина максимального ВО, в течение которого максимальное из значений х удовлетворяющих вместе с данным значением у селектирующему выражению f(x,v), больше 20.

¿упкцйя T_MJN. Пусть формула имеет вид T„MIN( х, f ( х, у) ) EQ

10. Множеством истинности этой формулы является нормализованное отношение, областями определения которого является t и у. Значением t в каждом корте«? такого отношения является .величина максимального ВО, в течение которого минимальное из значений к, удовлетворяющих вместе с данным значением у селектирующему выражению f(x,y). равно 10.

Оункнйя Т.COUNT. Пусть формула имсег- вид T_COlWT(x.f(x,y)) ЕQ 10. Множеством истинности этой формулы является нормализованное отношение, областями определения которого является t и v. Значением t. в каждом кортеже такого отношения является величина максимального ВО, в течение которого число различных значений х, удовлетворяющих вместе с данным значением у селектирующему выражению f(x,y), рай но 10.

' ЗуккцЛл T „TOTAL. Пусть формула имеет вид T_TOTAL(x,f(x,y)) LE 10. Множеством истинности этой формулы является нормализованное отношение, областями определения которого является t и у. Значением t в каждом кортеже такого отношения является величина максимального ВО, в течение которого сумма всех значений х, удовлетворяющих вместе с данным значением у селе1стирушему вы-рамэнию Г(х.у), меньше иди равна 10.

Функция Т„AVERAGE. Пусть формула имеет вид T_AVERAGE( х, f(x, у)) GT 5. Множеством истинности этой формулы является нормализованное отнесение, областями определения которого является t и у. Значением t в каждом кортеже такого отношения является величина максимального Ю, в течение которого среднее арифметическое значений х, удовлетворяющих селектирующему выражению Г(>:, у) вместе с данным значением у, больше 5.

Предложено формальное определение семантики функций T_MW. Т _МАХ, TJXHJNT, T_T0TAL и T_AVERAGE с помощью аналогичных Функций УКМД, что имеет важное практическое значение при разработке программного обеспечения. Предложенные формальные определения семантики функций ASC, DESC' и CONST можно использовать а качестве спецификации при реализации этих функций. .

Изменена семантика операторов UPDATE и DELETE. Изменение семантики этих операторов' достигается процедурными средствами УКМД. Частичная поддердка эволюции cxeii БД достигается посредством классических средств ганце птуалыюго моделирования данных в БД. Отметим, что вопросы поддержки временных БД с изменяющимися схемами нуждаются в дополнительном исследовании. Ограниче-иия целостности БД рассматривахтгся в контексте замкнутых формул на языке фильтров. Дана опенка уровня разработанного языка запросов. Сравнение существующими подходами концептуального моделирования 1ШБД показывает, что предложенный подход впитывает в себя лучыие черты этих систем и является их развитием.

Третья глава посвящена проблемам реализации языковых сродств временной ид. Ввиду своего назначения УКМД объективно расслаивается на два подуровня: локально концептуальный Д'-У) и глобально концептуальны^ ГКУ). в распоряжении ГКУ имеется разеитый декларативный аппарат для создания виртуальной БД. В огличие от операторов ЯВД ЛКУ, которые применяются к отноиенилм БД. операторы ЯМД ГКУ применяются к отношениям виртуальной БД. Хотя операторы НМД ЛКУ и ГКУ имеют один и тот ке содержательный смысл в

совпадают по синтаксису, семантика операторов ЯМД ГКУ существенно изменяется. Изменение семантики ЯМД ГКУ связано с тем, что отношения ГКУ являются абстрактными представлениям^обобщениями, соединениями,разностями) других отношения, которые, в свою очередь, являются подобными же производными объектами либо первичными отношениями. Поддержка виртуальных отношений' в БД порождает задачу задания семантики операторов ЯМД над отношениями - абстракциями. Рассматривается два подхода к решению данной задачи:

- на уровне языка алгебраического типа;

- на уровне фильтров.

Алгебраический подход. Для поддерики ЯМД концептуального 'уровня, ориентированного на исчисление предикатов первого порядка , на 'исполнительном уровне используется ЯМД алгебраического типа. Единицей действия, сообщаемой процессом прикладной программы реляционному процессору, является макропрограм-ма(программа на входном языке реляционного процессора). В отличие от фильтров, в которых допускается равноправное использование объектов ГКУ и ЛКУ, реляционный процессор выполняет операции исключительно над объектами ЛКУ. Предложены »алгоритмы для преобразования операторов ЯМД ГКУ в соиокупность операторов интерпретации их действий на ЛКУ. Разработанный блок редукции программ реляционного процессора к локальному представлению выполняет преобразование следующих групп однородных операторов:

- реляционной алгебры;

• " - циклической обработки; I , • - изменения отношений;

- - логических;

• ; - арифметических;

- управления.

! Преобразование фильтров. После трансляции ЯМД ГКУ во входной язык реляционного процессора, единственным путем задания семантики операторов ЯМД ГКУ является алгебраический подход. Альтернатива такого преобразования имеется на уровне фильтров. Для этого необходимо -в фильтрах объекты ГКУ заменять эквивалентным селектирующим выражением на языке фильтров над объектами ЛКУ. Пусть £ (Ч) обозначает множество истинности некоторой формулы1?. Пусть I* - множество атрибутов виртуального отношения .

Обозначим - К где 1аПбт, Тогда

б (IV -

Пусть Ь - множество атрибутов виртуального отношения , 1.1 - список атрибутов на которых образуется виртуальное отношение , ^-тг^ю. Итогда

б ' - IбV £ <Чя.))-Ог.а«01« .. Ю9 . где

И Ц = х^..... хЦ.

Пусть' Ь - множество атрибутов виртуального отношения , а Ц - множество атрибутов отношения и- . 1 г, 1 ^ п. Обозначим

8. ТГ - операция проекции реляционной алгебры.

9. - домел атрибута ,ЧМ.

ь -е,. -Су,*.'

где к1- количество тех атрибутов отношения И*, которые не входят схему отношения 1 ^ 1 'и^ к\ Тогда

т)

б (Rj) = Л £(R;) , где I .i- L;i Л

L \ Li. = <x£i, х*1..... XiK'>.

lie трудно убедиться, что в селектирующем выражении на языке фильтров объекты ГКУ заменяются формулами вида:

Rt г (((...((V )у...) V V V

(((... - • W^iV^ V

.. .v (((... ((H"v<)v<)... m«L)v

RpsRMVi'y,

Rj Зг С С---С (Ri fir R^ & Rj) & ...) & Rrt.j) a R„.

Один из возможных вариантов реализации такого подхода является использование аппарата логического программирования. В этой среде объекты ГКУ можно вырззить с помощью ПРОЛОГ программ и представить в БД ПРОЛОГа в ¡качестве фактов. Таким образом, задача задания семантики предикатов виртуальных отношений на уровне исчисления предикатов первого порядка сводится 1«

- отображению схему ]ВД в БД ПРОЛОГа; -

- интерпретацию ПРОЛОГ - программ для генерирования селектирующего выражения на языке фильтров, в котором участвуют только объекты ЛКУ. ■

Разработанные алгоритмы преобразования фильтров проверены в среде системы ».PROLOG". Дано сравнение предложенных подходое.

Реализация предложенных алгоритмов поддержки временных про- • дикатов, операций над АТД DATETITi и INTERVAL подтвердила эффективность рассмотренного подхода реализации этих операций.

В заключении сформулированы основные результаты диссертационной работы:

1. Предложено расширение реляционной МД для поддержи категории времени в базах данных:,

- определена семантика операций над АТД, задающим временной тип;

- определена семантика временных предикатов с помощью предиката MEETS;

- изменена семантика некоторых операций реляционной алгебры для отражения в них временного аспекта;

■ - разработаны агрегатные секции с временной семантикой;

- разработаны специальные конструкции для задания времен' ных ограничений на уровне Есего фильтра или его подформул..

2. Предложено формульное преобразование для абстракций . обобщения, соединения и разности: семантика виртуальных отношений рздается с помощью формул на"языке фильтров, включающих предикаты БД.

10. ITROLCG. Language reference manual, Budapest.: Dr.ki, 1Э83.

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

4. Разработаны алгоритм и программы поддержки временных предикатов и операций над ЛТД.

В приложении для некоторых временных предикатов приводится доказательство корректности предложенных преобразований с помощью предиката MEETS.

Результаты диссертации опубликованы в работах:

1. Калинпченко JL А. , Шчукян М. Г. Языковые средства временно - ориентированной модели данных( Программирование, 1990, N 5, в печати).

2. Калшшченко Л. Л. , Манукян И Г. Языковые средства концептуального моделирования категории времени в базах дан-ных(Проблемы пн форматики, ИЛИ АН СССР, 1990, в печати).

3. Мануклн И. Г. , Чабан И. А. Проблемы реализации декларативных средств концептуального уровня системы интеграции неоднородных баз данных// В сб.: Распределенная обработка данных и локальные сети ЭВМ. - М.: ШЩТП, 1987,- с. 38 - 48.

4. Цанукян М. Г. Анализ средств концептуального уровня системы интеграции неоднородных баз данных, ориентированных на работу с данными, имеющими различное представление// Веб.: Численные методы в математической физике. М. изд. МГУ, 1986. - с. 143 - 144.

5. Манукян М. Г. Блок редукции программ реляционного процессора к локальному представлению// В сб. Некоторые вопросы вычислительной математики, математической физики и программного обеспечения ЭВМ. - М.: изд. МГУ, 1987 - с. 72 - 74.

iUlXVUtik

МАНУКЯН МАНУК ГАРНЖЕВ1ГЧ

временная модкль даиш

(Автореферат )

Подписана к печати 24.10/30 Формат 60x°U Т/16 0,9 п.л. Уч.изд.л.0,7 Тираж 100 Заказ 671 Бесплатно_■

Ротапринт МАС:КВТУЗ-.'П!Л), 109260,Моеква ,Ап?опаволскпя,Т,;