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

 Наукова періодика України 

---

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

• Канарська Ірина Сергіївна (фізико-математичні науки)

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"