Композиційна семантика ядра SQL-подібних мов

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

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

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

АВТОРЕФЕРАТ

КОМПОЗИЦІЙНА СЕМАНТИКА ЯДРА SQL-ПОДІБНИХ МОВ

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

Поляков Сергій Анатолійович

Київ-2011

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

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

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

старший науковий співробітник

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

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

професор кафедри теорії та технології програмування.

Офіційні опоненти: доктор фізико-математичних наук,

професор

Глибовець Микола Миколайович,

Національний університет "Києво-Могилянська академія" Міністерства освіти і науки, молоді та спорту України, м. Київ,

декан факультету інформатики;

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

Мучнікова Лілія Анатоліївна,

ТОВ "Петер-Сервіс Україна", м. Київ,

інженер-програміст.

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

Актуальність теми дослідження. Для оптимізації бізнес процесів, збирання та аналізу інформації, підтримки процесів прийняття рішень у різних сферах економіки все ширше впроваджуються реляційні бази даних. Зростаючі вимоги до сучасних СУБД ініціюють процес швидкого розвитку мови SQL (Structured Query Language), яка є фактичним стандартом для реляційних баз даних. Одночасно з розширенням функціональності мови SQL росте і її складність, з'являються нові відгалуження, такі, як OLAP системи, сховища даних, дейта майнінг. Але розвиток мови йде, переважно, екстенсіональним шляхом, за рахунок додавання нових синтаксичних конструкцій. Як наслідок, на сьогодні, по кількості синтаксичних конструкцій SQL може конкурувати навіть з С++ мовою, яка відома своєю складністю та розмірами. Мова SQL розвивається досить хаотично, намагаючись задовольнити поточним вимогам і, при збереженні сучасних тенденцій, незабаром досягне такого розміру і складності, що її подальший розвиток дуже ускладниться, або, навідь, стане практично неможливим. Виходом є розробка порівняно компактної семантичної моделі, в яку б відображалися як існуючи синтаксичні конструкції, так і нові. Така модель повинна мати порівняно невелику кількість базових функцій та розвинуті засоби конструювання нових на базі існуючих функцій. Вона дозволить перейти на шлях інтенсіонального розвитку SQL.

Складність мови та наявність численних діалектів, запропонованих різними компаніями, приводить до того, що однакові запити можуть по-різному інтерпретуватися в різних діалектах мови або потребувати переробки синтаксису при переносі в іншу СУБД. Семантична модель дозволить суттєво спростити розробку крос-процесорів нового типу, котрі будуть відображати синтаксичні конструкції вхідного/початкового діалекту мови в функції семантичної моделі, а потім виконувати протилежне перетворення в синтаксичні конструкції вихідного/кінцевого діалекту мови.

В навчальному процесі наявність такої моделі дозволить продемонструвати основні ідеї та властивості мови SQL в явному вигляді, а вже потім навчати конкретним реалізаціям мови.

Реляційна алгебра Кодда, яка претендує на роль семантичного базису SQL, насправді таку роль не може виконувати, хоча б тому, що визначає таблиці даних через множини, а не мультимножини (сукупності з повтореннями), як це має місце в SQL, не підтримує невизначені значення та трьохзначну логіку, не говорячи про те, що структура її операцій не відповідає логічній структурі SQL.

Були розроблені численні модифікації реляційної алгебри, наприклад, П. Греєм, який запропонував реляційну алгебру ASTRID, П. Грефеном, розробившим розширену реляційну алгебру, Р. Елмарси та та С. Навазом, які задали операції для деяких типів оператора SELECT, які не мають відповідних семантичних функцій в реляційній алгебрі і т. ін. З іншого боку М. Негри, Г. Пелагатти та Л. Сбателла запропонували модель розширених трьохзначних обчислень на предикатах, в яку транслюються синтаксичні конструкції мови. Денотаційна семантика мови була описана С. Брауном в його дисертаційній роботі.

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

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

