автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:О критериях полноты (Математические аспекты выбора языка запросов)

академия наук российской штглшш

МЧИСЛИ1ЕЛМ1Ш lll'ïlïl-

" ¡1 р. i О .

v i )

> , t ,, ,

¿ ¿ Î'ïûîi twwJ l1' пр-т-к i'VKmiii'.it

X'f

Пимчнк АпиК1,анп|1 r¡i)|jii(.(ii)il'i

'/.'Iii - I''- "<

«S i

о пригкриях полили

сН этемаппяскни а<жкти нибпра язи на з ¡ицлн пн>

04.ii.it - натинсничискои и (фигромишк! пбоитчешш шпмплителмшх мадии, ппншюш.он, систем н re ген

Аиторнфира!

ЛШХРрЫШШ 1Ы ОИИСНЛНИО ■ JUHHfJIl i.l'HIltMIM

кл|1л11л-п<! ф1пик1/-и<1тг/натич1тких пеун

Hui КП.Ч -

-л-

РчОигл выполнена на кафедре информатики и процессов управления Уральского государственного университета

Научный руководитель:

чл.-корр, АЕН РФ. д.ф.-н-н. Третьяков В. К.

Официальные оппоненты:

академик РАН, л-ф. -н-п. Журавлев >). И-, д.ф.-н.н. Боршев В-Б-

Ведущая организация:

Институт математики и механики УрО РАН

.->, Защита состоится ■■Ж ■■ 199Э Г.

/Ъ 0 ■ #

и' ' часов на заседании Специализированного совета К.оог.эг.си при Вычислительном центре РАН по адресу 117907 Москва, ГСП 1, ул- Вавилова, д- 40

/

С диссертацией можно ознакомиться в библиотеке Математического института РАН. .

Автореферат разослан [" I паз г.

Ученый секретарь Специализированного совета ЦЩЧ к.ф.м.-н. Рудаков 1С-В.

Актуальность темы. Основная идея реляционного подхода заклы чается в тон. что данные представляются и виде отношений сиди, проще говоря» таблиц?. Манипулирование данными осуществляется < помощью обычных логических операции, имеющих весьма прпглую ir-vi-i глядную интерпретацию на таблицах.

Табличное представление понятно и привычно икбому пользователю. Благодаря этому пользователь-непрограммист легко овладевает реляционными языками. й

С другой стороны, реляционная модель обладает ясной математической семантикой- Она допускает применение мощного логико-матемЛического апппарата.

Совокупность этих свойств делает реляционным подход весьма привлекательным- ЗародЙвшись в рамках теории информационных систем. он теперь выходит в разные области применения компьютеров. Появляется реляционное программирование, реляционные модели one рационных систем, пакетов программ, систем автоматизации эксперимента, и т.п- Все это делает изучение проблем реляционной теории весьма актуальным.

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

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

ля.

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

■ni, li'ui ii'ijnu'ifiii языка запросом.

í«¡rifi|) кригериеи полнот привлекал внимание исследиьаюлчй MíiwfiiTr) возникновения реляционной теории. Ке ск.новшюпожник Е-Ф Juinn о in^. i. предложил т-н- критерий реляционной полноты. Сут ■го заключается в тон, что полный язык должен бить не слабее язи иj логики первого порядка.

Критерий Кояда считается одним из основных достижении тепри 5 ¡3 данных. Однако он может быть подвергнут критике как с теоре гнчоской. таи и с практической точки зрения.

В связи с этим были предложены другие критерии полноты, nal1 Оопее значительными из которых являются критерий Ф- Банцелог í Папе И hon, Ш7НЗ и Критерий Д.К.ЧаНДрЫ и Д.харела CChandrs и.юоэ. Все эги критерии рассматриваются в предлагаемой работе.

Критика критерия Кодда связана в основном со статьей А.Ахо Л г- Д.Ульмана сльо a. v., unman J.D. 1979), где показано, что языке nepiого порядка выразимы не все полиномиальные запросы-г вязи с этик возникает следующая проблема" пополнить язык пдрвог порядка так, чтобы в нем были выразимы в точности все полином» яльные запросы.

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

