Введение к работе
Актуальность теш. Основная идея реляционного подхода зак.іи чается в тон. что данные представляются а виде отношении (или, проще говоря» таблице. Манипулирование данными осуществляется < помощь» обычных логических операции, имеющих весьма простую іг-vm глядную интерпретацию на таблицах.
Табличное представление понятно и привычно любому пользова
телю. Благодаря этому пользователь-непрограммист легко овладева
ет реляционными языками. й
С другой стороны, реляционная модель обладает ясной математической семантикой- Она допускает применение мощного логико-матемЛического апппарата.
Совокупность этих свойств делает реляционный подход весьма привлекательным- Зародившись в рамках теории информационных систем, он теперь выходит в разные области применения компьютеров. Появляется реляционное программирование, реляционные модели one рационных систем» пакетов программ, систем автоматизации эксперимента, и т.п- Все это делает изучение проблем реляционной теории весьма актуальным.
Одной из важнейших проблем, возникающих при проектировании систем управления базами данных с СУБД), является проблема выбора языка запросов. Важность указанной проблемы определяется тем, что язык запросов во многом определяет архитектуру системы. Если в ходе эксплуатации выяснится необходимость изменения языка запросов, то это может вызвать перестройку всей системы.
Вместе с тем, это довольно трудная проблема. Ведь заранее предсказать, какие именно запросы будут поступать -в' систему» весьма затруднительно, а порой и невозможно. Дело в той, что информационная система - вешь, как правило, доро. ля и рассчитанная на долгую жизнь. Л информационная среда эволюционирует довольно бистро. Д- ж само появление такого мощного средства, как база данных Ч.;д>, может существенно изменить потребности пользователя.
Поэтому язык запросов должен обладать хорошими абстрактными свойствами, придающими ему гибкость, необходимую для обеспечения живучести системы в условиях непрерывно меняющейся среды. В этом смысле и говорят снесколько неопределенно}, что язык запросов должен быть полным. Однако не ясно, что в точности следует пони-
ні, іі'ііі immioion язика запросов.
(«їгіпр кршериео полнит привлекал внимание исследоьаіелей момента возникновения реляционной теории. Ее. оатвопопижник Е-Ф Jiiinn в in/,-', і. предложил т.н. критерий реляционной полноты. Сут мо заключается в тон, что молний, язык должен быть не слабее язі. и 5 логики первого порядка.
Критерий Кодда считается одним из основных достижении те при 5 '.з данных. Однако он может быть подвергнут критике как с теоре гнческой. так и с практической точки зрения.
В связи с этим были предложены другие критерии полноты, nat-более значительными из которых являются критерий Ф- Банцелої
illancllhon, 197НЗ и Критерий Л.К.ЧаНДрЫ И Д. ХарвЛа CChandrs
іуоої. Все эги критерии рассматриваются в предлагаемой работе.
Критика критерия Кодда связана в основном со статьей А.Ахо Л«- Д.Ульмана с дію a.v., unman j.d. 1о7ш, где показано, что языке пері ого порядка выразины не все полиномиальные запросы, гвлзн с этик возникает следующая проблема" пополнить язык пєрвої порядка так, чтобы в нен были выразины в точности все полинонт лльные запросы.
Решение этой проблемы с при. наличии линейного порядка) и ж )|>.:.тся одним из центральных результатов предлагаемой работы.
Целью работы является анализ существующих критериев полноті liuOdp нового критерия, его обоснование и конструирование язикої удовлетворяющих этому критерию.
Методика выполнения всслгдогззшн. Состояние Д;»1 рп.сматрнв< ется как алгебраическая система. Зто позволяет прии.скни. к/m аппарат математической логики и теории нодилеи. Наличие r.n'iivrtin го порядка на универсуме позполж г ииделировлп. у г"'"ту .' -.-іч 1м ринга в терминах БД.
Научная новизна. Все основные результаты диссертации ярл-т^ ся новыми. Языки полиномиальных запросов были описаны авторі (Лаяіак, I2Q2a) (Лавчак, 1502ь) наралг'-м ни с М-Им^ернат СІИШКЇГІВЛП, юогэ и М. Варди tv.-irdy, ionnj .
Приложения- Изучение іюіг.шинкаяшіх >nu.>;ou получили сузіес генное развитие по слелухлин направлениям. Пп -первых. п"Я!-шш работы, в которых обобщатся v ;\'"опіпаш'.:я пол гп-чци-' р--">/і!і i;ju В частности, делаются ікнчпі'г v і^-ірнться іч .ччнчімигіі п'.р^ль'.
- в
перенести полученные результаты на другие структуры (l)ubiisi. 1990), CLindeii, i9!jn, изменить форну оператора неиодшшіои ІИЧ
КИ CAbiteboill, 1989), CAbiteboul, 1990), CArvind, 1UH7), CGurevlch, 1985) II Т.Д. BO-BTOpllX, ПОЯВИЛИСЬ ИССЛеДОЬЭНИЯ, tl"'IU>
торых изучаются "абстрактные" ст.е. не связанные напрямую с зада чами теории БД) свойства полиномиальных языков cA|tai, ion7>,
CBlass, 1985), CBorger, 1989), CGurevlch, 1904), (. Gin evi.'li,
lOOfi), CGurevlch, 1987) И Др.
Апробация- Результаты работы докладывались на конференции "Автоматы, алгоритмы, полугруппы" сСвердловск, і они), школе-семинаре "Семиотические аспекты формализации интеллектуальной деятельности" стелави, 1984), конференции "Искусственный уп теллект и распознавание образов" сКие> . 1984), на Уральском мате -натическом обществе сСвердловск, ioes), на выездном заседании секции "Информатика" Научного совета по комплексной проблемне "Кибернетика" сСвердловск, 1987) и др.
Публикации. По теме диссертации опубликовано із работ. Исследования, отраженные в диссертации, проведены без соавторов.
Структура диссертации. Работа содержит іга страницы машинописного текста. Она состоит из введения, трех глав н заключения, а также сводки обозначений и списка литературы, содержащего пв названий.
