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

Автор(и)

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

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.