Цель» работы является анализ существующих критериев полнотт шОор нового критерия, его обоснование и конструирование язико! удовлетворяющих этому критерии.

■ Уатодяка выполке1ШЯ исслгдоЕзшн. Состояние Д;!1 рп/.матриц отся как алгебраическая система. Это позволяет принцип. к/ Hi аппарат математической логики и теории нодилгш. Наличие r.rmvftin го порядка на универсуме позполж г нивелиромгь pa'V-ту н-ч 1м finura в терминах БД.

Научная шлшшш. Все основные результаты днссерыпии ярл-г^ ся новыми. Языки полиномиальных запросов были описаны anropi (Яагпак, 1582«) (Лавчэк, 1902ь) иаралг-м ни с li. Мняррпаш С I ппюгтяп, юогэ И И. [ЗардИ tV.-irdy, 10Я2) .

Приложения- Изучение полллияюльних юыпеи полуш/ш с>яех' генной развитие по следующим направлениям- Пм -первых. п"Я!-шш работы, в которых cdodtaom ся м :\1-ч>ип;!»н:я пол гечни-' р:">'/j:i kui В частности, делаются гнтим'г р «Гчииться р: Л'ш< иного р'.р-!,-,к-

- в

перенести полученные результаты на другие структуры (Ъиьп^а. 1990), С1лп<1е1], 19!Л), изменить форну оператора неподвижном юч ки САЫ1еЬои1, 1909), САЬИвЬои1, 1990), САгу1пс|, ш«7), соигиу1сЬ, 1983) и т.д. Во-вторых, появились исследования, ц/|и> торых изучаются "абстрактные" ст.е. не связанные напрямую с зада чами теории БД) свойства полиномиальных языков сл|»а1, юв7>,

СП1а55, 1985), СВогдег, 1989), СГ,чге*1сЬ, 1904), < От еу1 <-Ь,

■э

1986), {6игв*1сЬ, 1987) И Др-

Апробация- Результаты работы докладывались на конференции "Автоматы, алгоритмы, полугруппы" сСвердловск, юад>, школе-семинаре "Семиотические аспекты формализации интеллектуальной деятельности" сТелэви, 1984), конференции "Искусственный уп теллект и распознавание образов" с Кие р , 1984), на Уральском мате -матическом обществе сСвердловск, ювз), на выездном заседании секции "Информатика" Научного совета по комплексной проблемно "Кибернетика" сСвердловск, 1987) и др.

Публикации. По теме диссертации опубликовано 1з работ. Исследования, отраженные в диссертации, проведены без соавторов.

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

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

Мы пользуемся стандартными средствами натемчтической логики. Этот подход не является оригинальным. Близкие точки зрения можно найти, например, в работах сБорщев, 19В1), сБорщев, 197а> и сРазмыслов, ют). Однако достаточно последовательно этот подход, по-видимому, не развивался. Применение его позволило, как нам ка жется, упростить формализацию основных понятий.

Приведен основные определения.

Пусть имеется некоторое множество им, которое мы будем назы-!' нь универсумом, и нножество ат, элементы которого называются отрибутами. Пусть * е *т, М £ иы. Кортежей типа а над М назовем ¡ункцию г ! а —> м , сопоставляющую каждому атрибуту а с а его течение гСа? «? м. Всякое множество таких кортежей будем называть отношением типа а над М. Совокупность всех кортежей типа а над М г;удем называть А-й декартовой степенью множества М и обозначать как к*. Т-о., всякое отношение к есть подмножество декартовой степени м*. где а - Асю - некоторое множество атрибутов, называемое типом отношения я.

Отношение удобно изображать в виде таблицы- При этом заголовки столбцов трактуются как атрибуты, а строки таблицы - как кортежи- Универсум трактуется как множество, содержащее все элементы, которые могут встретиться в таблицах, хранящихся в БД-

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

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

Пусть имеется сигнатп>& состоящая из конечного набора

