Теорія програмних алгебр композиційного типу та її застосування

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

Київський національний університет імені Тараса Шевченка

УДК 681.3.06

Теорія програмних алгебр композиційного типу та її застосування

01.05.03 - математичне та програмне забезпечення обчислювальних машин і систем

Автореферат

дисертації на здобуття наукового ступеня

доктора фізико-математичних наук

Буй Дмитро Борисович

Київ 2002

Дисертацією є рукопис.

Робота виконана на кафедрі теорії програмування факультету кібернетики Київського національного університету імені Тараса Шевченка.

Захист відбудеться 26 вересня 2002 р. о 14 год. на засіданні спеціалізованої вченої ради Д 26.001.09 при Київському національному університеті імені Тараса Шевченка за адресою: 03127, м. Київ, пр. Глушкова, 2, корп. 6, ф-т кібернетики, ауд. 40 (тел. 252-58-83, факс 252-59-77, e-mail: rada@unicyb.kiev.ua).

З дисертацiєю можна ознайомитися у Науковій бібліотеці Київського національного університету імені Тараса Шевченка за адресою: 01033, м. Київ, вул. Володимирська, 58.

Автореферат розiсланий 22 серпня 2002 р.

Учений секретар спеціалізованої вченої ради В.П.Шевченко

алгебра дескриптивний маніпуляція

1. ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Об'єктивна тенденція розвитку сучасного суспільства характеризується застосуванням інформаційних технологій у різноманітних сферах. Розробка, впровадження та супровід програмних систем, що реалізують інформаційні технології, наштовхуються на значні труднощі, які носять принциповий характер. Вимоги надійності, ефективності, відкритості, передбачуваності до програмних систем потребують формальних моделей на всіх етапах життєдіяльності програмного забезпечення. Труднощі застосування формальних моделей пов`язані, по-перше, з абсолютизацією інтуїтивної основи при уточненні визначальних категорій (програм та програмування як процесу синтезу програм) та, по-друге, з використанням формальних моделей, неадекватних у повному обсязі предметній області. Сам факт наявності багатьох стилів програмування (структурного; функціонального чи, за іншою термінологією, денотаційного; логічного; об`єктно-орієнтованого; візуального; модульного чи, за сучасною термінологією, компонентно-орієнтованого та ін.) свідчить не лише про безсумнівні досягнення сучасної комп`ютерної науки, а й про відсутність загальноприйнятої концептуальної платформи. Спроби виходу з такого незадовільного становища робилися В. М. Глушковим, К. Л. Ющенко, А. П. Єршовим, В. Н. Редьком та їх учнями.

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

Труднощі застосування існуючих моделей до реального програмування, пов`язані в першу чергу з нехтуванням вимоги експлікативності моделей предметній області (експлікативність у розумінні Р. Карнапа: по-перше, формальність моделей у загальноприйнятому розумінні та, по-друге, їх адекватність предметній області, що моделюється), добре усвідомлюються та здійснюються спроби їх подолання: створюються нові стилі програмування об`єднанням існуючих (функціонального з логічним, алгебраїчного з логічним та ін.), розробляються нові формалізми. Аналіз причин сучасного критичного стану в застосуванні формальних моделей до створення складних промислових програмних систем дозволяє сформулювати наступні вимоги, яким повинні задовольняти сучасні моделі програм:

експлікативність;

композиційність (уточнення семантичних структур програм у вигляді композицій - спеціальних алгебраїчних операцій у класах функцій, що виступають семантиками програм);

інтенсіональність (зміст понять, їхня структура);

явне використання структур іменування;

чітка витримка рівнів абстракції моделей.

Серед потенційно можливих моделей, які задовольняють наведеним вимогам, у дисертації обрані програмні алгебри композиційного типу, які базуються на композиційному програмуванні, закладеному в працях академіка В. Н. Редька у 70_х роках минулого століття. За поставленими задачами та методами їх вирішення робота розвиває експлікативне програмування. Реальні теоретико-практичні досягнення побудованій у дисертації теорії програмних алгебр композиційного типу і можливість застосування цієї теорії до нагальних потреб практичного програмування і визначають актуальність дисертаційного дослідження.

Зв`язок роботи з науковими програмами, планами, темами. Дисертаційна робота є складовою частиною наукових робіт, які ведуться на кафедрі теорії програмування факультету кібернетики Київського національного університету імені Тараса Шевченка (КНУ) при виконанні фундаментальних та прикладних тем: “Дослідження універсальних та спеціалізованих програмних логік” (№ 0197U003444, 1997-2000 рр.), “Побудова і дослідження програмних логік, що лежать в основі сучасних CASE-технологій” (№ 0101U002163, 2001-2005 рр.), “Дескриптивні CASE-технології генерації професійних систем програмування” (№ 0195U016803, 1995-1997 рр.), “Дослідження програмних алгебр композиційного типу” (№ 0198U002032, 1998-2000 рр.), “Еталонування семантичних структур мов CASE-середовищ програмологічними засобами” (№ 0101U005770, 2001-2003 рр.), “Розробка та реалізація підсистеми віддаленої актуалізації даних в засобах обліку державних службовців” (№ 0198U007174, 1998 р.).

Мета і задачі дослідження. Метою дисертаційної роботи є конструювання формальних моделей програмних систем засобами програмних алгебр композиційного типу на абстрактному та іменному рівнях абстракції:

побудова програмних алгебр, які виступають моделями загальнозначних дескриптивних та декларативних структур програм, моделями маніпуляційних дій у базах даних, зокрема, в реляційних базах даних;

математичні дослідження таких алгебр, орієнтовані на їх подальше застосування до потреб практичного програмування;

застосування отриманих результатів до опису повної семантики підмов маніпулювання даними (DML мов) у SQL-подібних мовах.

Відповідно до цієї мети в роботі ставляться такі задачі:

побудувати та дослідити на абстрактному рівні програмні алгебри суперпозицій та рекурсій, які виступають моделями загальнозначних дескриптивних (суперпозиція) та декларативних (рекурсія) структур програм;

побудувати та дослідити на абстрактному та іменному рівнях абстракції програмні алгебри зберігаючих денотати функцій, які виступають моделями маніпуляційних дій в базах даних; абстрактному рівню відповідають примітивні програмні алгебри, іменному - програмні алгебри іменних функцій;

побудувати та дослідити табличні алгебри, які уточнюють маніпуляції коддовського типу;

побудувати програмну алгебру іменних функцій та застосувати її до визначення повної формальної семантики DML мов у SQL-подібних мовах.

Наукова новизна одержаних результатів. Побудована узагальнююча теорія розв`язування систем рівнянь, асоційованих з рекурсіями, і одержані такі нові результати цієї теорії:

