Estimates of the complexity of algorithms of implementation of set-theoretic operations in table algebras

Authors

  • I.S. Kanarskaya Taras Shevchenko National University of Kiev

DOI:

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

Keywords:

complexity of algorithms, database, table algebra

Abstract

The algorithms of implementation of the intersection, union, and difference of tables in the table algebras are investigated. A modification of the most common algorithms reducing the amount of computation is proposed. Based on the evaluated complexities in the worst case and on the average for the modified algorithms, the fastest algorithms for each operation are found. The experiments, which confirm the theoretical estimates, are executed.

Downloads

Download data is not yet available.

References

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.

Downloads

Published

23.12.2024

How to Cite

Kanarskaya, I. (2024). Estimates of the complexity of algorithms of implementation of set-theoretic operations in table algebras . Reports of the National Academy of Sciences of Ukraine, (11), 17–23. https://doi.org/10.15407/dopovidi2016.11.017

Issue

No. 11 (2016): Reports of the National Academy of Sciences of Ukraine

Section

Information Science and Cybernetics

License

Copyright (c) 2024 Reports of the National Academy of Sciences of Ukraine

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.