Програмні алгебри, які розвиваються в рамках заснованого В.Н. Редьком, а потім розвинутого в подальших працях Д.Б. Буя, М.С. Нікітченка та ін., композиційного підходу до програмування, задовольняють всім вимогам до нової семантичної моделі мови і тому є підходящим засобом для її побудови. В рамках школи композиційного програмування в 80-х роках була розроблена композиційна СУБД КОМБАД (Композиційні Бази Даних) під керівництвом І.А. Басараба, яка застосовувала композиційний підхід до SQL. Основні теоретичні принципи цієї СУБД були викладені в монографії "Композиційні бази даних", написаної В.Н. Редьком разом з І.А. Басарабом та М.С. Нікітченком. Але семантична модель мови SQL та і не була створена. На початку 2000 років під керівництвом В.Н. Редька така семантична модель була розроблена Д.Б. Буєм, Ю.Й. Броной та співшукачем.

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота є складовою частиною наукових робіт, які ведуться на кафедрі теорії та технології програмування факультету кібернетики Київського національного університету імені Тараса Шевченка при виконанні фундаментальних та прикладних тем: “Розробка конструктивних математичних формалізмів для інтелектуальних систем прийняття рішень, обробки знань, еталонування мов сучасних СУБД та CASE-засобів” (№ 0106U005856, 2006-2010 рр.), “Формальні специфікації програмних систем” (№ 08U002463, 2008-2009 рр.).

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

З огляду на мету в роботі ставляться такі задачі:

- створити нову семантичну модель таблиць, яка більш точно відповідає семантиці таблиць в реальних СУБД;

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

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

- побудувати операційну та денотаційну семантику рекурсивних запитів в SQL;

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

Предметом дослідження є мова SQL.

Об'єктом дослідження є реляційні бази даних.

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

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

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

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

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

Результати роботи були впроваджені у навчальний процес за спеціальністю "Інформатика" на факультеті кібернетики КНУ (нормативні курси "Прикладна логіка", "Композиційна семантика SQL-подібних мов"; спеціальний курс "Вступ до реляційних баз даних"), а також у Кіровоградському державному педагогічному університеті імені Володимира Винниченка (нормативний курс "Табличні алгебри та SQL подібні-мови").

Особистий внесок здобувача. Всі результати, які складають суть дисертаційної роботи, отримані здобувачем самостійно. З праць, виконаних зі співавторами, на захист виносяться лише результати, отримані особисто здобувачем. У спільно виконаних роботах науковому курівнику Д.Б. Бую належить загальна постановка проблеми побудови програмної алгебри семантичних функцій SQL, обговорення та інтерпретація результатів. В монографії дисертантом був написаний розділ 3 "Композиційна семантика мови SQL".

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

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

