RO  EN
IMCS/Publications/CSJM/Issues/CSJM v.25, n.2 (74), 2017/

Nominative data with ordered set of names

Authors: Volodymyr G. Skobelev, Ievgen Ivanov, Mykola Nikitchenko
Keywords: nominative set, nominative data, linear ordering, set-theoretic operations, time complexity of algorithms.

Abstract

In the paper we analyze the set of nominative sets, which can be considered as some mathematical model for data used in com- puting systems, under assumption that the set of names is line- arly ordered. We design algorithms, implemented for execution of basic set-theoretic operations on this set of nominative sets under assumption that nominative sets are presented by doubly linked lists with the order of names in increasing strength. The worst- case time complexity under logarithmic weight for the designed algorithms is investigated in detail. Applications of presented re- sults for table algebras, which are mathematical models, intended for developing and theoretic analysis of relational databases, as well as of associated query languages, are proposed. The obtained results can be used in formal software development.

Volodymyr G. Skobelev
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
40 Glushkova ave., Kyiv, Ukraine, 03187
Phone: +38 063 431 86 05 E-mail:

Ievgen Ivanov
Taras Shevchenko National University of Kyiv
01601, Kyiv, Volodymyrska st, 60
Phone: +38044 2590519
E-mail:

Mykola Nikitchenko
Taras Shevchenko National University of Kyiv
01601, Kyiv, Volodymyrska st, 60
Phone: +38044 2590519 E-mail:



Fulltext

Adobe PDF document – 0.16 Mb