постоянных предихатшх символов бс - < р1, гг, ... , Рк> и бесконечного набора переменных предикатных символов зд - < сц, аг, >- Постоянная спеременнаяэ. часть сигнатуры состоит из конечного с бесконечного? набора постоянных с переменных? предикатных символов, интерпретируемых как имена базисных с производных? отношений-Т.о., предикатные символы есть ни что иное, как имена таблиц-

Состояние БД - это модель эгт сигнатуры бу^ т.е. пара эт -■ с-м, где и - м^ - некоторое множество, называемое носителем состояния эт, а I » - функция, сопоставляющая каждому предикатному символу я из эт его значение 1С5?, являющееся отношением над м. Значение синв'ла х в состоянии ят мы будем обозначать еще и как Т.о.. ^эт « Состояние яг называет'

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

ношения.

Мы говорили, что всякое состояние ест в интерн[ I-1 лии. сигнатуры зу. Однако, не всякая интерпретация нижет Сын, в д>.чи I вительности состоянием БД. ;

В связи с этим вводится в рассмотрение класс допустимы* оосго яний кь. Вообще говоря, им может быть любой подкласс класса вес-:.; состояний. Однако, особый интерес представляет случай, копы зил класс задается конечным числом ограничений целостности <плн, в логической терминологии, аксиом).

Запрос - это частичная функция г, сопоставляющая сом пинию из и. некоторие отношение геэт) над м^. Отношение л«) называется ответом на запрос г в состоянии ят.

Как же пользователь'сообщает свои запрос системе? Очевидно, для этого нужен специальный язык-'

Язык запросов - это пара , гьэ, I де Ф, - множество фор-

мул языка ь, а Т( - функция, сопоставляющая каждой формуле к из ^ и состоянию я из и. некоторое отношение т1«=сг,ят), называемое значением формулы г в состоянии эт. Заметим, что если п^....^*^ - формула обычного логико-математического языка (.например, логики первой ступени), то ее значением будет отношение тек,бт) -<{*,...,»)! бт |.« гсх , ....к э> - множество всех кортежей, на которых она истинна.

Скажем, что запрос г выразиы в языке и если существует формула к е такая, что гсэт)=т<г,чт) для любого допустимого состояния бт. Множество всех запросов, выразимых в языке I. будем называть выразительной силой языка 1. и обозначать как ерс!.). Язык ь реляционно полон, если он обладает выразительной силой не меньшей, чем язык УИП, т.е. если ерсЬ) а ерсУИЬ>.

Вышесказанное позволяет определить такие понятия, как база данных сБА и система управления базами данных (СУБД).

Основной функцией СУБД принято считать выдачу ответов на запросы. Для простоты мы абстрагируемся от остачышх ее функций.' Тогда СУБД можно трактовать как алгоритм А1, который по каждой формуле г языка запросов и по каждому допустимому состоянию 5гт вычисляет ответ пг.чп. БД можно трлк [ орать как |рпнку < ь, кт., ль), где ь - язык занрог ин, м - кла< с липу гииых со( г мяний. а А1. -СУБД.

- я

Конечно, такое определение БД не является исчерпывающим- Скорее, оно отражает БД лишь с точки зрения пользователя- Однако, во многих случаях оно оказывается полезным- В частности, в гл. г оно ¡¿I.пользуется для анализа критериев полноты.

Из абстрактных критериев, говорящих о том, каким должен быть /ороший" язык запросов, наиболее известным является критерий ре-чяционной полноты сссхм, 1972э. Как уже отмечалось, этот критерий теоретически не обоснован. В п- г-г рассматривается попытка Банке лона свапс1д Ьоп, дегаэ обосновать его.

Пусть эт - состояние, п —> м^ - взаимно-однозначная

1уккция, отображающая носитель м^ в себя, а а £ ат - некоторое множество атрибутов. Скажем, что отношение я £ м^. стабильно относительно если г «= «г <«»> 1т е й для любого г из м^. «здесь о - суперпозиция функций г и п. Функция г называется ввтоморфазиом состояния ет, если для любого предикатного символа и из эу о гноение Iэ)5гг стабильно относительно г. ,

Отношение и £ называется яг -стобилышл, если оно стабиль -

о

н) относительно любого автоморфизма состояния эт.

