Дана робота є продовженням робіт, присвячених актуальній проблемі розробки теоретичної основи табличних баз даних, в якості якої виступають табличні алгебри. Розглядається питання про зв'язок між табличною алгеброю нескінченних таблиць та мультимножинною табличною алгеброю. Враховуючи той факт, що 1-мультимножини є аналогами звичайних множин, виникає питання, чи є таблична алгебра нескінченних таблиць підалгеброю мультимножинної табличної алгебри. Ця проблема і досліджується у даній роботі. Застосовуючи теоретико-множинні та логіко-алгебраїчні методи, встановлено, що таблична алгебра нескінченних таблиць не утворює підалгебру мультимножинної табличної алгебри, бо не є замкненою відносно деяких операцій сигнатури мультимножинної табличної алгебри. У роботі встановлено, що це за операції. Ключові слова. Реляційні бази даних, таблична алгебра нескінченних таблиць, мультимножинна таблична алгебра. Данная работа является продолжением работ, посвященных актуальной проблеме разработки теоретической основы табличных баз данных, в качестве которой выступают табличные алгебры. Рассматривается вопрос о связи между табличной алгеброй бесконечных таблиц и мультимножественной табличной алгеброй. Учитывая тот факт, что 1-мультимножества являются аналогами обычных множеств, возникает вопрос, является ли табличная алгебра бесконечных таблиц подалгеброй мультимножественной табличной алгебры. Эта проблема и исследуется в этой работе. Применяя теоретико-множественные и логико-алгебраические методы, установлено, что табличная алгебра бесконечных таблиц не образует подалгебру мультимножественной табличной алгебры, потому что не является замкнутой относительно некоторых операций сигнатуры мультимножественной табличной алгебры. В работе установлено, что это за операции. Ключевые слова. Реляционные базы данных, табличная алгебра бесконечных таблиц, мультимножественная табличная алгебра. This article is a continuation of the works devoted to the actual problem of the development of the theoretical basis of the table databases. The question of the relationship between table algebra of infinite tables and multiset table algebra is considered. Considering the fact that 1multisets are analogues of ordinary sets, the question arises, is whether table algebra of infinite tables a subalgebra of multiset table algebra. This paper is devoted to this issue. Applying the theorem-plural and logical-algebraic methods found that this is not the case. The table algebra of infinite tables does not form subalgebra of multiset table algebra, since it is not closed in relation to some signature operations of multiset table algebra. These operations are determined.
Таблична алгебра нескінченних таблиць проекція якої за першою компонентою рівна R (тобто по суті розглядається функція вигляду s : R D ). (таблиць) – S (відповідно T ). Таким чином, S
RA S(R) , T(R) t, R | t P(S (R)), T T (R) , де P( X ) –
Під табличною алгеброю нескінченних таблиць розуміємо (часткову параметричну) алгебру T , P, , pP, де T – множина усіх таблиць, P, R , R , \ R , p,R , X ,R , R1,R2 , RR1 , Rt ,R , ~ R
2 X ,R,R1,R2 A P, – множини параметрів. Сигнатура містить аналоги теоретико-множинних операцій (об’єднання, перетин, різницю) та спеціальні операції (селекцію, проекцію, з’єднання, ділення, перейменування та активне доповнення). – сигнатура, Мультимножинна таблична алгебра Дамо означення основних понять мультимножинної табличної алгебри на основі монографії [2]. Як і раніше, A – множина атрибутів, D – універсальний домен. Довільна скінченна множина атрибутів R A – це схема. Рядком схеми R називається іменна множина на парі R , D , проекція якої за першою компонентою рівна R . Множина всіх рядків схеми R позначається S (R) , а множина всіх рядків – S .
Поняття таблиці задається як пара , R , де перша компонента – це довільна мультимножина, зокрема, нескінченна, а друга компонента R – схема таблиці.
Множину всіх таблиць схеми R позначимо (R) , а множину всіх таблиць (R) . RA Позначимо через Occ(s, ) – кількість дублікатів (екземплярів) рядка s у мультимножині . Домовимося мультимножину записувати
як ( ) {s1,..., sk ,} – основа мультимножин . {s1n1 ,...,sknk ,} , де ni Occ(si , ) , i 1,2,, а Під мультимножинною табличною алгеброю розуміємо алгебру , P, , де – множина всіх pP, таблиць, P, Al,lR ,Al,lR , \ Al,lR , p,R , X ,R , R1,R2 , Rt ,R , ~ R X ,R,R1,R2 A – сигнатура, P , – множини параметрів.
Наведемо основні поняття мультимножин в термінах робіт [1, 3]. Зафіксуємо деяку множину U . Під мультимножиною з основою U будемо розуміти відображення вигляду :U N , де N {1,2,...} – множина натуральних чисел.
Нехай D – універсум елементів основ мультимножин, тоді булеан P(D) – універсум основ мультимножин. Під характеристичною функцією мультимножини розуміємо функцію вигляду : D Z , значення якої задається наступною кусковою схемою:
(d ), якщо d dom , (d )
0, інакше; для всіх d D .
Мультимножина називається порожньою і позначається як m , якщо її основа – порожня множина. Мультимножини, областю значень яких є порожня множина або одноелементна множина вигляду {1}, називаються 1-мультимножинами.
У роботі [1] операції над мультимножинами визначено в термінах характеристичних функцій. Автори вводять операції об’єднання 1 , перетину 1 , різниці \1 мультимножин, що будують 1-мультимножини, основи яких отримуються відповідно теоретико-множинними об’єднанням, перетином та різницею основ мультимножин-аргументів, та операції об’єднання All , перетину All , різниці \ All мультимножин, які будують мультимножини загального вигляду. Також задано операцію декартового з’єднання мультимножин , операцію Dist( ) , що будує 1-мультимножину, основа якої збігається з основою вихідної мультимножини та вводиться аналог повного образу для мультимножин.
З’ясуємо чи є таблична алгебра нескінченних таблиць підалгеброю мультимножинної табличної алгебри. Для цього припустимо, що таблицею табличної алгебри нескінченних таблиць є пара t1, R , де t1 – 1-множина – основи 1-мультимножин t11
R t11, R All t12, R t11 All t12, R , де t11, R , t12 , R T (R).
Основа мультимножини t11 All t12 дорівнює об’єднанню основ 1-мультимножин таблиць-аргументів: (t11 All t12 ) (t11) (t12 ) .
Дублікати рядків, які з’явилися після виконання операції, не будуть вилучатися. Кількість дублікатів кожного рядка визначається за формулою:
1, якщо s (t11) \ (t12 ) або s (t12 ) \ (t11), Occ(s,t11 All t12 )
2, якщо s (t11) (t12 ); де s (t11) (t12 ) . В результаті t1 All t2
1 1 мультимножиною.
Отже, множина T не замкнута відносно операції об’єднання RAll .
З’ясуємо, чи замкнена множина T відносно інших операцій сигнатури мультимножинної табличної алгебри P, .
Множина
T є замкненою відносно перетину: RAll : Т (R) Т (R) Т (R) , причому
R t11, R All t12, R t11 All t12, R , де t11 , R , t12 , R T (R).
Основа мультимножини t11 All t12 дорівнює перетину основ 1-мультимножин таблиць-аргментів: буде мультимножиною загального вигляду, а не 1(t11 All t12 ) (t11) (t12 ) , а кількість дублікатів рядка визначається як
Occ(s, t11 All t12 ) minOcc(s, t11),Occ(s,t12 ) 1 , де s (t11) (t12 ) .
Оскільки кожен рядок, що входить як в таблицю t11, R , так і в таблицю t12 , R має кількість входжень рівну одиниці, то мінімальна кількість дублікатів цього рядка в таблиці t1 All t12, R теж буде рівна одиниці. 1 Отже, t11 All t12 є 1-мультимножиною і t1 All t12, R T(R) , тобто в результаті перетину двох таблиць з 1 множини T отримаємо таблицю з цієї ж множини.
R Розглянемо операцію різниці \ RAll . Нехай t11, R , t12 , R T (R) , тоді t11, R \ All t12, R t11 \ All t12, R . Основа мультимножини t11 \ All t12 визначається як Кількість дублікатів знаходиться так:
(t11 \ All t12 ) (t11) \ (t12 ) .
1, якщо s (t11) \ (t12 ), Occ(s,t11 \ All t12 ) 0, якщо s (t12 ) \ (t11) Occ(s,t11) Occ(s,t12 ) , Нехай p : S ~ {true, false} – частковий предикат на множині рядків. З’ясуємо чи замкнена множина Основа мультимножини результуючої таблиці визначається як:
(t) {s | s (t1) p(s) ~ true} , де ~ – узагальнена рівність (тобто обидві частини або одночасно не визначені або одночасно визначені і рівні [4]).
В залежності від значення предиката на рядку s усі дублікати цього рядка або входять до мультимножини отриманої таблиці, або ні:
Occ(s, t) Occ(s,t1) 1, де s (t) . Тому t є 1-мультимножиною і t, R T (R) . Отже, множина T замкнена відносно операції проекції за множиною атрибутів X . Отже, X ,R t1, R t, R X , де t1, R T (R) . селекції.
Нехай X A – скінченна множина атрибутів. З’ясуємо чи замкнена множина T відносно операції Основа мультимножини t визначається як Дублікати рядків, які з’явилися після виконання операції, як і раніше, не вилучаються. Кількість дублікатів кожного рядка визначається за формулою: (t) {s | X | s (t1)}.
Occ(s, t) s(t1), s|X s Occ(s, t1) , де s (t) . Таким чином, t не є 1-мультимножиною. Отже, множина T не замкнена відносно операції проекції.
З’ясуємо чи замкнена множина T відносно операції з’єднання Маємо, t11, R1 R1,R2 t12 , R2 t, R1 R2 , де t11, R1 T (R1), t12 , R2 T (R2 ) . Змістовно кажучи, кожний рядок з t11 .
R1,R2 з’єднується з кожним рядком із t12 .
Основою мультимножини t є множина рядків
( ) s'| s1s2 s1 ( 1) s2 ( 2 ) s1 s2 s' s1 s2 . Кількість дублікатів знаходиться так:
Occ(s', t) Occ(s'| R1, t11) Occ (s'| R2,t12 ) 1, де s' (t) . Таким чином, t є 1-мультимножиною. Отже, множина T замкнена відносно операції з’єднання. Розглянемо операцію перейменування.
Маємо
R ,R t1, R Rs [t1],[R] , t1 T (R) , де id A\domξ , Rs (s) (A), s(A) | A R, Rs [t1] – повний образ 1-мультимножини t1 з основою (t1) відносно функції Rs .
Основою мультимножини Rs [t1] є повний образ множини (t1) відносно функції Rs ,R . А кількість дублікатів рядка у результуючій таблиці задається рівністю Висновки де s Rs1(s) , s (Rs [t1]) .
Оскільки кількість дублікатів при перейменуванні не змінюється з огляду на ін’єктивність функції Rs , то Rs [t1] є 1-мультимножиною. Отже, множина T замкнена відносно операції перейменування.
І наостанок розглянемо операцію активного доповнення ~ R . Маємо ~ R t1, R C t1, R \ RAll t1, R , де насичення визначається за формулою
C t1, R {A1},R t1, R ... {A1},{A2} {A1,...,An1},{An} {An},R t1, R .
Оскільки після застосування операції проекції до 1-мультимножини, ми не обов’язково отримаємо 1мультимножину, то результат різниці мультимножини та 1-мультимножини дасть мультимножину. Отже, множина T не замкнена відносно операції активного доповнення.
Таким чином, множина всіх таблиць табличної алгебри нескінченних таблиць T замкнена відносно операцій перетину, різниці, селекції, з’єднання та перейменування і не замкнена відносно об’єднання, проекції та активного доповнення. Отже, таблична алгебра нескінченних таблиць не утворює підалгебру мультимножинної табличної алгебри.
Дана стаття є продовженням робіт присвячених актуальній проблемі розвитку теоретичної основи табличних баз даних. Основна увага в роботі зосереджена на питанні чи є таблична алгебра нескінченних таблиць підалгеброю мультимножинної табличної алгебри. Застосовуючи теоретико-множинні та логікоалгебраїчні методи встановлено, що це не так. Таблична алгебра нескінченних таблиць не утворює підалгебру мультимножинної табличної алгебри, бо не є замкненою відносно об’єднання, проекції та активного доповнення.
Редько В.Н., Брона Ю.Й., Буй Д.Б., Поляков С.А. Реляційні бази даних: табличні алгебри та SQL-подібні мови. Київ: Видавничий дім "Академперіодика". 2001. 198 с. Буй Д.Б., Глушко І.М. Числення на розширення сигнатур табличних алгебр: монографія. Ніжин: НДУ ім. М. Гоголя, 2016. 151 с. Богатирьова Ю.О. Теорія мультимножин та її застосування: дис. … канд. фіз.-мат. наук. К., 2011. 113с. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М.: Мир, 1983. 256 с.
REDKO, V.N. et al. (2001) Relational Databases: Table Algebras and SQL-like Language. Kyiv: Publishing house Academperiodica. BUY, D.B & GLUSHKO, I.M. (2016) Calculi and extensions of table algebras signature. Nizhyn: NDU im. M. Gogol.
BOGATYREVA, J.A. (2011) Multisets theory and its applications. A Thesis Submitted of the Requirements of the Kyiv National Taras Shevchenko University for the Degree of Doctor of Philosophy. Location: Kyiv National Taras Shevchenko University.
CUTLAND, N. (1983) Computability. An introduction to recursive function theory. Moscow: Myr.