встановлена структура множини всіх розв`язків, залежність розв`язків від початкового наближення, параметрів та функцій правих частин;

отримані нижні та верхні оцінки найменших розв`язків, які узагальнюють оцінки відомих теорем теорії рекурсивних програм - теорем Парка (Park) про індукцію нерухомої точки, Кадью (Cadiou) та Війємана (Vuillemin) про безпечні правила обчислення;

обґрунтована коректність застосування методу Гаусса (послідовного виключення невідомих) до розв`язування систем;

досліджені загальнозначні перетворення систем типу підстановки, які зберігають найменші розв`язки; останній результат є узагальненням важливої теореми Війємана про інваріантні перетворення нерухомої точки в теорії рекурсивних програм.

Побудована і досліджена з нових позицій програмна алгебра суперпозицій та рекурсій:

досліджена монотонність і неперервність суперпозиції за окремими аргументами, монотонність рекурсії та неперервність обмежень рекурсії на класи неперервних функцій;

доведена замкненість класів монотонних (неперервних) функцій відносно рекурсії;

встановлений взаємозв`язок між сигнатурними операціями.

У дисертаційній роботі узагальнена модель маніпуляційних дій Редька-Басараба шляхом введення поняття функцій, які зберігають денотати відносно оцінок-параметрів універсуму даних. Побудовані і досліджені програмні алгебри функцій, які зберігають денотати. Розв`язані проблеми повноти для програмних алгебр обчислюваних функцій, що зберігають денотати для основних оцінок універсуму іменних даних.

На основі узагальнення класичних реляційних алгебр Кодда побудована таблична алгебра, яка уточнює інформаційний та маніпуляційний аспект реляційних баз даних. Повністю вирішена проблема взаємної похідності сигнатурних операцій табличної алгебри. Побудована SQL-орієнтована програмна алгебра іменних функцій, засобами якої адекватно задана повна формальна семантика операторів маніпулювання даними SQL-подібних мов.

Практичне значення одержаних результатів. Дисертація має теоретико-прикладну спрямованість. Результати роботи по теорії програмних алгебр композиційного типу та по її застосуванню для еталонування мовних засобів у реляційних базах даних використовувались при проведенні проектів, пов`язаних з дослідженням універсальних і спеціалізованих програмних логік, програмологічних засобів інформаційних технологій, семантичних структур CASE-середовищ (замовники - КНУ, Фонд фундаментальних досліджень Міністерства освіти і науки України); зі створенням дескриптивних CASE-технологій генерації професійних систем програмування (ДНТП 05.10 “Нові технології програмування та універсальні інструментальні програмні засоби створення комп`ютерних систем”); з програмною реалізацією компонент Єдиної державної комп'ютерної системи “Кадри” (замовник - Головне управління державної служби України). Результати дисертаційного дослідження щодо формальних моделей програм можуть також використовуватись при створенні складних програмних систем, які ґрунтуються на основі СУБД реляційного типу.

Результати роботи щодо формальної семантики SQL-подібних мов були впроваджені у навчальний процес на факультеті кібернетики КНУ (спецкурси для студентів 4-5 курсів за спеціальністю “Інформатика”).

Особистий внесок здобувача. Всі результати, які складають суть дисертаційної роботи, отримані здобувачем самостійно. З праць, виконаних зі співавторами, на захист виносяться лише результати, отримані особисто здобувачем.

Апробація результатів дисертації. Основні результати роботи доповідались у провідних наукових колективах України, Росії, Словаччини: на семінарах КНУ, Інституту кібернетики НАН України, Московського державного університету ім. М.В. Ломоносова, на Всесоюзних конференціях з прикладної логіки (Новосибірськ, 1985 р., 1988 р.), X Всесоюзному семінарі “Параллельное программирование и высокопроизводительные системы: методы представления знаний в информационных технологиях” (Уфа, 1990 р.), на Міжнародних конференціях “Ителлектуальные системы” (Росія, Красновідово, 1991 р., 1993 р.), Всеукраїнських наукових конференціях “Застосування обчислювальної техніки, математичних моделей та математичних методів у наукових дослідженнях” (Львів, 1995 р., 1997 р., 1998 р.), XI та XII Міжнародних конференціях “Проблемы теоретической кибернетики” (Ульянівськ, 1996 р.; Нижній Новгород, 1999 р.), Міжнародній конференції “Питання оптимізації обчислень” (Київ, 1997 р.), Міжнародному симпозіумі “Питання оптимізації обчислень - XXVIII” (Київ, 1999 р.), першій та другій Міжнародних науково-практичних конференціях з програмування УкрПРОГ'98, УкрПРОГ'2000 (Київ, 1998 р., 2000 р.), IV Міжнародній конференції “Electronic Computers and Informatics'2000” (Kosice-Herlany, Slovakia, 2000 р.) та V Міжнародній конференції “Information Theories & Applications” (Varna, Bulgaria, 2000 р.).

Публікації. Результати дисертації опубліковані у одній монографії, 27 статтях у наукових журналах і збірниках наукових праць, 2 тезах конференцій; з них 25 статей опубліковані у фахових виданнях, затверджених ВАК України, серед яких 10 одноосібних праць.

Структура і обсяг роботи. Дисертаційна робота складається з переліку умовних позначень, вступу, п'яти розділів (15 підрозділів), висновків, списку використаних джерел (209 найменувань на 17 с.) і додатків (37 с., доведення технічних тверджень, формальні визначення агрегатних функцій мови SQL). Загальний обсяг дисертації становить 367 с., основний зміст викладено на 295 с. Праця містить 9 рисунків та 6 таблиць загальним обсягом 8 с.

2. ОСНОВНИЙ ЗМІСТ

У вступі обґрунтована актуальність роботи, сформульовано мету, задачі та об`єкт дослідження дисертації. Наведений огляд основних математичних положень роботи в контексті близьких результатів, відомих у літературі.

Перший розділ присвячений нерухомим точкам монотонної функції на довільній частково впорядкований множині (ч. в. м.). Мета розділу полягає у визначенні і дослідженні формальних моделей загальнозначних декларативних структур мов програмування.

Добре відомо, що при природному уточненні понять ефективності, неперервності та монотонності для функцій на частково впорядкованому універсумі даних вони знаходяться у такій логічній підпорядкованості: з ефективності випливає неперервність, а з неперервності - монотонність. Тому щоб дотримати рівень абстракції далі розглядаються саме монотонні функції; як виявляється, для побудови змістовної загальної теорії цього цілком достатньо.

Об`єкт дослідження - формальні моделі декларативних структур, якими виступають рівняння з розв`язною відносно невідомого лівою частиною та монотонною правою частиною: #, де # - монотонна функція на універсумі. Іншими словами, мова йде про метод нерухомої точки у програмології. При дослідженнях використовуються топологічні методи, апарат #-ланцюгів елемента відносно функції Абіана-Брауна (Abian-Brown), техніка Тарського розгляду спеціальних обмежень вихідної функції, оператори замикання та трансфініти.

Основні результати розділу: встановлена топологічна характеристика монотонних функцій, критерій власного включення класу неперервних функцій у клас монотонних функцій в термінах умови обриву зростаючих ланцюгів; описана множина нерухомих точок монотонної функції на довільній ч. в. м., зокрема на індуктивній множині. Наведемо точні означення та формулювання відповідних тверджень.

Означення 1.1. Скажемо, що функція #, де #, # - частково впорядковані множини (ч. в. м.), монотонна, якщо виконується імплікація # для всіх елементів #.?

Означення 1.2. Скажемо, що ч. в. м. індуктивна, якщо її довільний ланцюг має точну верхню грань (супремум).?

Зауважимо, що в індуктивній множині існує найменший елемент, оскільки він дорівнює супремуму порожньої множини #, яка є ланцюгом. Супремум множини # будемо позначати #; найменший елемент - #.

Означення 1.3. Скажемо, що функція #, де # - індуктивні множини, неперервна, якщо для довільного непорожнього ланцюга # виконується рівність #, де # - повний образ множини # відносно функції #.

Таким чином, поняття монотонної, неперервної функції та індуктивної множини використовуються у стандартному розумінні. Сім'ю всіх тотальних (тобто всюди визначених) функцій з множини # у множину # будемо позначати через #, сім'ю всіх монотонних функцій з ч. в. м. # у ч. в. м. # - через #, а сім'ю всіх неперервних функцій з індуктивної множини # в індуктивну множину # - через #. Як зазначалося вище, з неперервності функції випливає її монотонність, наступна ж теорема вирішує питання про власне включення відповідних класів функцій.

Теорема 1.1 (критерій власного включення класу неперервних функцій у клас монотонних). Нехай # - індуктивні множини. Включення # виконується тоді і тільки тоді, коли множина # не задовольняє умові обриву зростаючих ланцюгів, а множина # не є дискретно впорядкованою.

Добре відома топологічна характеристика неперервних функцій за допомогою топології Скотта, дамо аналогічну характеристику монотонних функцій. Для цього розглянемо наступну топологію на ч. в. м.: множина називається відкритою, якщо вона зростаюча. Ця топологія будується просто опущенням другої умови на відкриті множини у топології Скотта. Назвемо цю більш тонку топологію #-топологією Скотта; переходячи до двоїстих понять (спадних множин) отримуємо #-топологію Скотта.

Твердження 1.4 (критерій монотонності у термінах топологій). Розглянемо функцію #, де #, # - ч. в. м. Функція монотонна тоді і тільки тоді, коли вона неперервна в #-топології Скотта (#-топології), введеній на множинах #.

Зафіксуємо ч. в. м. #, функцію вигляду # та елемент #; наступне означення належить Абіану-Брауну.

Означення 1.5. #-Ланцюгом (елемента відносно функції #) назвемо множину # таку, що

# - цілком упорядкована множина (ц. у. м.) за індукованим порядком з найменшим елементом # та деяким найбільшим елементом;

для довільного елемента #, відмінного від найбільшого в #, значення функції # - наступний елемент за # в # (тобто #);

для довільної непорожньої підмножини # існує супремум #, який належить підмножині #.

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

Теорема 1.2 (опис множини нерухомих точок монотонної функції на довільній ч. в. м.). Множина нерухомих точок # монотонної функції # збігається з множиною найбільших елементів #-ланцюгів # для #:

Отже, нерухомі точки співпадають з супремумами #-ланцюгів, які згідно з наслідком 1.4 є ц. у. м.; елементи вигляду # у випадку існування супремумів множин # виступають початковими наближення до нерухомих точок функції. Враховуючи, що в індуктивних множинах існують супремуми довільних ланцюгів, з теореми 1.2 випливає наступна теорема, яка в контексті внутрішньої проблематики методу нерухомої точки визначає особливе місце індуктивних множин в ньому. Щодо прикладного аспекту, то роль індуктивних множин визначається тим, що множина часткових функцій, впорядкованих за включенням графіків, є індуктивною.

Теорема 1.3 (опис множини нерухомих точок монотонної функції на індуктивній множині). Нерухомі точки монотонної функції на індуктивній множині збігаються з найбільшими елементами #-ланцюгів # для #: #. Множина нерухомих точок # є індуктивною множиною за індукованим порядком з найменшим елементом #. Для довільної множини # нерухомих точок виконується рівність # за умови існування супремума у правій частині рівності; зокрема, ця рівність завжди виконується, якщо # - ланцюг нерухомих точок.

Отже, множина нерухомих точок монотонної функції на індуктивній множині успадковує тип вихідної ч. в. м. Цей факт є аналогом відомої теореми Тарського про устрій нерухомих точок монотонної функції на повній решітці.

Структура множини нерухомих точок у попередній теоремі встановлюється шляхом розгляду оператора #; #,# #.

Твердження 1.9. Оператор #, #, є оператором замикання з областю значень #.

З цього твердження, зокрема, випливає, що оператор взяття супремума # монотонно залежить від першого елемента #-ланцюга; в цей супремум початкова монотонна функція входить як параметр, і далі буде встановлена монотонна залежність і від цієї функції (для найменшої нерухомої точки це теореми 3.1 та 3.6). Наступна теорема показує, які додаткові властивості мають нерухомі точки неперервної функції; головне тут, що #-ланцюги переходять у #-сплінтери, а формула для знаходження супремумів нерухомих точок спрощується.

Теорема 1.3ґґ (опис множини нерухомих точок неперервної функції на індуктивній множині). Нерухомі точки неперервної функції на індуктивній множині збігаються з супремумами #-сплінтерів для #: #. Множина нерухомих точок # має супремум # найменшим елементом і замкнена відносно операції взяття супремумів непорожніх ланцюгів, тобто #, де # - довільний непорожній ланцюг нерухомих точок.

Перший розділ у цілому носить допоміжний характер, у третьому розділі його результати використовуються при розгляді рекурсії.

Метод нерухомої точки складає ядро денотаційного програмування. В літературі розглядалися, як правило, неперервні функції на конкретних індуктивних множинах та обмежувалися фактом існування хоча б однієї нерухомої точки, зокрема в дослідженнях з денотаційної семантики, - найменшої. А класичне питання про опис множини всіх нерухомих точок при цьому навіть і не ставиться. Лише результат Тарського говорить про успадкування структури нерухомих точок монотонної функції на повній решітці. Значення цього результату підсилюється природними інтерпретаціями не тільки найменших, а й найбільших нерухомих точок при визначенні денотаційної семантики логічних програм та передумов програм.

Другий розділ присвячений стандартній суперпозиції тотальних функцій, яка виступає моделлю загальнозначних дескриптивних структур програмування. Об`єкт дослідження - суперпозиції тотальних функцій та програмологічні операції над частковими функціями - підстановка, колекція, розгалуження. При дослідженнях використовуються топологічні методи, апарат індуктивних і підіндуктивних множин, який дозволяє природно переносити результати з абстрактного рівня на більш конкретні.

Основні результати розділу: встановлена монотонність і неперервність суперпозиції за окремими аргументами; описана структура часткових функцій, впорядкованих за включенням графіків; встановлена еквівалентність різних означень неперервних операцій над частковими функціями; досліджені зв`язки між частковими та тотальними функціями, суперпозицією та підстановкою, розгалуженням та функцією вибору. Суперпозиція розглядається на максимально абстрактному рівні, необхідному для постановки та дослідження питання про її монотонність і неперервність. Це дає можливість висвітлити принципово різну інтенсіональну роль функцій-аргументів суперпозиції, яка проявляється у властивостях монотонності чи не монотонності суперпозиції за різними аргументами (один є активним - він “викликає” інші аргументи; інші аргументи є пасивними - вони “викликаються”). Аналогічна ситуація і з неперервністю. Разом з тим, розглядаючи суперпозицію тільки над монотонними (неперервними) функціями, розрізнити ці ролі неможливо, бо така суперпозиція є монотонною (неперервною) за всіма аргументами.

Оскільки є дві дуже близькі операції над функціями - суперпозиція тотальних функцій та підстановка часткових функцій, - то встановлюється зв`язок між ними (підрозд. 2.3). Сама методика вкладання часткових функцій у тотальні добре відома у літературі, але питання про адекватність такого моделювання та про взаємозв`язок між суперпозицією та підстановкою раніше навіть не ставилося.

Дамо точні означення та формулювання основних тверджень. Під суперпозицією розуміємо, операцію вигляду #, #, таку, що # для всіх функцій # відповідних сімей та елементів #. При розгляді питань про монотонність і неперервність операцій над тотальними функціями такі функції впорядковуються точково.

Теорема 2.1 (про монотонність суперпозиції). Суперпозиція загального вигляду #, де # - ч. в. м., монотонна за першим аргументом. Суперпозиція вигляду #, де # - ч. в. м., монотонна; зокрема суперпозиція вигляду #, де всі множини # - ч. в. м., також монотонна.

Теорема 2.2 (про неперервність суперпозиції) Суперпозиція загального вигляду #, де множини # індуктивні, неперервна за першим аргументом. Суперпозиція вигляду #, де множини # індуктивні, неперервна; зокрема суперпозиції вигляду #, де множини # індуктивні, а # - ч. в. м., і #, де всі множини # індуктивні, неперервні.

Розглянемо ч. в. м. часткових функцій на універсумі #, які впорядковані за включенням графіків, - #, де #. Тут при записі часткових функцій використовується стрілка #; сам клас часткових функцій позначається як #. Як добре відомо, ця ч. в. м. є індуктивною з найменшим елементом - всюди невизначеною функцією #. Нижче скінченні часткові функції позначаються #. Згідно з теорією арифметичних рекурсивних функцій топологія додатної інформації (т. д. і.) задається своєю базою #, яка складається з порожньої множини та верхніх конусів всіх скінченних функцій. Роль т. д. і. висвітлює наступне твердження.

Твердження 2.5. Для індуктивної множини часткових функцій топологія Скотта збігається з топологією додатної інформації.

Як і в теорії рекурсивних функцій неперервні операції над частковими функціями можна вводити згідно з наступним означенням, в якому для спрощення позначень розглядається унарний випадок

Означення 2.3. Операцію # назвемо неперервною, якщо для всіх функцій # і елементів # виконується еквівалентність

Зв`язок між двома означеннями неперервності встановлюється нижче.

Твердження 2.6. Неперервність операцій над частковими функціями у розумінні означення 2.3 збігається з неперервністю відносно топології Скотта (т. д. і.).

Розглянемо тепер операцію суперпозиції часткових функцій; щоб розрізнити випадки часткових і тотальних функцій, цю операцію будемо називати підстановкою.

Означення 2.4. Під підстановкою розуміємо операцію вигляду #, #, таку, що # для всіх функцій # відповідних сімей та елементів #.

Твердження 2.8. Операція підстановки часткових функцій неперервна.

Заключні пункти 2.3.4 та 2.3.5 присвячені моделюванню часткових функцій тотальними. Тут встановлено, що неперервність підстановки та розгалуження часткових функцій є формальним наслідком неперервності суперпозиції тотальних функцій та монотонності функції вибору. Але безпосередній розгляд питання про неперервність підстановки та розгалуження є більш адекватним, оскільки він не привносить ірелевантності, пов`язані з вкладенням часткових функцій у тотальні.

У третьому розділі вводиться рекурсія та досліджується разом з суперпозицією; таким чином, тут будується програмна алгебра суперпозицій та рекурсій. У першому підрозділі розглядалася унарна рекурсія та встановлювалися її властивості, які були перенесені у другому підрозділі на багатомісну рекурсію. Третій підрозділ присвячений загальній теорії розв`язування рівнянь, асоційованих з рекурсіями.

Унарні та багатомісні рекурсії індуковані рівняннями і системами рівнянь з розв`язними відносно невідомих лівими частинами та монотонними правими частинами вигляду:

Функції та предикати систем алгоритмічних алгебр Глушкова (САА), рекурсивні програми та функції, формальні мови, композиції, типи даних, функціональні програми, взаємодіючі послідовні процеси Хоара природно задаються як розв'язки саме таких систем у конкретних індуктивних множинах; таким чином, зазначені системи виступають потужним декларативним засобом специфікації об'єктів. Саме тому доцільно розвивати загальну теорію розв'язування систем рівнянь зазначеного вигляду, що і робиться у дисертаційному дослідженні.

При дослідженнях використовуються ординальні зображення найменших розв`язків, зображення рекурсії через більш прості операції абстракції та добутку, техніка підіндуктивних множин, встановлені у розд. 2 властивості суперпозиції. Таким чином, у третьому розділі, використовуючи результати перших двох розділів, основні властивості суперпозиції переносяться на рекурсію.

Основні результати третього розділу: встановлена монотонна залежність найменшого розв`язку від функції правої частини та параметру; доведена монотонність рекурсії, неперервність її обмежень на неперервні функції, замкненість класів монотонних та неперервних функцій відносно рекурсії; описаний зв`язок між суперпозицією та рекурсією у вигляді системи співвідношень, коли аргументи операцій побудовані у свою чергу суперпозиціями та рекурсіями; побудована загальна теорія розв`язування рівнянь, асоційованих з рекурсіями (метод Гаусса; розв`язування систем рівнянь з суперпозиціями та рекурсіями у правих частинах; загальнозначні перетворення систем, що зберігають найменші розв`язки; нижні та верхні оцінки найменших розв`язків). У цілому цей розділ носить інтегруючий характер і узагальнює дослідження перших двох розділів.

Перейдемо до точних формулювань. Твердження щодо унарної рекурсії з огляду на їхній проміжний характер не наводяться. Означення багатомісної рекурсії базується на наступній теоремі.

Теорема 3.6 (ординальне зображення найменшого розв'язку системи рівнянь). Система рівнянь (3.9), де множини # індуктивні, а функції # монотонні, має найменший розв'язок #, причому #, ..., #, де трансфінітна послідовність #, #; # - ординал, задається наступним чином #, ..., #; #, де #, ... #, # - найменші елементи відповідних індуктивних множин. Відображення #, що зіставляє монотонним вихідним функціям найменший розв'язок системи (3.9), монотонне.

З цієї теореми випливають відомі зображення найменших розв'язків систем рівнянь вигляду (3.9) у повних решітках формальних мов, у індуктивних множинах часткових функцій та предикатів, упорядкованих за включенням їхніх графіків. Крім того, теорема доповнює відомий результат про неперервну залежність найменшої нерухомої точки від вихідної неперервної функції.

Зафіксуємо множину # і розглянемо систему вигляду (3.9) з параметром

Унарна рекурсія позначається просто як #. Унарні та багатомісні рекурсії, що відповідають декільком параметрам і визначаються аналогічно, позначаються #, #. Далі використовується термальна форма запису найменших нерухомих точок - #. Основні властивості рекурсії розкривають дві наступні теореми.

Теорема 3.9 (про монотонність рекурсії). Багатомісна рекурсія загального вигляду

Теорема 3.10 (про неперервність рекурсії). Операція рекурсії вигляду неперервна. Клас неперервних функцій замкнений відносно рекурсії. Операція рекурсії наступного вигляду також неперервна #.

Для формулювання теореми про застосування методу Гаусса для розв`язування систем (3.9) розглянемо наступні дві системи

Теорема 3.12 (метод Гаусса для монотонних правих частин системи рівнянь). Системи рівнянь (3.9), (3.26), (3.27) мають однакові найменші розв'язки. Для найменшого розв'язку # системи (3.27) виконується: # - найменший розв'язок підсистеми, яку складають перші # рівнянь цієї системи, а #

Зауважимо, що метод Гаусса застосовувався для розв'язування систем рівнянь в САА, зокрема при доведенні принципово важливої теореми про регуляризацію мікропрограм, та у повній решітці формальних мов.

Для ілюстрації методів розв`язування систем рівнянь з суперпозиціями і рекурсіями у правих частинах розглянемо систему вигляду

Для опису найменшого розв'язку системи (3.35) розглянемо наступну систему відносно невідомих # та її підсистему відносно невідомих # і параметрів #:

В наступному твердженні встановлюється зв'язок між найменшими розв'язками останніх трьох систем.

Твердження 3.13. Нехай # - найменший розв'язок системи (3.35), а # - найменший розв'язок системи (3.35'') при значеннях параметрів #. Тоді #,# - найменший розв'язок системи (3.35'). Навпаки, якщо #,# - найменший розв'язок системи (3.35'), то # - найменший розв'язок системи (3.35), а # - найменший розв'язок системи (3.35'') при значеннях параметрів #.

Зауважимо, що останнє твердження уточнює розкриття рекурсивних викликів функцій у теорії рекурсивних схем програм. Виконуються аналоги твердження 3.13 для систем з суперпозицією у правих частинах (п. 3.3.3). З тверджень типу 3.13 випливає, що розв`язування систем рівнянь з суперпозиціями і рекурсіями у правих частинах зводиться до розв`язування систем з початковими функціями у правих частинах, але сплачувати за це приходиться збільшенням кількості рівнянь.

Розглянемо перетворення систем, що зберігають найменші розв`язки. Нехай # - множина формальних рівностей, де # - невідомі (змінні), а # - терми, побудовані з функціональних символів і невідомих #. Запис # означає, що терм # будується з терму # заміною деяких входжень змінних # на терми #. Транзитивне замикання відношення # позначимо через #. Розглянемо систему вигляду

Теорема 3.13 (інваріантні перетворення найменшого розв'язку системи рівнянь). Найменші розв`язки систем (3.46) і (3.47) збігаються. Іншими словами, при многократних замінах невідомих на свої праві частини або на свої найменші розв`язки найменший розв`язок системи не змінюється.

Частковий випадок цієї теореми для # і # відомий у теорії рекурсивних програм як теорема Війемана про інваріантні перетворення нерухомої точки.

Наступне твердження розкриває зв`язок між рекурсією та добутком функцій (тобто бінарною суперпозицією функцій), і є наслідком відповідного твердження теорії розв`язування систем рівнянь.

Твердження 3.20. Для довільної функції #, монотонної за другим аргументом, і довільної монотонної функції # виконується рівність #, де функції # та # мають наступні термальні зображення #, #.

Доведено, що також виконуються аналоги цього твердження, в яких ідеться про редукцію виразів вигляду # (твердження 3.19), # (твердження 3.21) та узагальнень таких виразів для багатомісних суперпозицій та рекурсій. З теореми 3.12 про застосування методу Гаусса випливає наступний наслідок щодо зв`язку між рекурсіями і суперпозиціями.

Наслідок 3.6. Багатомісна рекурсія #, #, #, є похідною відносно унарних рекурсій #, #, суперпозицій та селекторів.

Наступні наслідок і дві теореми стосуються оцінок найменших розв`язків.

Наслідок 3.7 (верхня оцінка найменшого розв'язку системи рівнянь). Нехай # довільні значення, такі, що #, #. Тоді в припущенні монотонності функцій правих частин #, #, має місце така верхня оцінка найменшого розв'язку # системи (3.9): #, #.

Наведена в останньому наслідку верхня оцінка відома у теорії рекурсивних програм як теорема Парка про індукцію нерухомої точки. Дамо нижню оцінку найменшої нерухомої точки монотонної функції # на індуктивній множині для випадку, коли функція зображається деяким термом #, побудованим із символів монотонних функцій на індуктивних множинах і змінної #: #.

Теорема 3.15 (нижня оцінка найменшої нерухомої точки монотонної функції, зображеної термом). Нехай терми #, такі, що #, #, #, де #. Тоді виконуються нерівності:

З теореми 3.15 випливає теорема Кадью теорії рекурсивних програм. Добре відомо, що # у випадку, коли терм # будується зі символів неперервних функцій. Тут, як звичайно, #, #, #. Наведемо верхню оцінку елементів #. Нижче відношення конфінальності використовується у стандартному розумінні: #.

Теорема 3.16. Нехай терми # такі, що #, #, #, де #. У кожному термі # виділимо всі входження змінної, які замінювались при побудові терму # за термом #: #. Тоді виконується нерівність #, де #.

У четвертому розділі розглядаються примітивні програмні алгебри (ППА) та програмні алгебри (ПА) іменних функцій. Носіями ППА виступають класи багатомісних часткових функцій та предикатів, а сигнатури складаються з композицій підстановки, розгалуження і циклувань. Носіями ПА виступають класи іменних функцій та предикатів, а сигнатури містять композиції добутку, розгалуження, циклування і параметричні суперпозиції за значенням. При цьому сигнатурні операції зазначених алгебр являються моделями загальнозначних керуючих структур мов програмування. Зауважимо, що сигнатурні операції програмних алгебр є адекватними уточненнями і тому мають аналоги серед, наприклад, операцій над нормальними алгорифмами Маркова, сигнатурних операції САА, операцій над функторами граф-схем Заславського, операцій структурованих схем програм.

Мета розділу полягає у визначенні формальних моделей маніпуляційних дій у базах даних і вирішенні проблеми синтезу таких дій. Під мініпуляційними розуміються дії, пов`язані насамперед з перебудовою структури аргументів, а не з обчисленням компонент структур даних. Об`єкт дослідження - формальні моделі маніпуляційних дій, якими виступають функції, що зберігають денотати, та відповідні програмні алгебри. Універсум даних розглядається як оцінений - фіксується відображення, яке зіставляє даному множину його компонент. Методика дослідження - формальне уточнення характеристичної властивості маніпуляційності у вигляді вимоги скінченності так званої характеристики функції та встановлення зв`язків між характеристиками функцій при застосування до функцій основних програмологічних операцій. При розв'язуванні проблем повноти різних класів обчислюваних функцій, що зберігають денотати, класична нумераційна обчислюваність моделюється функціями, що зберігають денотати.

Основні результати розділу: уточнена маніпуляційність дії у вигляді функції, що зберігає денотати; введене основне поняття - характеристика функції - та встановлені основні властивості характеристик; розповсюджено поняття збереження денотатів з функцій на композиції та встановлено збереження (чи незбереження) денотатів для основних композицій; визначено взаємне розташування класів функцій, що зберігають денотати, та обчислюваних функцій; сформульовані природні необхідні умови повноти для програмних алгебр у випадку оціненого універсума; знайдені системи породжуючих для ППА обчислюваних векторних функцій, що сильно зберігають денотати, та низки ПА іменних обчислюваних функцій, що зберігають денотати відносно природних оцінок універсуму іменних даних.

Вихідними даними для досліджень розділу є поняття функції маніпулювання даними, введене В. Н. Редьком та І. А. Басарабом, - по суті це збереження денотатів відносно однієї конкретної оцінки. В дисертаційній роботі це поняття параметризується, причому допускаються і нескінченні оцінки. Остання обставина дала змогу поставити і вирішити питання збереження денотатів не тільки для функцій, а і для основних програмологічних операцій.

Перейдемо до точних формулювань. Зафіксуємо універсум #, під функціями (предикатами) будемо розуміти часткові -арні операції (предикати) на #; # Функції позначатимемо #, предикати - #; для випадку, коли не істотно, що мається на увазі - функція чи предикат, - застосовуватимемо позначення #,... Зафіксуємо множину # та відображення вигляду #, яке назвемо оцінкою; універсум назвемо оціненим. Основна інтерпретація оцінки: елементи універсуму будуються з елементів множини #, і # - множина елементів множини #, які використовуються при побудові елементу #. Елементи множини # назвемо праелементами. Природні оцінки з'являються при розгляді структурних об'єктів: векторів, матриць, таблиць, іменних даних. Останні два випадки найбільш цікаві і розглядаються окремо у підрозд. 5.2 та 4.3.

Означення 4.1. Скажемо, що #-арна функція # зберігає #-денотати (або є функцією, що зберігає #-денотати), якщо існує скінченна множина # така, що виконується

Основна інтерпретація збереження денотатів: функція, що зберігає денотати, формує результат, змінюючи структуру своїх аргументів, можливо поповнюючи результат праелементами зі скінченної фіксованої для функції множини. Множину # назвемо #-характеристикою функції #. Значення характеристики розкриває наступне твердження.

Твердження 4.1 (критерій збереження денотатів у термінах характеристик). Функція зберігає денотати тоді і тільки тоді, коли її характеристика скінченна.

Означення 4.2. Скажемо, що функція сильно зберігає #-денотати (є функцією, яка сильно зберігає #-денотати), якщо її #-характеристика є порожньою множиною.

У наступній теоремі, присвяченій основним властивостям характеристик, - композиція розгалуження, а * - композиція циклування.

Теорема 4.1 (властивості характеристики). Виконуються наступні твердження:

характеристика дистрибутивна відносно об'єднань сумісних сімей функцій: #, де всі функції сім'ї # мають однакову арність, а сама сім'я функцій сумісна;

характеристика монотонна відносно теоретико-множинного включення:

якщо оцінка # є неперервною функцією з індуктивної множини # у повну решітку #, то #, де рекурсія має вигляд #, а # - дно індуктивної множини #.

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

Наслідок 4.2. Клас функцій, що зберігають денотати, замкнений відносно підстановки, розгалуження та циклування. Клас функцій, що сильно зберігають денотати, також замкнений відносно цих композицій.

Характеристика зіставляє функціям множини праелементів - #; тому початкова оцінка універсуму індукує оцінку класу функцій на ньому, яку позначимо #, і можна ставити питання про збереження #-денотатів основними програмологічними операціями. Оскільки аргументами цих операцій виступають не тільки функції, а й предикати, то треба домовитись, що розуміти під характеристикою предиката. Покладемо за означенням, що #-характеристика предиката порожня.

Твердження 4.3. Підстановка, розгалуження та циклування сильно зберігають #-денотати.

Оскільки програми індукують ефективні функції, то всюди далі розглядаються сюр`єктивні оцінки універсуму даних вигляду #, де #- множина всіх скінченних підмножин універсуму; причому, множини #, # злічені. Взаємне розташування класів функцій, що зберігають денотати при оцінці #, і класу обчислюваних функцій (чр-функцій) при нумераційному введенні обчислюваності розкриває наступне твердження.

Твердження 4.5. Класи # функцій, які зберігають #-денотати, та обчислюваних функцій # мають непорожній перетин, непорівнювані за включенням і не вичерпують клас всіх функцій #.

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

Означення 4.4. Скажемо, що ППА # #-повна, якщо для її носія # виконується рівність #, тобто об'єднання характеристик всіх функцій носія дорівнює множині праелементів #.

Носії алгебр # містять довільні унарні константні тотальні функції, для характеристик яких згідно з лемою 4.2 виконується рівність #, а оцінка сюр`єктивна, і тому ці алгебри #-повні.

Наслідок 4.4 (необхідна умова повноти #-повних ППА). Якщо # - система породжуючих #-повної ППА, то #. Зокрема, якщо # - скінченна система породжуючих такої ППА, то # містить хоча б одну функцію зі зліченою характеристикою; отже, ППА # не є скінченнопородженими.

У праці вводяться інші природні підсім`ї #-повних ППА (#-породжуючі, #-регулярні) і встановляється їх взаємне розташування. Для ППА функцій, що сильно зберігають денотати, останній наслідок не виконується. У роботі це продемонстровано для ППА векторних обчислювальних функцій, що сильно зберігають денотати для природної оцінки, яка векторам зіставляє множини їхніх компонентів.

Покладемо #, де # - функція виділення першої компоненти, # - функція вилучення першої компоненти, # - функція конкатенації векторів, # - функція відміток (#),# - тотальні предикати перевірки відповідно рівності та нерівності двох векторів.

Теорема 4.3. # - система породжуючих ППА всіх векторних чр-функцій, які сильно зберігають #-денотати, та всіх чр-предикатів. Причому з системи # без втрати властивості повноти не можна вилучити жодного елемента, крім можливо селекторних функцій.

У підрозд. 4.3 розглядається випадок універсума іменних даних #, побудованого на основі довільних фіксованих множин # (множина імен) і # (множина денотатів): #, де #, #, #. Тут # - множина всіх скінченних функціональних відношень на парі множин #. Покладемо #, #. Очевидно, що #. Елементи множини # назвемо іменними множинами, елементи множини # - #-множинами. Іменні дані позначимо через #, іменні множини - #, #-множини - #. Для імен використаємо позначення #, для денотатів - #

Для введення оцінок розглянемо бінарне відношення # на #, яке є рефлексивно-транзитивним замиканням наступного відношення на #:

Змістовна інтерпретація цього відношення: # означає, що елемент # використовується при побудові елемента #. У термінах цього відношення задамо низку оцінок з різними множинами праелементів:

Основна інтерпретація: #, # - відповідно множина денотатів та множина імен, з яких будується іменне дане #; # - множина денотатів чи імен, з яких будується #; # - множина імен, які в процесі побудови іменного даного # використовуються саме як імена, тобто щось іменують в #; # - множина всіх пар ім`я-денотат, які містить іменне дане #.

Під іменними функціями (предикатами) розуміються унарні часткові функції (предикати) на #. Для введення конкретних іменних функцій та предикатів покладемо, що множина імен # має щонайменше два елементи, які позначимо через 1,2. Промоделюємо іменними множинами впорядковані пари та декартові добутки: #; #, де #; #. Розглянемо наступні іменні функції та предикат

Функція # називається омноженням, # - іменуванням, # - розіменуванням; функції # , #, # - аналоги теоретико-множинних операцій. Вище # - відношення сумісності іменних множин: #, де #, а # - обмеження # за множиною #.

Твердження 4.12 (про збереження денотатів основними іменними функціями). Функції # сильно зберігають денотати при оцінках #. Функція іменування # сильно зберігає денотати при оцінках #; іменування зберігає #-денотати (сильно зберігає #-денотати) тоді і тільки тоді, коли # є скінченною множиною (#); іменування не зберігає #-денотати при довільних множинах #.

Перейдемо до розгляду програмних алгебр іменних функцій. Носіями виступають класи іменних функцій і предикатів, а сигнатури # складаються з бінарної підстановки #, розгалуження #, циклування # та суперпозиції за значенням, яка відображає специфіку іменного випадку. Для таких алгебр, як і для ППА, вводиться поняття #-повноти та формулюється природна необхідна умова повноти (твердження 4.13 та його посилення 4.13').

Означення 4.10. Нехай # - кортеж попарно різних імен, #. Під суперпозицією за значенням розуміється #-арна операція # така, що #, де #. .

З твердження 4.14 про #-характеристику суперпозиції за значенням випливають рівності: #, #, #. Таким чином, інтенсіонал іменування проявляється не тільки на рівні функцій (твердження 4.10), а й на рівні композицій.

Далі розглядаються ПА # обчислюваних іменних функцій, що зберігають #-денотати при оцінках #. Для цього проводиться конструктивізація множин імен і денотатів. Перша множина може бути скінченною або ефективно зліченою; у другому випадку фіксується ефективна в інтуїтивному розумінні однозначна проста нумерація множини імен # - #. Ця нумерація індукує функцію наступності на іменах #, #, #; і константну функцію #, яка фіксує ім'я з нульовим #-номером. Оскільки у випадку скінченної множини # функції, що зберігають #-денотати, взагалі не виділяють власний підклас у множині всіх функцій, то множина # покладається ефективно зліченою, що приводить до деякої однозначної простої нумерації #, ефективної в інтуїтивному розумінні. Ця нумерація індукує функцію відміток #, де #, а # є #-номером денотата #. Крім того, далі знадобиться функція вибору (за деяким ефективним критерієм) #, де #, # для всіх непорожніх #-множин #.

ПА # для злічених множин # позначимо #, а для скінченної #-елементної множини імен # та зліченої множини # - #, #. Покладемо

Тут # - константні тотальні функції.

Теорема 4.5. Множини #, # - системи породжуючих ПА #, # відповідно; причому без втрати повноти з систем не можна вилучити жодної константної функції #, #.

Виконуються аналоги цієї теореми для оцінок # (теорема 4.6) та для сильного збереження #-денотатов (теорема 4.7).

Нарешті, заключний п`ятий розділ присвячений застосуванню теорії програмних алгебр в реляційних базах даних. Мета розділу полягає у визначенні формальних моделей маніпуляційних дій у СУБД реляційного типу. Об`єкт дослідження - формальні моделі маніпуляційних дій у таких СУБД, якими виступає таблична алгебра та SQL-орієнтована програмна алгебра іменних функцій. Таблична алгебра будується на основі відомих реляційних алгебр Кодда. Її носій складають таблиці, а сигнатуру - операції об`єднання, перетину, різниці, селекції, проекції, з`єднання, ділення, перейменування та активного доповнення. У табличних алгебрах явно вводяться структури іменування як на рівні даних, так і на рівні сигнатурних операцій; проекція розглядається як тотальна операція, параметром селекції виступає довільний предикат на рядках, з`єднання уточнюється як еквіз`єднання та нетривіально вводиться перейменування атрибутів. Носій SQL-орієнтованої програмної алгебри містить іменні функції на універсальному домені, рядках, таблицях, а сигнатура складається з композицій фільтрації, взяття повного образу, агрегування та підстановки.

Основні результати розділу: побудована таблична алгебра (п. 5.2.1); встановлена непохідність операцій об`єднання (твердження 5.2), селекції (твердження 5.7), проекції (твердження 5.8), з`єднання (твердження 5.3-5.5), перейменування (твердження 5.6), активного доповнення (твердження 5.4) відносно решти сигнатурних операцій та довільних констант; окреслена виразна сила табличної алгебри (твердження 5.10); побудована SQL-орієнтована програмна алгебра (пункти 5.3.1-5.3.7) та застосована для опису повної семантики операторів маніпулювання даними (п. 5.3.8), включаючи таблиці з дублікатами рядків (п. 5.3.3) та без дублікатів (п. 5.2.1), упорядковані таблиці (п. 5.3.4) та таблиці з групуванням (п. 5.3.6), внутрішні та зовнішні операції з`єднання таблиць (п. 5.3.1), агрегатні функції (п. 5.3.5).

Традиційно вважається, що формалізм типу алгебр Кодда (чи еквівалентні їм числення на кортежах або доменах) служить моделлю при визначенні семантики мов у реляційних СУБД. Але в праці показано, що низка суттєвих особливостей реальних СУБД (дублікати рядків, впорядкування та групування рядків, зовнішні з`єднання, агрегатні функції) не моделюється таким формалізмом. Отже виникає проблема побудови відповідних більш потужних моделей, яка і вирішується розглядом SQL-орієнтованої програмної алгебри.

Проблематиці взаємної похідності та виразної сили основних табличних операцій не надавалося достатньої уваги у літературі. Таке становище приводить до того, що вимоги повноти реляційних мов формулюються в змістовних термінах (неформальна прагматична повнота) чи просто в термінах виразності основних коддовських операцій. Власні підалгебри алгебри табличних операцій з операцією підстановки, побудовані у дисертації при дослідженнях з непохідності, дозволяють по-новому підійти до проблем повноти реляційних мов.

Визначимо табличну алгебру. Зафіксуємо множину #, елементи якої назвемо атрибутами, і # - універсальний домен. Скінченну множину атрибутів # назвемо схемою. Рядком схеми # називається іменна множина на парі #, #, проекція якої за першою компонентою рівна #. Таблицею схеми # називається скінченна множина рядків схеми #. Множину всіх рядків (таблиць) схеми # позначимо # (відповідно #), а множину всіх рядків (таблиць) - # (відповідно #). Рядки позначимо #, таблиці - # Носієм табличної алгебри є множина всіх таблиць #, задамо операції.