скажем, что отношение к £ м^. формулъно в языке I., если существует формула к языка ь такая, что е-т^г, бтэ. Язык 1- полон по Башцшжу, если для любого допустимого состояния эт любое :;т-стабильное отношение форнульно в ь.

Форнулу вида с э ^э.-.с э где г - формул-ч УИП, не со-

держащая кванторов, будем называть Е-форыулой- Язык Е-форнул бу~ ,чпм обозначать символом ьЕ. '

.Теорема 1. Язык Ц. полон по Банцелону, но не рел«щи -г.Ь'ПО полон. ' . /

Из теоремы 1 и тот о факта, что ЗИП полон по Башшлоиу (ВаисНЬоп, 1В78), следует, что критерий БанцЬлоил слабее, чем критерий реляционной полноты.

Остановимся на содержагьг ной стороне критерия Банцелона.

Для простоты будем считать, что некоторый предикапшй символ б любом допустимом состоянии бт интерпротируется как отношение линейного порядка на М,-г. В этом с.луие нетривиальных автоморфизмов нет. Поэтому если язык I- полон пи Гэнцолону, "го <■ при 1ыеи) НрРЛППЛПЖОНИЯХ? ДЛЯ любого допустимого СОСТОЯНИЯ И Л^бою 01 ношения к сутрогвуе г формула г языка г. 1лк?ч, -и о к = т) с I. яп.

Заметин, чго формула f может зависеть от состояния эт.

Рассмотрим некоторый запрос z. Напомним, что ответ zcsn в состоянии st есть отношение над м^. При нашем предположении в полной по Банцелону языке l будет выразим любой ответ zcsd. Однако, это еще не гарантирует, что в нем будет выразим запрос т.е. что будет существовать единая форнула г такая, что zcsd « tlcf, st) для всех st.

Т.о., критерий Банцелона может гарантировать скорее полноту некоего 'языка ответов', но не языка запросов. В этом смысле нож-но сказать, что критерий Банцелона теоретически не обоснован.

Еще один критерий полноты был предложен А-К.Чандрой и Л-Ха -релон с chandra, 1980). Они называют язык полным, если в нем вырэ-зини все вычислимые запросы смы будем называть такие языки универсальными). Однако такой критерий не является, по-видииоиу. рабочим. Дело в тон, что универсальный язык запросов не попускает эффективных оценок времени ответа. В общих чертах этот факт хорошо известен, но ввиду важности его в контекся -теории БД. mi рассмотрим его более подробно.

Скажем, что СУБД al допускает эф£зктшзнуи оценку врекеиз получения ответа, если существует рекурсивная функциг г такая,

что О < f С f, ST) - t^CF, ST) < по ДЛЯ ЛЮбОЙ формулы f « Í>L И ЛЮбого состояния st е kl. Здесь t cf, sp - время, затрачиваемое СУБД al для вычисления ответа,на запрос f в состоянии sr. сЕсли ответ не определен, то полагав! t^cF, sn " оо)-

БД cl, kl, al) назовем слошюй, если сущесгвует'алгоритм, кото рый по любой фориуле f языка l строит допустимое состояние эту. причем разным формулам соответствуют разные состояния. Иными словами, требуется, чтоПы множество 1>V изоморфно вкладывалось в kl.

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

Теорема я. Пусть БД <l, kl, al> - сложная. Если язык i.-универсален, то СУБД ai. пп допускает эффективных оценок времени получения чтпета на запрос.

Итак, ни пднн )п ичррслмну критериев полнот« не является

- ю -

, 1 ,

вполне удовлетворительным. В связи с этим мы предлагаем критерий

сложностной замкнутости, который обсуждается в п- 2.4.

Пусть фиксирована некоторая мера сложности вычислений с, например, время счета. Т.о., каждому алгоритму Аь и каждому состоянию эт сопоставлено число ссаь, бтэ - сложность работы алгоритма а1. в состоянии эт. Скажем, что алгоритм ац не сложнее алгоритма а1-в, если ссац.эт) < ссаь2,этз для всех допустимых состояний эт кроме, может быть, конечного числа.

