Tuple calculus for multiset table algebra

This paper is a logical continuation of research devoted to the actual problem of developing the theoretical foundations of table (relational) databases. The issue of using multisets in table databases is important and relevant. Many database-oriented languages require a relational model with multis...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2024
Автор:	Lysenko, І.M.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	PROBLEMS IN PROGRAMMING 2024
Теми:	relation databases multiset multiset table algebra tuple calculus UDC 004.65
Онлайн доступ:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/616
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Problems in programming
Завантажити файл:

Репозитарії

Problems in programming

id	pp_isofts_kiev_ua-article-616
record_format	ojs
resource_txt_mv	ppisoftskievua/55/30113c0cb4390db7bf4bd5f51e4f5b55.pdf
spelling	pp_isofts_kiev_ua-article-6162025-02-13T19:16:58Z Tuple calculus for multiset table algebra Числення рядків для мультимножинної табличної алгебри Lysenko, І.M. relation databases; multiset; multiset table algebra; tuple calculus UDC 004.65 реляційні бази даних мультимножина; мультимножинна таблична алгебра; числення рядків УДК 004.65 This paper is a logical continuation of research devoted to the actual problem of developing the theoretical foundations of table (relational) databases. The issue of using multisets in table databases is important and relevant. Many database-oriented languages require a relational model with multiset semantics. There are many applied problems, the feature of which is multiplicity and repeatability of data. For example, these are sociological polls of different population groups, calculations on DNA, and others. In this context, the question of constructing a tuple calculus for a multiset table algebra is considered, in which the concept of a table is refined using the concept of a multiset. In the article, the formalization of tuple calculus for multiset table algebra is carried out. The alphabet, and the syntax of terms, atoms, and formulas are defined. A set of legal formulas is introduced through the concept of the free and bound variable. The concept of a scheme and set of attributes with which a tuple variable occurs in a formula are also introduced. The definition of tuple calculus expression for multiset table algebra is given, according to which it is a multiset of tuples that satisfy the condition defined by the legal formula. The article provides rules for determining the number of tuple duplicates in the resulting multiset. Another important result consists in proving that constructed tuple calculus is as expressive as multiset table algebra. This research opens up new possibilities for database theory development and may be useful for information technology and database professionals. It contributes to a deeper understanding of construction query principles, an important aspect of modern computer science and industry.Prombles in programming 2024; 2-3: 28-36 Дана робота становить логічне продовження досліджень, присвячених актуальній проблемі розробки теоретичних основ реляційних (табличних) баз даних. Питання використання мультимножин у табличних базах даних є важливим і актуальним, зважаючи на те, що багато мов запитів, орієнтованих на роботу з базами даних, потребують реляційну модель, яка передбачає мультимножинну семантику. Це обумовлено наявністю прикладних задач, особливістю яких є множинність і повторюваність даних. Наприклад, це соціологічні опитування різних груп населення, розрахунки на ДНК та ін. У цьому контексті розглядається питання побудови числення рядків для мультимножинної табличної алгебри, в якій поняття таблиці уточнюється, використовуючи поняття мультимножини. У роботі проведено формалізацію числення рядків для мультимножинної табличної алгебри: визначено алфавіт, синтаксис термів, атомів і формул числення рядків; введено множину дозволених формул, використовуючи концепцію вільних і зв'язаних рядків; також вводяться поняття схеми та множини атрибутів, з якими рядок зустрічається у формулах. Дано означення виразу числення рядків для мультимножинної табличної алгебри, згідно з яким – це мультимножина рядків, що задовольняють визначену дозволеною формулою умову. У статті наведено правила, за якими визначається кількість дублікатів рядків у результуючій мультимножині. Інший важливий результат полягає у доведенні того, що побудоване числення рядків є не менш виразним, ніж мультимножинна таблична алгебра. Це дослідження відкриває нові можливості для розвитку теорії баз даних і може бути корисним для спеціалістів у сфері інформаційних технологій та баз даних. Воно сприяє глибшому розумінню принципів побудови запитів, що є важливим аспектом у сучасній комп'ютерній науці та індустрії.Prombles in programming 2024; 2-3: 28-36 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2024-12-17 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/616 10.15407/pp2024.02-03.028 PROBLEMS IN PROGRAMMING; No 2-3 (2024); 28-36 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2024); 28-36 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2024); 28-36 1727-4907 10.15407/pp2024.02-03 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/616/668 Copyright (c) 2024 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-02-13T19:16:58Z
collection	OJS
language	Ukrainian
topic	relation databases multiset multiset table algebra tuple calculus UDC 004.65
spellingShingle	relation databases multiset multiset table algebra tuple calculus UDC 004.65 Lysenko, І.M. Tuple calculus for multiset table algebra
topic_facet	relation databases multiset multiset table algebra tuple calculus UDC 004.65 реляційні бази даних мультимножина мультимножинна таблична алгебра числення рядків УДК 004.65
format	Article
author	Lysenko, І.M.
author_facet	Lysenko, І.M.
author_sort	Lysenko, І.M.
title	Tuple calculus for multiset table algebra
title_short	Tuple calculus for multiset table algebra
title_full	Tuple calculus for multiset table algebra
title_fullStr	Tuple calculus for multiset table algebra
title_full_unstemmed	Tuple calculus for multiset table algebra
title_sort	tuple calculus for multiset table algebra
title_alt	Числення рядків для мультимножинної табличної алгебри
description	This paper is a logical continuation of research devoted to the actual problem of developing the theoretical foundations of table (relational) databases. The issue of using multisets in table databases is important and relevant. Many database-oriented languages require a relational model with multiset semantics. There are many applied problems, the feature of which is multiplicity and repeatability of data. For example, these are sociological polls of different population groups, calculations on DNA, and others. In this context, the question of constructing a tuple calculus for a multiset table algebra is considered, in which the concept of a table is refined using the concept of a multiset. In the article, the formalization of tuple calculus for multiset table algebra is carried out. The alphabet, and the syntax of terms, atoms, and formulas are defined. A set of legal formulas is introduced through the concept of the free and bound variable. The concept of a scheme and set of attributes with which a tuple variable occurs in a formula are also introduced. The definition of tuple calculus expression for multiset table algebra is given, according to which it is a multiset of tuples that satisfy the condition defined by the legal formula. The article provides rules for determining the number of tuple duplicates in the resulting multiset. Another important result consists in proving that constructed tuple calculus is as expressive as multiset table algebra. This research opens up new possibilities for database theory development and may be useful for information technology and database professionals. It contributes to a deeper understanding of construction query principles, an important aspect of modern computer science and industry.Prombles in programming 2024; 2-3: 28-36
publisher	PROBLEMS IN PROGRAMMING
publishDate	2024
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/616
work_keys_str_mv	AT lysenkoím tuplecalculusformultisettablealgebra AT lysenkoím čislennârâdkívdlâmulʹtimnožinnoítabličnoíalgebri
first_indexed	2025-07-17T09:47:18Z
last_indexed	2025-07-17T09:47:18Z
_version_	1850409833235218432
fulltext	Теоретичні і методологічні основи програмування 28 УДК 004.65 http://doi.org/10.15407/pp2024.02-03.028 І.М. Лисенко ЧИСЛЕННЯ РЯДКІВ ДЛЯ МУЛЬТИМНОЖИННОЇ ТАБЛИЧНОЇ АЛГЕБРИ Дана робота становить логічне продовження досліджень, присвячених актуальній проблемі розробки теоретичних основ реляційних (табличних) баз даних. Питання використання мультимножин у таб- личних базах даних є важливим і актуальним, зважаючи на те, що багато мов запитів, орієнтованих на роботу з базами даних, потребують реляційну модель, яка передбачає мультимножинну семанти- ку. Це обумовлено наявністю прикладних задач, особливістю яких є множинність і повторюваність даних. Наприклад, це соціологічні опитування різних груп населення, розрахунки на ДНК та ін. У цьому контексті розглядається питання побудови числення рядків для мультимножинної табличної алгебри, в якій поняття таблиці уточнюється, використовуючи поняття мультимножини. У роботі проведено формалізацію числення рядків для мультимножинної табличної алгебри : визначено алфа- віт, синтаксис термів, атомів і формул числення рядків; введено множину дозволених формул, вико- ристовуючи концепцію вільних і зв'язаних рядків; також вводяться поняття схеми та множини атри- бутів, з якими рядок зустрічається у формулах. Дано означення виразу числення рядків для мультим- ножинної табличної алгебри, згідно з яким – це мультимножина рядків, що задовольняють визначену дозволеною формулою умову. У статті наведено правила, за якими визначається кількість дублікатів рядків у результуючій мультимножині. Інший важливий результат полягає у доведенні того, що по- будоване числення рядків є не менш виразним, ніж мультимножинна таблична алгебра. Це дослі- дження відкриває нові можливості для розвитку теорії баз даних і може бути корисним для спеціалі- стів у сфері інформаційних технологій та баз даних. Воно сприяє глибшому розумінню принципів побудови запитів, що є важливим аспектом у сучасній комп'ютерній науці та індустрії. Ключові слова: реляційні бази даних мультимножина, мультимножинна таблична алгебра, числення рядків. І.M. Lysenko TUPLE CALCULUS FOR MULTISET TABLE ALGEBRA This paper is a logical continuation of research devoted to the actual problem of developing the theoretical foundations of table (relational) databases. The issue of using multisets in table databases is important and rel- evant. Many database-oriented languages require a relational model with multiset semantics. There are many applied problems, the feature of which is multiplicity and repeatability of data. For example, these are socio- logical polls of different population groups, calculations on DNA, and others. In this context, the question of constructing a tuple calculus for a multiset table algebra is considered, in which the concept of a table is re- fined using the concept of a multiset. In the article, the formalization of tuple calculus for multiset table algebra is carried out. The alphabet, and the syntax of terms, atoms, and formulas are defined. A set of legal formulas is introduced through the concept of the free and bound variable. The concept of a scheme and set of attributes with which a tuple variable occurs in a formula are also introduced. The definition of tuple calculus expression for multiset table algebra is given, according to which it is a multiset of tuples that satisfy the condition defined by the legal formula. The article provides rules for determining the number of tuple duplicates in the resulting multiset. Another important result consists in proving that constructed tuple calculus is as expressive as multi- set table algebra. This research opens up new possibilities for database theory development and may be useful for information technology and database professionals. It contributes to a deeper understanding of construction query principles, an important aspect of modern computer science and industry. Key words: relation databases, multiset, multiset table algebra, tuple calculus. Вступ Реляційне числення є основою бі- льшості реляційних мов запитів, оскільки орієнтоване лише на очікуваний результат. Водночас реляційна алгебра передбачає побудову реляційного виразу та виконання операцій. Існує два основних підходи до реляційного числення: © І.М. Лисенко, 2024 ISSN 1727-4907. Проблеми програмування. 2024. №2-3 Теоретичні і методологічні основи програмування 29 1) числення кортежів (E. Кодд) – оперує рядками таблиць [1]; 2) числення доменів (М. Лакруа, А. Піротт) – фокусується на доменах таблиць [2]. У роботі [3] розглядається таблична алгебра нескінченних (скінченних) таб- лиць, яка суттєво узагальнює та розширює класичну реляційну алгебру Кодда. Для даної алгебри побудовано числення на ко- ртежах (доменах) та доведено еквівалент- ність табличної алгебри та даних числень. Методологічну основу вказаних дослі- джень складає композиційний підхід до програмології. Крім того у роботі [3] побудовано мультимножинну табличну алгебру, яка розширює можливості баз даних за раху- нок використання мультимножин. Приро- дно постає питання про розробку числення для даної алгебри. Мета дослідження – побудувати чи- слення рядків для мультимножинної таб- личної алгебри та показати, що воно є не менш виразним, ніж мультимножинна таб- лична алгебра. 1. Мультимножинна таблична алгебра Почнемо з розгляду ключових тер- мінів мультимножин на основі джерел [4, 5]. Нехай U – довільна множина. Під му- льтимножиною  з основою U розуміти- мемо відображення вигляду :U N → , де {1,2,...}N = – множина натуральних чи- сел. Позначимо через D – універсум елементів основ мультимножин. Характе- ристична функція мультимножини  – це функція вигляду : Z → +D , значення якої задаються кусковою схемою: ( ), якщо dom , ( ) 0, інакше; d d d     =   для всіх dD . Порожньою мультимножиною m називається мультимножина, основа якої – це порожня множина. 1-мультимножинами називаються мультимножини, областю значень яких є одноелементна множина вигляду {1}. Основні поняття та твердження му- льтимножинної табличної алгебри розгля- немо, спираючись на монографію [3]. Розглянемо дві множини: A – множина атрибутів та D – універсальний домен. Схемою будемо називати довільну скінченну множину атрибутів R A . Ряд- ком схеми R будемо називати іменну множину на парі R , D , проекція якої за першою компонентою рівна R . Викорис- таємо наступні позначення: ( )S R – мно- жина всіх рядків схеми R , а S – множина всіх рядків. Пара , R , де  – довільна (мож- ливо нескінченна) мультимножина, а R – схема таблиці, називається таблицею му- льтимножинної табличної алгебри. Множина всіх таблиць схеми R по- значається як ( )R , а множина всіх таб- лиць – ( )R R  =   A . Через ( , )Occ s  позначають кіль- кість дублікатів рядка s у мультимножині  . Мультимножину  також записують як 1{ ,..., , }1 nn ks sk , де ( , )n Occ si i = , 1,2,i = , а ( ) { ,..., , }1s sk = – основа мультимножин  . Мультимножинною табличною ал- геброю називають алгебру ,, P   , де  – множина всіх таблиць, 1 2 , , , , , , , , , \ , , , ,R R R P p R X RAll All All R R        =    1 2 , , , , , , ~ p P R R X R R R Rt     A – сигнатура, P ,  – множини параметрів. Має місце наступне твердження. Твердження 1. Будь-який вираз мультимножинної табличної алгебри мож- на замінити еквівалентним йому виразом, який використовує лише операції селекції, з’єднання, проєкції, об’єднання, різниці та перейменування. Теоретичні і методологічні основи програмування 30 2. Побудова числення рядків для мультимножинної табличної алгебри Основою реляційного числення є числення предикатів першого порядку. Побудову числення рядків для мультим- ножинної табличної алгебри почнемо з ви- значення алфавіту. Алфавіт числення ряд- ків для мультимножинної табличної алге- бри складають: •множина атрибутів A (тобто мно- жина імен атрибутів) і універсальний до- мен D ; •множина предметних змінних, тоб- то змінних рядків , ,...1 2x x ; •множина предметних констант , ,...1 2d d ; •множина функціональних символів 1 2, ,...1 2 n n f f , 1ni  ; •множина предикатних символів 1 2, ,...1 2 m m p p , 1mi  ; • множина символів сталих таб- лиць – , R ; • множина символів змінних таб- лиць – RX , ; • знаки логічних операцій  ,  ,  та квантори ,  ; • знаки пунктуації – дужки та кома (,) . Область інтерпретації предметних констант – це універсальний домен D , а область інтерпретації предметних змін- них – це множина всіх рядків на домені D . Надалі в тексті використовуємо на- ступні позначення: x – синтаксична змін- на, областю зміни якої є змінні: f ( p ) – синтаксична змінна, областю зміни якої є функціональні (предикатні) символи; d – синтаксична змінна, областю зміни якої є константи; A – синтаксична змінна, об- ластю зміни якої є атрибути. Серед слів, записаних за допомогою символів алфавіту, виділяють терми та фо- рмули. Сформулюємо означення цих син- таксичних об’єктів індукцією за їхньою довжиною. Дамо означення термів числення рядків для мультимножин: a) d – терм; b) x (A) – терм; c) якщо f – n -арний функціона- льний символ, а ,...,1 nu u – терми, то ( ,..., )1 nf u u – терм; d) ніяких інших термів, крім зазна- чених в пунктах а)-с) немає. Надалі в тексті u – це синтаксична змінна, областю зміни якої є терми. Об- ластю інтерпретації термів є універсаль- ний домен D . Дамо означення формул числення рядків для мультимножин. Почнемо з атомарних формул (атомів), які бувають трьох типів: а1') нехай , R – стала таблиця, a x – змінний рядок, тоді ( )R x – атом, який (за інтерпретації) означає, що рядок , Rx ; а1'') нехай RX , – змінна таблиця, a x – змінний рядок, тоді ( )X R x – атом, який (за інтерпретації) означає, що рядок ,X Rx ; а2) нехай p – m -арний предикат на універсальному домені D , а ,...,1 mu u – те- рми, тоді ( ,..., )1 mp u u – атом. Побудуємо формули із атомів, ви- користовуючи логічні зв’язки  ,  ,  , квантори ,  та дужки (,) . f1.Будь-який атом є формулою. f2.Якщо P і Q – формули, тоді вирази ( )P , ( )P Q , ( )P Q також є формулами. f3.Нехай x – змінний рядок, P – формула, R A – схема, тоді вирази ( )Rx P і ( )Rx P також є формулами. f4.Якщо P – формула, тоді вираз ( )P – також формула. Теоретичні і методологічні основи програмування 31 f5. Інших формул, крім зазначених в пунктах f1-f4 немає. Будемо використовувати P , Q та G як синтаксичні змінні, областю зміни яких є формули. Визначимо клас дозволених формул числення рядків для мультимножинної табличної алгебри, використовуючи по- няття вільних та зв’язаних рядків, схеми ( , )scheme x P змінного рядка x та множи- ни атрибутів ( , )attr x P , з якими рядок x зустрічається у формулах. Вирази ( , )scheme x P та ( , )attr x P визначені, якщо рядок x має хоча б одне вільне входження у формулу P . Крім того має місце включення ( , ) ( , )attr schemex P x P , якщо дані вира- зи визначені. Виділимо клас, так званих, дозво- лених формул числення рядків мультим- ножинної табличної алгебри. Почнемо з термів: 1) якщо =u d , то ( , )attr =x u ; 2) якщо =u x (A), то ( , )attr =x u {A}, а ( , (attr x y A))= , якщо x y ; 3) якщо ( ,..., )1 n=u f u u де iu – те- рми, то ( , ) ( , ) 1 n attr attr ii = = x u x u . Іншими словами, ( , )attr x u – це множина атрибутів, які повинна мати схе- ма рядка x . Нехай P – атомарна формула, тоді а1') якщо ( )R=P x , то єдине вхо- дження змінного рядка x є вільним у фо- рмулі P і ( , ) ( , )scheme attr R= =x P x P ; а1'') аналогічно, якщо ( )X R=P x , то єдине входження змінного рядка x є вільним у формулі P і ( , ) ( , )scheme attr R= =x P x P ; а2) якщо ( ,..., )1 m=P p u u , де iu – терми, ,...,1 kx x – усі змінні цих термів, тоді входження цих змінних рядків є віль- ними у формулі P , при цьому схема ( , )scheme ix P не визначена, а ( , ) ( , ) 1 m attr attri i jj = = x P x u , 1,...,i k= . Атоми завжди дозволені. Побудову дозволених формул числення рядків для мультимножинної табличної алгебри про- ведемо індукцією за довжиною формули. Нехай G і Q дозволені формули. f1. Якщо =P G , то формула P – дозволена, а входження змінних у формулі P будуть вільними або зв’язаними залеж- но від того, вільні або зв’язані входження цих змінних у формулі G . Якщо рядок x входить у формулу G вільно, то мають мі- сце рівності ( , ) ( , )scheme scheme−x P x G і ( , ) ( , )attr attr=x P x G , де − – узагальнена рівність, яка означає, що обидві частини рівності або невизначені, або визначені та мають рівні значення. f2. Якщо = P G Q або = P G Q , то входження змінних у формулі P будуть вільними або зв’язаними, залежно від того, вільні або зв’язані входження цих змінних у підформулах G або Q . Припустимо, що змінний рядок x входить у підформули G та/або Q вільно. Для схеми та множини атрибутів, з якими рядок x зустрічається у формулах маємо три випадки: a. Схеми формул ( , )scheme x G та ( , )scheme x Q визначені. Формула P до- зволена, якщо виконується рівність ( , ) ( , )scheme scheme=x G x Q . Покладемо за означенням ( , ) ( , )scheme scheme=x P x G . b. Схема визначена тільки для однієї з підформул. Припустимо, що схема ( , )scheme x G визначена, а схема ( , )scheme x Q – невизначена. Формула P дозволена, якщо виконується включення ( , ) ( , )attr schemex Q x G . Покладемо за означенням ( , ) ( , )scheme scheme=x P x G . c. Схема невизначена для обох пі- дформул. Формула P є дозволеною, але ( , )scheme x P теж невизначена. Для будь-якого з розглянутих випа- дків а - с ( , ) ( , ) ( , )attr attr attr=x P x G x Q . f3.Якщо ( )R= P x G і змінний ря- док x входить у підформулу G вільно, то Теоретичні і методологічні основи програмування 32 формула P – дозволена. При визначеності схеми ( , )scheme x G та за умови виконання включення ( , )attr Rx G повинна викону- ватися рівність ( , )scheme R=x G . Оскільки змінна x не входить вільно у формулу P , то ( , )scheme x P і ( , )attr x P невизначені. Якщо y x , то будь-яке входження змін- ної y в P вільне або зв’язане, залежно від того, вільне або зв’язане входження y в G . Якщо y входить у P вільно, то ( , ) ( , )scheme scheme−y P y G і ( , ) ( , )attr attr=y P y G . f4.Якщо ( )R=P x G і змінний ря- док x входить у підформулу G вільно, то формула P – дозволена, а всі визначення і обмеження аналогічні випадку f3. f5.Якщо ( )=P G , то формула P – дозволена, а вільні та зв’язані входження змінних, схема і множина атрибутів, з якими змінний рядок зустрічається у фор- мулах, залишаються такими як і для під- формули G . Іншими словами, рівність ( , )attr R=x P , означає, що для конкретної інтерпретації формули P , коли змінна x набуває значення у вигляді рядка s схеми 'R , повинне виконуватися включення 'R R . Дозволеність формули забезпечує її коректну інтерпретацію при розгляді вира- зів числення рядків для мультимножинної табличної алгебри. Вирази числення рядків для муль- тимножинної табличної алгебри мають ви- гляд { ( ) \| ( )}n Rx P x , де 1. формула P – дозволена; 2. змінна x – єдина змінна, яка входить у формулу P вільно; 3. якщо ( , )scheme x P визначена, то ( , )scheme R=x P , інакше, ( , )attr Rx P 4. n – кількість дублікатів рядка x . Варто підкреслити, що результатом виконання запиту, визначеного виразом { ( ) \| ( )}n Rx P x , є мультимножина рядків, які описує вираз ( )P x . Нехай формула ( )P x – дозволена, R A. Підставивши конкретний рядок s схеми R замість x у формулу P отрима- ємо формулу ( / )sP x , значення якої ви- значається шляхом модифікації кожного атома з P за наступними правилами: а1') нехай рядок x підформули ( )'R x вільний у формулі P . За означен- ням дозволеної формули маємо включення 'R R . Атом ( )'R x істинний у разі під- становки конкретного рядка s замість змінної x , якщо \| 's R t , інакше атом ( )'R x хибний а1'') нехай рядок x підформули ( )'X R x вільний у формулі P . Аналогічно випадку а1'), має місце включення 'R R . Атом ( )'X R x істинний у разі підстановки конкретного рядка s замість змінної x , якщо \| 's R X , де ( ( '))X P S R – значен- ня змінної таблиці; а2) нехай рядок x підформули ( ,..., )1 mp u u вільний у формулі P , тоді замінимо ( )Aix на di D , де ,A d si i  ( di значення атрибута Ai в рядку s ) при підстановці конкретного рядка s замість змінної x . Атом ( ,..., )1 mp u u буде істин- ний, якщо предикат p – істинний на відпо- відних значеннях, інакше атом буде хиб- ний. Інтерпретацією формули є множина значень істинності всіх атомів цієї форму- ли. Припустимо, що формула P – дозво- лена без вільних змінних. Визначимо інте- рпретацію формули P для кожного випад- ку. f1. Якщо =P G , то в G не повин- но бути вільних змінних. P істинна фор- мула, коли підформула G хибна, і хибна, коли підформула G істинна. f2. Якщо = P G Q або = P G Q , то в підформулах G та Q не повинно бути вільних змінних. При = P G Q , формула P істинна тоді, коли підформули G та Q одночасно істинні, та хибна у всіх інших випадках. При = P G Q , формула P хи- бна тоді, коли підформули G і Q одноча- Теоретичні і методологічні основи програмування 33 сно хибні, та істинна у всіх інших випад- ках. f3. Якщо ( )R= P x G , то x – єдина змінна, яка входить у підформулу G віль- но. Формула P істинна, якщо знайдеться принаймні один рядок ( )s S R такий, що формула ( / )sG x отримана при підстанов- ці s замість x – істинна, інакше P – хиб- на. f4. Якщо ( )R=P x G , то x – єдина змінна, яка входить у підформулу G віль- но. Формула P істинна, якщо для кожного рядка ( )s S R формула ( / )sG x , отримана в результаті підстановки, буде істинна, ін- акше формула P хибна. f5. Якщо ( )=P G , то формула P іс- тинна, коли підформула G істинна і хиб- на, коли підформула G хибна. Нехай { ( ) \| ( )}nE R= x P x – вираз числення рядків для мультимножинної табличної алгебри. Значенням виразу E назвемо таблицю , R мультимножинної табличної алгебри, яка складається з ряд- ків ( )s S R таких, що формула ( / )sP x істинна, а кількість дублікатів рядка s в таблиці , R визначається так: 1) нехай ( )R=P x , тоді ( , ) ( , )n Occ s Occ s = = ; 2) нехай ( )X R=P x , тоді ( , ) ( , )n Occ s Occ s X= = ; 3) нехай P = ( ,..., )1 mp u u , де ju – терми, 1,j m= , , ,1 kx x – всі змінні цих термів, тоді маємо ( , ) ( ', ), ' ( ), ' \| ' ( , , )1p n Occ s Occ s s s R s u u truem    = =   = = де , R – таблиця до якої будується за- пит, ' ( , ) 1 x u m R attr i jj = = , 1,i k= ; 4) нехай =P G та формула G по- роджує m дублікатів рядка s , тоді ( , ) ( , ( ))n Occ s Occ s C m = = − , де ( )C  – мультимножина таблиці ( ),C R , яка є насиченням таблиці , R , що є значен- ням виразу { ( ) \| ( )}Ry G y , а зрізана різниця ∸ розуміється в звичайному сенсі , якщо 0, якщо x y x y x y x y −  − =   ; 5) нехай = P G Q та формула G породжує k дублікатів рядка s , а формула Q породжує m дублікатів рядка s , тоді ( , )n Occ s = = min( , )k m ; 6) нехай = P G Q та формула G породжує k дублікатів рядка s , а формула Q породжує m дублікатів рядка s , тоді ( , )n Occ s = = k m+ ; 7) нехай ( )R= P x G та формула G породжує k дублікатів рядка s , тоді ( , )n Occ s = = k ; 8) нехай ( )R=P x G та формула G породжує k дублікатів рядка s , тоді ( , )n Occ s = = k ; 9) нехай ( )=P G та формула G породжує k дублікатів рядка s , тоді ( , )n Occ s = = k . Твердження 2. Якщо F – вираз мультимножинної табличної алгебри, то можна ефективно побудувати еквівалент- ний йому вираз E числення рядків для мультимножинної табличної алгебри. Доведення. Згідно Твердження 1 у процесі доведення досить розглянути ви- рази мультимножинної табличної алгебри, які міститимуть тільки операції об’єднання, різниці, селекції, проєкції, з’єднання та перейменування. Доведемо дане твердження методом математичної індукції за числом операцій у виразі F . База індукції. У цьому випадку ви- раз F не містить операцій. Це або стала, або змінна таблиці. Нехай ,F R= – стала таблиця, де  – мультимножина рядків схеми R . Покладемо { ( ) \| ( )}x xR nE R = . Нехай ,F X R= – змінна таблиця, тоді { ( ) \| ( )}x xR nE R X= . □ Крок індукції. Припустимо, що тве- рдження виконується для всіх виразів му- льтимножинної табличної алгебри, які міс- Теоретичні і методологічні основи програмування 34 тять менше i операцій. Розглянемо вираз F , який містить i операцій. Випадок 1 (об’єднання). 1 2 R AllF F F= , де вирази 1F і 2F мають менше i операцій. Тоді існують вирази числення рядків { ( ) \| ( )}x P xn R і { ( ) \| ( )}x Q xm R , які еквівалентні 1F і 2F відповідно. Значеннями цих виразів є таб- лиці, в які рядок x входить n та m разів відповідно. Покладемо E рівним  ( ) \| ( ) ( )x P x Q xk R  , де кількість дублі- катів рядка x у вихідній таблиці дорівнює k n m= + . □ Випадок 2 (різниця). \1 2 R AllF F F= , де вирази 1F і 2F мають менше i опера- цій. Нехай { ( ) \| ( )}1x P xn R і { ( ) \| ( )}x Q xm R – вирази числення рядків, еквівалентні 1F і 2F відповідно. Значен- нями цих виразів є таблиці, в які рядок x входить n та m разів. Покладемо E рів- ним  ( ) \| ( ) ( )x P x Q xk R  , причому кі- лькість дублікатів рядка x у вихідній таб- лиці дорівнює k n m= − . □ Випадок 3 (селекція). ( ), 1F Fp R= , де вираз 1F має менше i операцій. Тоді існує вираз { ( ) \| ( )}x P xn R , еквівалентний 1F . Покладемо  ( ) \| ( ) ( ( ),..., ( ))1x P x p x xkE R A Am=  , де { ,..., }1R A Am= схема таблиці, що є зна- ченням виразу 1F , а кількість дублікатів рядка x у вихідній таблиці не змінюється, тому k n= . Предикат-параметр селекції заданий наступним чином ( ) ( ( ),..., ( ))1pp s T s A s A Tm=  = , ( )s S R , де p – m -арний предикатний символ. □ Випадок 4 (проєкція). ( ), 1F FX R= , де вираз 1F має менше i операцій. Тоді існує вираз числення рядків { ( ) \| ( )}x P xn R , еквівалентний 1F . Значен- ням цього виразу є таблиця, до якої рядок x входить n разів. Покладемо E рівним { ( ) \| ( )( ( ) ( )y x P x yk X R R A A X R    =  ( ))}x A= , де кількість дублікатів рядка y у вихідній таблиці дорівнює ( ) ( )y x A X R A A k n   = =  . □ Випадок 5 (з’єднання). 1 2,1 2 F F F R R =  . Тоді існують вирази чис- лення рядків { ( ) \| ( )}x P xn R і { ( ) \| ( )}x Q xm R , які еквівалентні 1F і 2F відповідно. Значеннями цих виразів є таб- лиці, до якиїх рядок x входить n разів, а рядок y – m разів відповідно. Покладемо вираз E рівним 1 2 1 2{ ( ) \| ( ) ( )( ( ) ( )z x y P x Q yk R R R R    , 1 2 ( ) ( ) ( ) ( ))}z x z y A R A R A A A A     =   = при- чому кількість дублікатів рядка z у вихід- ній таблиці дорівнює k n m=  . □ Випадок 6 (перейменування). ( ), 1F Rt FR= , де : A A → – ін’єктивна функція, що здійснює перейменування ат- рибутів. Нехай { ( ) \| ( )}x P xn R – вираз чи- слення рядків, еквівалентний 1F . Значен- ням цього виразу є таблиця, до якої рядок x входить n разів. Покладемо E рівним 2 \ { ( ) \| ( )( ( ) ( ) ( )y x P x y xk C R dom R R C C     =  ( ) ( ( )))}x y A R dom A A      = , де \ [ ]2R R dom R = , а кількість дубліка- тів рядка y у вихідній таблиці дорівнює n . □ ⁯ 3. Зв’язок з мовою запитів SQL Фундаментальним об'єктом даних у мові SQL є не класичне відношення Е. Кодда, а скоріше таблиця. Причому таблиці SQL містять, власне кажучи, не множини, а мультимножини рядків, тобто Теоретичні і методологічні основи програмування 35 допускаються повторення елементів. Ос- новні оператори SQL не є реляційними операторами у сенсі цього терміну, а є аналогами реляційних операторів, які призначені для роботи з мультимножина- ми. При створенні нової таблиці за допо- могою запиту, система SQL, як правило, не видаляє дублікати рядків, а повертає результат, в якому один і той же рядок може зустрічатися декілька разів. Так, щоб виключити появу дублікатів, за опе- ратором SELECT потрібно поставити ключове слово DISTINCT. Продемонструємо доцільність по- будови числення рядків для мультимно- жинної табличної алгебри на наступному прикладі. Розглянемо таблицю <Scores, R>, де схема R ={№, Name, Topic 1, Topic 2, Top- ic 3, Quiz} (див. Табл. 1). Таблиця 1 Таблиця <Scores, R> № Name To pi c 1 To pi c 2 To pi c 3 Q ui z 1. Баков А. 5 15 14 16 2. Бойко І. 6 14 15 16 3. Борода К. 7 17 20 20 4. Геранов О. 9 20 19 20 5. Кайдан Ю. 5 18 15 18 6. Кузенко Є. 6 19 13 20 7. Кулак П. 4 8 9 16 Відповідь на питання «Які бали отримали за тест (Quiz) перші п’ять студе- нтів?» на мові SQL матиме вигляд: SELECT Quiz FROM Scores LIMIT 5; Таблиця-результат <Quiz, R1>, де схема R 1={Quiz}, міститиме значення- дублікати (див. Табл. 2). Таблиця 2 Таблиця <Quiz, R1> Quiz 16 16 20 20 18 Реалізувати цей запит в термінах класичного числення рядків неможливо, оскільки результатом його виконання буде множина рядків, а не мультимножина (як очікується), тобто дублікати не будуть враховуватися в результат. У численні рядків для мультимно- жинної табличної алгебри вираз еквівален- тний даному запиту матиме вигляд: { nx (Quiz) \| y(R)(Scores(y) (y (№) = 1 y ( №) = 2 y (№) = 3 y (№) = 4 y (№) = 5)  x(Quiz) = y(Quiz))}. Результат, який він описує, аналогі- чний результату отриманому при виконан- ні відповідного запиту на мові SQL. Отже, як видно з прикладу, побудо- ване числення рядків для мультимножин- ної табличної алгебри дозволяє адекватно формалізувати мови запитів, зокрема SQL, врахувавши мультимножинну семантику закладену в їхній основі. Висновки У статті запропоновано числення рядків для мультимножинної табличної ал- гебри. Визначено алфавіт, синтаксис тер- мів, атомів і формул числення рядків. Ви- користовуючи концепцію вільних і зв'яза- них рядків, поняття схеми та множини ат- рибутів, з якими рядок зустрічається у фо- рмулах, введено клас дозволених формул. Показано, що запропоноване числення ря- дків є не менш виразним, ніж мультимно- жинна таблична алгебра. На прикладі про- демонстровано доцільність побудови чис- лення рядків для мультимножинної табли- чної алгебри, враховуючи те, що мови за- Теоретичні і методологічні основи програмування 36 питів орієнтовані на роботу з базами даних передбачають повторюваність елементів у таблиці. Проблематика наступних дослі- джень полягає у встановленні відповідного дуального результату. Література 1. Codd E.F. Relational Сompleteness of Data Base Sublanguages. Data Base Systems. New York: Prentice-Hall, 1972. P. 65-98 2. Lacroix M., Pirotte A. Domain-oriented Relational Languages. Proc. 3rd Int. Conf. on Very Large Data Bases. Tokyo, October, 1977. P. 370-378. 3. Буй Д. Б., Глушко І. М. Числення на розширення сигнатур табличних ал- гебр: монографія. Ніжин: НДУ ім. М. Гоголя, 2016. 151 с. 4. Реляційні бази даних: табличні алгебри та SQL-подібні мови / В. Н. Редько, Ю. Й. Брона, Д. Б. Буй, С. А. Поляков. Київ: Видавничий дім "Академперіо- дика", 2001. 198 с. 5. Богатирьова Ю. О. Теорія мультимно- жин та її застосування: дис. Канд. фіз.- мат. наук: 01.05.03. К., 2011. 113с. References 1. E.F. Codd Relational Сompleteness of Data Base Sublanguages, in: Data Base Systems (1972) 65-98. 2. Lacroix M., Pirotte A. Domain-oriented Relational Languages, in: Proceedings of. 3rd Int. Conf. on Very Large Data Bases., 1977, pp. 370-378. 3. V.N. Redko, et al. Relational Databases: Table Algebras and SQL-like Language. Kyiv: Publishing house Academperiodica, 2001. [in Ukrainian] 4. D.B Buy, I.M. Glushko, Calculi and extensions of table algebras signature. Nizhyn: NDU im. M. Gogol, 2016. [in Ukrainian] 5. J.A. Bogatyreva Multisets theory and its applications. Ph.D. thesis, Kyiv National Taras Shevchenko University, 2011. [in Ukrainian] Одержано: 12.02.2024 Внутрішня рецензія отримана: 19.02.2024 Зовнішня рецензія отримана: 08.03.2024 Про авторів: Лисенко Ірина Миколаївна, к.ф.-м.н., доцент. http://orcid.org/0000-0003-2549-5356. Місце роботи автора: Ніжинський державний університет імені Миколи Гоголя, E-mail: iryna.glushko@ndu.edu.ua Сайт: http://www.ndu.edu.ua/

Tuple calculus for multiset table algebra

Репозитарії

Схожі ресурси