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

1Kanarskaya, IS
1Taras Shevchenko National University of Kyiv
Dopov. Nac. akad. nauk Ukr. 2016, 11:17-23
https://doi.org/10.15407/dopovidi2016.11.017
Section: Information Science and Cybernetics
Language: Russian
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.

Keywords: complexity of algorithms, database, table algebra
References: 
  1. Codd E.F. Communications of the ACM, 1970, 13, No 6: 377–387. doi: https://doi.org/10.1145/362384.362685
  2. Red'ko V.N., Bui D.B. Cybernetics and Systems Analysis, 1996, 32, No 4: 471-478. doi: https://doi.org/10.1007/BF02366768
  3. Knuth D.E. The Art of Computer Programming, Volume 4, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions, Addison-Wesley Professional, 2008.
  4. Jarke M., Koch J. ACM Computing Surveys, 1984, 16, No 2: 111-152. doi: https://doi.org/10.1145/356924.356928
  5. Valduriez P. ACM Transactions on Database Systems, 1987, 12, No 2: 218-246. doi: https://doi.org/10.1145/22952.22955
  6. Kuznetsov S.D. Itogi nauki i tekhniki. Vychislitelnye nauki, 1989, 1: 76-153 (in Russian).
  7. 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
  8. Maier D. The Theory of Relational Databases, Comp. Sc. Press, 1983.
  9. 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).
  10. Cormen T., Leiserson, Ch., Rivest R. Stein C. Introduction to Algorithms. 3rd edition, MIT Press, 2009.