Скажем, что запрос 21 не сложнее запроса 22, если для любого алгоритма а1-г, вычисляющего г2, существует алгоритм ац, вычисляющий такой, что аь1 не сложнее, чем аь2. Нетрудно видеть, что отношение ".быть не сложнее" рефлексивно и транзитивно. Т.о., оно является квазипорядком на множестве всех запросов. Мы будем обозначать его символом < .

Язык ь назовем сложкостко замкнутый (относительно меры сз, если для любых двух запросов и г2 справедливо!

С г, е ЕРСЬЭ «. < е. Э --> е ЕРС1_Э,

1 2 с 1 2

т.е. Рели из того, что выразим в ь, а г2 не сложнее,чем следует, что и '¿г выразим в ь.

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

Чтобы пояснить идею сложностной замкнутости, рассмотрим следующую метафору. Допустим на минуту, что полиномиальность является формальным аналогом 'практической вычислимости". Тогда язык, е котором выразимы в точности все полиномиальные запросы, будет действительно полным, расширять его заведомо не придется, поскольку все, что можно практически вычислить, в нем заведомо выразимо.

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

Кроне рассмотреных критериев полноты, имеется еще один, предложенный А.К. Айламазянои и М-М-Гилулой в сАйламазян, 1воз). Однако туманность формулировок не ппзволяяет однозначно интерпретировав критерий Анланазяна 1'илулы.

случаи жизни.

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

Требование сложностной занкнутости языка запросов представляется весьма естественным. По сути дела оно означает, что класс всех запросов, выразимых в языке ст.е. его выразительная сила), является сложностным классом. Языки запросов, обладающие этим СВОЙСТВОМ, изучались В работах Clmmerman, 1982), CVardi, 10833, сЛинчак. 1982а), сЛивчак. 1082Ь) и др. Однако в контексте критериев полноты это свойство по-видимому не обсуждалось.

В главе з рассмотрено несколько языков, каждый из которых является сложностным замыканием языка УГО. В каждом из этих языков выразимы в точности все запросы, вычислимые за вреня, полиномиальное относительно объема БД. сТочнее», относительно объема носителя соответствующего состояния. Как и в предыдущей главе, состояния предполагаются конечными.)

Для простоты изложения ны ограничимся рассмотрением только таких СОСТОЯНИЙ ST, 4ip m^j. СНОЩНОСТЬ НОСИТвЛЯ СОСТОЯНИЯ st3 больше единицы.

Мы будем предполагать, что некоторый предикатный символ, например Pj, интерпретируется в любом состоянии st как отношение линейного порядка на носителе н^. Иногда мы будем обозначать этот порядок также символом <■ Для простоты.изложения ны будем считать, что носителем любого допустимого состояния является начальный отрезок натурального ряда свключая' о), a задает на нем естественный порядок-

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

Фиксируем некоторнй линейный порядок на множестве всех атрибутов at ню отношению к БД этот порядок является внешним, т-е. соответствующее отношение не является базисным)- Этот порядок мы будем такте изображать символом < схотя это и не вполне

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

Это позволяет изображать кортеж г ,.в виде последовательности

г^а15, гСа2), .. | Са(1), ГДе асг) • <а1,---• "пу ~ ТИП Кортежа г,

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

