Оцінки складності алгоритмів реалізації теоретико-множинних операцій в табличних алгебрах

Автор(и)

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

DOI:

https://doi.org/10.15407/dopovidi2016.11.017

Ключові слова:

бази даних, складність алгоритму, табличні алгебри

Анотація

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

Завантаження

Посилання

Codd E.F. Communications of the ACM, 1970, 13, No 6: 377–387. doi: https://doi.org/10.1145/362384.362685

Red'ko V.N., Bui D.B. Cybernetics and Systems Analysis, 1996, 32, No 4: 471-478. doi: https://doi.org/10.1007/BF02366768

Knuth D.E. The Art of Computer Programming, Volume 4, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions, Addison-Wesley Professional, 2008.

Jarke M., Koch J. ACM Computing Surveys, 1984, 16, No 2: 111-152. doi: https://doi.org/10.1145/356924.356928

Valduriez P. ACM Transactions on Database Systems, 1987, 12, No 2: 218-246. doi: https://doi.org/10.1145/22952.22955

Kuznetsov S.D. Itogi nauki i tekhniki. Vychislitelnye nauki, 1989, 1: 76-153 (in Russian).

Mendkovich N.A., Kuznetsov S.D. Proc. of the Institute for System Programming, 2012, 23: 195-214 (in Russian). doi: https://doi.org/10.15514/ISPRAS-2012-23-12

Maier D. The Theory of Relational Databases, Comp. Sc. Press, 1983.

Red'ko V.N., Brona J.J., Buy D.B., Polyakov S.V. Relational data base: table algebras and family of the SQL languages, Kiev, Akademperiodyka, 2001 (in Ukrainian).

Cormen T., Leiserson, Ch., Rivest R. Stein C. Introduction to Algorithms. 3rd edition, MIT Press, 2009.

##submission.downloads##

Опубліковано

23.12.2024

Як цитувати

Канарська, І. (2024). Оцінки складності алгоритмів реалізації теоретико-множинних операцій в табличних алгебрах . Доповіді Національної академії наук України, (11), 17–23. https://doi.org/10.15407/dopovidi2016.11.017

Номер

№ 11 (2016): Доповіді Національної академії наук України

Розділ

Інформатика та кібернетика

Ліцензія

Авторське право (c) 2024 Доповіді Національної академії наук України

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial 4.0 International License.