Nominative data with ordered set of names

Abstract

In the paper we analyze the set of nominative sets, which can be considered as some mathematical model for data used in computing systems, under assumption that the set of names is linearly 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 results 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.

Keywords

• nominative set
• nominative data
• linear ordering
• set-theoretic operations
• time complexity of algorithms