Фиксируем некоторое состояние эт. Тем самым фиксирован универсум М^. упорядоченный отношением [Р^ет. Пусть а - некоторое множество атрибутов, а - натуральное число. Символом г^хС1:> будем обозначать 1-ый кортеж декартовой степени н^. в лексикографическом порядке. Мы будем писать просто гею, если ясно, о ка£их ет и а идет речь.

Символом и^сгэ будем обозначать номер кортежа г в декартовой степени > упорядоченной лексикографически.

Кодом отношения к ->е н£г:> назовем, последовательность ь2,... >, где есть 1', если гС1э принадлежит «г, и о в противном случае. Кодом основного сос.ояния бт назовем последовательность ьсст) - < ыг0, ы^, ... >, где - 1Р11эт - 1-ое базисное отношение.

Кодирование отношений и состояний в виде последовательностей нулей и единиц позволяет применять к БД аппарат теории машин Тыо-ринга.

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

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

Запрос г полиномиален, если он вычисляется некоторой полиномиальной машиной Тьюринга.

В гл. з описано два языка - рсл. и УИП+, в каждом из которых выразииы в-точности все полиномиальные запросы.

Основным элементом языка РФ. является программа. Действие любой программы П заключается в том, что она присваивает перемен-

ним предикатным символам Qj, Og, ... значения iQjin, K^irt, ... . Программу П можно трактовать как оператор, переводящий БД из не ходкого состояния st в заключительное состояние IRstj.

Язык pql определяется с помошью следующих правил» i. Пусть Q - переменный предикатный символ арности n, f - формула УИП с п свободными индивидными переменными. Тогда програнна cq:=»tfj принадлежит pol. В результате выполнения этой программы предикатный символ q получает значение Ty^pCF, sr>, где sr - текущее состояние БД- Остальные предикатные синволы не неняют своих значений. Более формально семантика программы cq»-tf:> определяется так: [q1cq: «tf5st - ty^cf, stt3 ДЛЯ Любого СОСТОЯНИЯ stf есЛИ s - предикатный символ, отличный от Q, то isicq:«теэтэ » tsiST. г. Пусть программы IIj и Г^ принадлежат pol. Тогда их суперпозиция сП^ПрЭ также принадлежит pol.. Выполнение этой программы заключается в последовательном выполнении программ Г^ и П,. Более формально! cIIjS^cstj - с^сГ^сстээ.

з. Пусть П - програнна pql, a q - переменны1) предикатный символ. Тогда программа c«hiie q с Ю)П do П> также принадлежит pol. Выполнение этой программы заключается в циклической выполнении программы П до тех пор, пока истинно услопие q с НЛП Зп^сь Ю'П - это значение символа о после выполнения прогроннн П, а условие q с юШ означает строгое теор^тико-чнотествонноо включение соответствующих отношений. Т.о., sr » с »mi» о с- Ю)П >1» П э t > если и только если супес.вует посчедовательность состояний ^Tj. sra, ... , srk такая, что ™ Ifcsr^, п;15г( ¿ !Qifn-JtJ для

всех i<k, i 'OisTfc с юШгзтэ и sr кт .'

т е о р о и а з. Всякий полиномиальный, запрос выразим в ке pql.

Творен а Всякий -■чпрог, омразиный п pol. гкшшот?-ален.

fitw. уип* получается, если к обичнчм правилам_ оСразиоанил форму" п ЛОТ .|..башпь ет° лпа»

i. Если f - формула» Q - переменный предикатный символ, арность которого равна числу свободных индипклннх пвррненних В f, то вн-ратение vCF, о> есть формула.

г. Если f и п - фррнул». о - переменный предикатный сшшол. арность которого рарча числу ст^олт«; индивмгшых пороучтш* о í-op-

нуле g, то выражение sCF,q,g) есть формула. .....

Вхождениь-переменного предикатного символа Q в формулу f,называется свободный, если оно не содержится ни в какой подформуле В^да vCtí, Q) или sCF, Q, G)

; Формула vcf.q) интерпретируется как бесконечная дизъюнкция« vCF,o> - ve i>o >, где Фц-f, о,Ф> ). семантика

же формулы scf, р. G) определяется так. Пусть <>1 получается из о переименованием всех связанных индивидных переменных так, чтобы они не встречались в f. Тогда формула síf, о, ю эквивалентна результату замены в f всех свободных- вхождений символа Q на е

сточнее, подформула QtXj.....хпэ заменяется на результат замены в

в свободных индивидных переменных на xJt...,xn).

Теорема в. Всякий полиномиальный запрос выразим в языке

па*.

Теорема е. Всякий запрос, выразимый в УГО+. полиномиален.

Попытаемся взглянуть.»а затронутые проблемы с общелогической точки оврения- Почему стандартный логический аппарат оказался не вполне адекватен задачам теории БД? Впимо, потому, что он приспособлен В ОСНОВНОМ К бесконечным структурам CGurevich, 1984), а БД существенно конечны. Значит теория БД ставит перед логикой задачу развития теории конечных моделей. В связи с этим в работах