- The Fifth International Conference "Theoretical and Applied Aspects of Program Systems Development" (TAAPSD'2008), Ukraine, Chernihiv, Kyiv, 22-26 September 2008;

- The Sixth International Conference "Theoretical and Applied Aspects of Program Systems Development" (TAAPSD'2009), Ukraine, Chernihiv, Kyiv, September 2009;

- "Современные направления теоретических и прикладных исследований": международная конференция SWORD, 16-27 марта 2009 г., Одесса;

- VІІ Міжнародній науково-практичній конференції з програмування УкрПРОГ 2010, Київ, Україна, 2010 р.;

- Міжнародній науковій конференції "Computer Science and Engineering" CSE'2010, Кошице, Стара Любовна, Словаччина, 2010 р.

Публікації. Результати дисертації опубліковані у 1 [1] монографії , 9 статтях [2, 3, 4, 5, 6, 7, 8, 9, 10] в наукових журналах і збірниках наукових праць, 5 тезах конференцій [11, 12, 13, 14, 15]; з них 9 статей опубліковані у фахових виданнях, затверджених ВАК України.

Структура та обсяг дисертації. Дисертаційна робота складається з вступу, чотирьох розділів, висновків, списку використаних джерел (105 найменування). Загальний обсяг дисертації становить 120 с., основний зміст викладено на 110 с. Праця містить 13 рис. та 13 табл.

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

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

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

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

В підрозділі 2.1 "Загальна характеристика мови SQL" описуються найбільш важливі підмножини операторів мови. Розглядається структура оператора запитів.

Запити першого типу мають вигляд

SELECT <список вибірки>

FROM <табличний вираз> WHERE <умова>

ORDER BY <список впорядкування>,

причому агрегатні функції в списку вибірки не використовуються.

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

Нарешті, запити третього, найбільш загального, типу використовують групування та агрегатні функції.

В підрозділі 2.2 "Основні операції на таблицях" будується програмна алгебра, орієнтована на моделювання семантичних структур операторів маніпулювання даними SQL-подібних мов.

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

Рядком схеми R називається іменна множина на парі R, D (тобто множина пар (атрибут, значення)), проекція якої за першою компонентою рівна R. Таблицею схеми R називається пара , де - скінченна множина рядків схеми R, яка називається станом таблиці. Відмітимо, що в більшості випадків схема таблиці може бути відновлена по множині рядків. Але для порожньої множини рядків це неможливе. Множину всіх рядків (таблиць) схеми R позначимо S(R) (відповідно T()), а множину всіх рядків (таблиць) - S (відповідно T). Таким чином, ,. Схема може бути порожньою; при цьому існує єдиний рядок порожньої схеми, який позначається . Рядки будемо позначати , таблиці - , стани таблиць - а схеми - .

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

Визначаються операції внутрішнього з'єднання, а саме декартового з'єднанням (cross join, Cartesian join), внутрішнього природного з'єднання (inner natural join), внутрішнього з'єднання за атрибутами та внутрішнього з'єднанням за предикатом (inner join on ).

Наприклад, під декартовим з'єднанням розуміється часткова операція вигляду,

Стан результуючої таблиці визначається формулою.

Схема результуючої таблиці будується шляхом об'єднання схем вихідних таблиць.

Серед операцій зовнішнього з'єднання задаються зовнішнє ліве з'єднання (outer left join), зовнішнє праве з'єднання (outer right join), повне зовнішнє з'єднання (outer full join) та зовнішнє з'єднання об'єднанням (union join). Відзначимо, що в предикатах з'єднання враховується NULL-значення.

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

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

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

Композиція фільтрації Fl предикату вигляду ставить у відповідність функцію, , довільне значення якої задається узагальненою рівністю

, (2.1)

де. У випадку, коли хоча б одне значення вигляду, де, невизначене, то і значення в лівій частині рівності (2.1) покладається невизначеним.

Функція зберігає схему таблиці-аргументу, тобто результуюча таблиця має ту ж саму схему.

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

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

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

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

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

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

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

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

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

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

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

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

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

Підрозділ 2.5 "Впорядковані таблиці" присвячений уточненню таблиць, яке дозволяє задати семантику фрази ORDER BY. Суть уточнення полягає у розгляді таблиць як множин (мультимножин) з бінарним відношенням, яке індукується зазначеною фразою. Отже, таблиці уточнюються як моделі, носіями яких є таблиці в попередньому розумінні, а сигнатури містять єдиний бінарний предикатний символ.

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

Зафіксуємо на універсальному домені порядок . На множині розглянемо наступне бінарне відношення, яке параметризоване за кортежем імен:

Відношення є порядком на сім'ї рядків. Розширимо це відношення на множину рядків. Через позначимо функцію обмеження рядків на відповідну множину атрибутів. Тепер на множині рядків розглянемо наступне бінарне відношення, параметризоване за кортежем імен:.

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

Під у-таблицею ("упорядкованою" таблицею) будемо розуміти пару вигляду, де.

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

В підрозділі 2.6. "Семантика агрегатних функцій" розглядаються функції, характеристична властивість яких полягає в тому, що їхніми аргументами є скінченні множини (мультимножини) або пари, одна з компонент яких є скінченою множиною (мультимножиною), а друга має такий самий тип елемента, що і елементи множини (основи мультимножини), а значеннями - елементи універсального домену або булевські значення. З огляду на зазначену вище характеристичну властивість функцій-семантик агрегатних функцій до них також віднесені функції EXISTS - перевірка множини (таблиці) на непорожність; IN - перевірка належності елемента (рядка) множині (таблиці); ALL - аналог квантору загальності за скінченною множиною (мультимножиною); ANY - аналог квантору існування за скінченною множиною (мультимножиною).

Спочатку задаються формальні означення агрегатних функцій. Наприклад:

Сума елементів множини. Значення задаються кусковою схемою для всіх:

Таким чином, і.

Квантор загальності відносно предиката . Значення задаються рівністю (тут і надалі в тризначній логіці); при цьому використовується звичайна угода відносно порожньої множини -.

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

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

Аналізуючи всі можливі випадки, встановлюються рівності, які зв'язують значення функції на множинах потужності і ,

де і всі елементи попарно різні.

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

Під потужністю скінченної мультимножини будемо розуміти суму дублікатів елементів її основи; за означенням покладемо.

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

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

Далі композиція агрегування задається для випадку мультимножин. Функція вибору розуміється як і раніше. Вона індукує функцію вибору елементу основи мультимножини:.

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

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

В підрозділі 2.7 "Семантика групування даних" задається операція групування. Нехай - множина, яка складається з атрибутів, На сім'ї розглянемо бінарне відношення, параметризоване за множиною атрибутів:.

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

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

Якщо стан уточнюється як мультимножина, основою якої є множина односхемних рядків, то розбиття стану має вигляд, де - основа мультимножини ,- обмеження мультимножини за множиною.

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

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

В підрозділі 2.8 "Оператори оновлення даних" описується семантика операторів оновлення даних мови SQL - INSERT, UPDATE, DELETE. При цьому використовуються тільки раніше введені конструкції.

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

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

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

Якщо на деякому кроці, де , отримується порожня таблиця, причому усі попередні таблиці послідовності не є порожніми, то процес обчислень закінчується з результатом.

В іншому випадку (тобто всі таблиці непорожні) значення покладається невизначеним. Таким чином,

Вище операція - операція об'єднання мультимножин з врахуванням дублікатів. Характеристична властивість цього об'єднання полягає в тому, що коли обидві таблиці-аргументи не є порожніми, то результат відрізняється від аргументів.

Перейдемо до задання денотаційної семантики. Для цього розглянемо наступне рівняння з параметром відносно змінної (область значень - ).

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

Теорема 3.1. Об'єднання в припущенні скінченності є розв'язком рівняння (3.2).

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

1) теоретико-множинні операції та функції об`єднання, перетину та різниці таблиць; функція вилучення дублікатів;

2) параметрична функція побудови упорядкованих таблиць;

3) предикати та функції, потрібні для побудови агрегатних функцій композицією агрегування;

4) параметрична функція групування;

5) операції та функції внутрішнього і зовнішнього з`єднання;

6) операції кон`юнкції, диз`юнкції та заперечення тризначної логіки;

