Оцінки часової складності для додавання, видалення та порівняння при реалізації алгоритмів теоретико-множинних операцій у табличних алгебрах
Рік:
2016
Сторінок:
С. 55-60
Тип документу:
Стаття
Головний документ:
Київський Вісник Київського національного університету імені Тараса Шевченка / Київський, університет імені національний; редкол.: голов. ред. Анісімов А.В. ; Хусаінов Д.Я., Arturs Medvids, Miklos Ronto [та ін.]. - Київ, 2016
Анотація:
В роботі досліджуються алгоритми, що реалізують перетин, об"єднання і різницю в табличних алгебрах. Запропоновано модифікації найбільш поширених алгоритмів, що дозволяють скоротити кількість обчислень. Було знайдено оцінки у найгіршому випадку та у середньому для кожного з основних перетворень таблиць при реалізації кожного з запропонованих алгоритмів. Розроблено програмну систему, що експериментально підтверджує теоретичні оцінки.
In this paper we investigate algorithms implementing intersection, union, and difference in table algebra which are modern analogue of Codd"s well-known relational algebra and form the theoretical foundation of modern query language databases. Elements of the carrier of table algebra specify relational data structures, andsignature operations are based on the basic table manipulations in relational algebra and SQL-like languages. Modifications of the most widespread algorithms which reduce the amount of computations are proposed. In these algorithms there are three basicconversions of tables: adding, deleting and comparing data. Because in real databases the performance of these conversions is different, for more accurate calculation of the execution time of the set-theoretic operations it is desable to find complex&ity characteristics for each conversion separately. Based on the complexities evaluated for the each conversion of each modified algorithms, the fastest algorithm was found for each operation. A program that experimentally confirms theoretical estima&tes was developed.