CBorger, 1Q85), CGurevich, 1QÜ6), CGuievich, 1087), CStockmeyer,

loar) и др. рассматриваются некоторые абстрактно-логические свойства языков типа pql, УИП+ и др.

ю. Гуревич CGurevich, 1984). CGurevich, 1087) трактует ЯЗЫК

УШ1+ как расширение УГО с помощью специального вида оператора неподвижной точки ст. н. раздувающей неподвижной точк"). Такой рзгляд весьма интересен, поскольку известен и другой язык полиномиальных запросов, который получается добавлением к УИП оператора наименьшей неподвижной ТОЧКИ Clemerman, 1082), CVardl, 1982). Основное прагматическое различие между.этими языками заключается в том, что оператор наименьшей неподвижной точки можно применять

Весьма интересной представляется с;вязь указанных работ с работами & В.Сазонова. Сазонов идет как бы в обратном направлении - от логики коночного сямогю», 1 поо) к 1еории баз данных (Сазонов, 1007, юао).

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

Как уже отмечалось, при наличии линейного порядка и в том, и в другом языке выразимы в точности все полиномиальные запросы. Ю.Гуревич и Ш.Шелах показали се.1ге*1съ, 198в>, что эти языки будут эквивалентными и при отсутствии линейного порядка.

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

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

запросы.

По теме диссертации опубликованы работы»

СЮ91) Ливчак А-Б. Реляционны? модели баз данных и полиномиальная вычислимость. ✓✓ НТИ, сер. г, 19В1, м е, с. го-го. И

сюпга) Ливчак А.Б. Язык полиномиальных программ- " Расчет и оптимизация теплотехнических и электрохимических объектов с помощью ЭВМ, Свердловск, 1982, с. 40 ,

с1яогы Ливчак А-Б. Язык полиномиальных запросов. " Тан те,

с. 41. '

СЮ8ЙС-) Ливчак А-Б. Реляционная модель систем автоматического эксперимента. " НТИ, сер.2, ^oaг, н 4, с. 17-ю.

' с 1983а) Ливчак А-Б- Реляционная модель управления процессом. " НТИ, сер. г, юаз, и с. 27-г*1.

С1983М Ливчак А. Б. Сложностний анализ реляционных ягн.чов " Тез. докл. научн.-техн. совещания "Логико-алгсбрпччпски«' по дели представления знаний в экономических, технических срг-чни-

- 1 ö -

Зационныл системах". Ашхабад. юаз, с. зг - 34.

uae<j) Ливчак A.B. Сложностная гутмкнутость реляционных язы кив Тез. докл. и сообщ. конференции "Проблемы искусственны о ,'нгеилекта и распознавания образов" Киев, 1ов4, с. юа-по.

, ciue4b) Ливчак А.Б. О семантической силе языка запросов. ИГИ, Сир. 2, 1084, N г, с. 30 -31.

ciaes«) Ливчак А.Б. О полиномиальной вычислиностн. " Известия ВУЗов. Математика, 1ввз, н i, с. ой-67.

HBubbj Ливчак А-Б- Полиномиальные запросы к реляционным Чаз'ан данных. s* Программирование, laas, н г, с. wwa

ciseoa) Ливчак А.Б- Сложностный анализ реляционных языков. " Вопросы кибернетики, лып. 14о, М., Паука, 1шш, с. нг-оа. о • ■ . , ■

осшвы Ливчак А. Б.. Неоднородные отношения! язык запросов и контекстные ограничения. ✓✓ НТИ, сер.г, юна, н \г, с. 17-1ы.

с 1001> Ливчак А-Б- Некоторые понятия реляционной теории баз данных, ss Логические методы в компьютерных науках - М-, Utöi, с. 107—124.

Подписано ь пичати Ш.06.19Э5. Формат 60x04/1(3

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

Обьем <,0 уч.-изд.л. Тираж 100 экз. Заказ (f

BecnaaîHO. Уральский ун-т. 620083, Екатеринбург, пр. Ленина, fil

"Ышлзборатория УрГУ, 620083, Екатеринбург, пр. Ленина, iîl