7) операція об`єднання сумісних рядків, параметричні функції іменування та розіменування рядків за атрибутами;

8) вихідні операції та предикати універсального домену (арифметика, рівність, порядок та т.і.).

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

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

Модель даних розуміється як сукупність

- типів атомарних даних та типів колекцій даних;

- типів допустимих зв'язків на колекціях даних;

- множини операцій.

Множина операцій є необов'язковим компонентом і може бути відсутня для деяких моделей даних.

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

Вводиться операція розширеного декартового з'єднання. Для наведених вище мультимножин, розширеним декартовим з'єднанням буде множина вигляду, другий компонент елементів якої враховує, який саме екземпляр входить до елементів з'єднання.

Перелік розглянутих моделей даних і їх характеристики містяться в табл. 1.

ВИСНОВКИ

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

Основні результати включають в себе :

1. Побудована нова семантична модель таблиць, завдяки чому функції та оператори семантичної моделі мають таку ж семантику для випадку порожніх таблиць, як і в SQL. Для нової семантики таблиць визначені і математично обґрунтовані композиції фільтрації, взяття повного образу та функції групування, а також операції внутрішнього та зовнішнього з'єднання;

2. Для агрегатних функцій побудована нова композиція агрегації та множина базових функцій, семантика роботи яких з NULL значеннями, як показало тестування, співпадає з SQL;

3. Вперше надана операційна та денотаційна семантика рекурсивних запитів в SQL;

4. Доведена еквівалентність операційної та денотаційної семантик рекурсивних запитів;

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

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

З результатів роботи випливають наступні висновки.

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

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

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

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

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

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

СПИСОК ПРАЦЬ, ОПУБЛІКОВАНИХ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. В.Н. Редько. Реляційні бази даних: табличні алгебри та SQL-подібні мови / Редько В.Н., Брона Ю.Й., Буй Д.Б., Поляков С.А. - Київ: Видавничий дім "Академперіодика", 2001. - 198 с.

2. Поляков С.А. Алгебра табличних функцій / С.А. Поляков // Вісник Київського університету. Сер.: фіз.-мат. науки. - 1996. - Вип. 2. - С. 150-155.

3. Поляков С.А. Композиційна семантика SQL-подібних мов / С.А. Поляков // Вісник Київського університету. Сер.: фіз.-мат. науки. - 1997. - Вип. 3. - С. 205-211.

4. Поляков С.А. Композиційна семантика SQL-подібних мов: табличні структури даних, композиції, приклади / Д.Б. Буй, С.А. Поляков // Вісник Київського університету. Сер.: фіз.-мат. науки. - 1999. - Вип. 1. - С. 130-140.

5. Поляков С.А. Композиційна семантика SQL-подібних мов: мультимножини, рядки, впорядковані таблиці / Д.Б. Буй, С.А. Поляков // Вісник Київського університету. Сер.: фіз.-мат. науки. - 1999. - Вип. 2. - С. 183-194.

6. Поляков С.А. Композиційні структури SQL-подібних мов: фільтрація та повний образ / Д.Б. Буй, С.А. Поляков // Вісник Львівського університету. Сер.: механіко-математична. - 1998. - Вип. 50. - "Задачі та методи прикладної математики". - С. 24-26.

7. Поляков С.А. Огляд стандартів мови SQL / С.А. Поляков // Вісник Київського університету. Сер.: фіз.-мат. науки. - 2008. - Вип. 1. - С. 132-137.

8. Поляков С.А. Композиційна семантика рекурсивних запитів в SQL-подібних мовах / Д.Б. Буй, С.А. Поляков // Вісник Київського університету. Сер. фіз.-мат. науки. - 2010. - Вип. 1. - С. 45-50.

9. Поляков С.А. Композиційна семантика рекурсивних виразів та їхніх узагальнень в SQL-подібних мовах / С.А. Поляков, Д.Б. Буй // Наукові записки НаУКМА. Сер.: Комп'ютерні науки. - 2010. - Том 112. - С. 21-25.

10. Поляков С.А. Рекурсивні запити в SQL-подібних мовах: приклади, змістовна і формальна семантика / С.А. Поляков, Д.Б. Буй // Проблеми програмування. - 2010. - №2-3 (Спеціальний випуск). - С. 434-439.

11. Поляков С.А. Три замечания о трехзначной логике Клини / Д.Б. Буй, С.А. Поляков, Е.В. Шишацкая // The Fourth International Conference "Theoretical and Applied Aspects of Program Systems Development" (TAAPSD'2007). Abstracts (Ukraine, Berdynsk, 4-9 September 2007). - Київ: Пульсари, 2007. - С. 47-51.

12. Поляков С.А. Типи даних в стандарті SQL: 2003 / С.А. Поляков, Д.Б. Буй // International Conference "Theoretical and Applied Aspects of Program Systems Development (TAAPSD'2008)". Abstracts (Ukraine, Chernihiv, Kyiv, 22-26 September 2008). Volume 2. - Київ: Пульсари, 2008. - С. 53-57.

13. Поляков С.А. Побудова рекурсивних запитів в SQL / С.А. Поляков // International Conference "Theoretical and Applied Aspects of Program Systems Development (TAAPSD'2009)". Abstracts (Ukraine, Chernihiv, Kyiv, September 2009). Volume 2. - Київ: Пульсари, 2009. - С. 204-209.

14. Поляков С.А. Ієрархічні дані в SQL / С.А. Поляков // Современные направления теоретических и прикладных исследований: международная конференция SWORD, 16-27 марта 2009 г., Одесса: Черноморье. - 2009. - Т.2. - С. 52-59.

15. Polyakov S. Recursive queries in SQL and their generalization - systems of recursive queries / S. Polyakov, D. Buy //Proceeding of CSE 2010 International Scientific Conference on Computer Science and Engineering, September 20-22, 2010, Kosice - Stara Lubova, Slovakia, P. 252-257.

АНОТАЦІЯ

Поляков С.А. Композиційна семантика SQL-подібних мов. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.03 - математичне та програмне забезпечення обчислювальних машин і систем. - Київський національний університет імені Тараса Шевченка. - Київ, 2011.

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

Отримані результати застосовані для уточнення семантики мови SQL; у побудові навчальних курсів, які читаються в Київському національному університеті імені Тараса Шевченка, в Ніжинському державному університеті імені М.В. Гоголя та Кіровоградському державному педагогічному університеті імені Володимира Винниченка; при уточнені семантики складних запитів до реляційних баз даних.

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

Поляков С.А. Композиционная семантика SQL-подобных языков. - Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.03 - математическое и программное обеспечение вычислительных машин и систем. - Киевский национальный университет имени Тараса Шевченко. - Киев, 2011.

Работа посвящена актуальной проблеме построения семантической модели (программной алгебры) языка SQL и является продолжением работ, ведущихся с 80-х годов прошлого века в рамках школы композиционного программирования, основаной академиком В.Н. Редько. В отличие от существующих семантических моделей, на роль которых претендует реляционная алгебра Кодда и ее многочисленные модификации, предложенные П. Греем, П. Грефеном, Р. Элмарси, С. Навазом и др., разрабатываемая модель носит открытый характер. Иными словами, она содержит сравнительно небольшое количество базовых функций и развитые средства построения новых функций на основе существующих.

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

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

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

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

Новая семантика таблиц, представленная в работе, решила проблему соответствия семантических функций операциям языка SQL для случая пустых таблиц.

Новый подход к заданию композиция (оператора) агрегации позволил задать семантику агрегатных функций программной алгебры, совпадающую с таковой в SQL для случая множеств/мультимножеств, содержащих неопределенные значения.

Впервые задана семантика рекурсивных запросов в SQL. Построена как операционная семантика рекурсивных запросов на основе специальной композиции (оператора) рекурсии, так и денотационная семантика в виде уравнения, решение которого совпадает с результатом выполнения эквивалентного рекурсивного запроса языка SQL. Доказана эквивалентность обоих подходов.

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

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

Результаты работы позволяют задавать семантику новых синтаксических конструкций в SQL, создавать кросс-процессоры, транслирующие запрос с одного диалекта языка SQL в другой. А именно, синтаксическая конструкция одного диалекта языка транслируется в выражение семантической модели, а затем данное выражение транслируется в синтаксическую конструкцию другого диалекта языка. На основе результатов диссертации читаются курсы лекций в Киевском национальном университете им. Тараса Шевченко и Кировоградском государственном педагогическом университете им. Владимира Винниченко.

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

Polyakov S.A. The compositional semantics of the SQL. - Manuscript.

Thesis for a candidate degree of Physics and Mathematics. Speciality 01.05.03 - Mathematical and software support of computers and systems. - National Taras Shevchenko University of Kyiv. - Kyiv, 2011.

The dissertation is devoted to the specialized program algebra development. The carrier of the program algebra are functions and compositions are used as signature operations. It defines the set of the semantic functions of the SQL language based on the language structure and take into account such SQL features as tables based on bugs, undefined values and three-valued logic.

The received results are used for SQL language semantics elaboration, multisets(bugs) in developing the series of lectures which are given at Taras Shevchenko National University of Kyiv, Negin government university and Kyrovograd government university; for clarifying the complex queries in the relation data bases.

Key words: SQL, relational data bases, composition, multisets, table data bases, semantics of the programming languages, program algebra.

Размещено на Allbest.ru

...