Open AccessOn the nonkeys
Author(s) -
Vũ Đức Thi
Publication year - 2016
Publication title -
journal of computer science and cybernetics (vietnam academy of science and technology)/journal of computer science and cybernetics
Language(s) - English
Resource type - Journals
eISSN - 2815-5939
pISSN - 1813-9663
DOI - 10.15625/1813-9663/13/1/7979
Subject(s) - cardinality (data modeling) , relation (database) , integer (computer science) , scheme (mathematics) , mathematics , polynomial , time complexity , integer programming , combinatorics , discrete mathematics , algorithm , computer science , mathematical optimization , mathematical analysis , database , data mining , programming language
In this paper we give some results about nonkeys. We show that for relation scheme the problem decide whether there is a nonkey having cardinality greater than or equal to a give integer m is NP-complete. However, for relation this problem can be solved by a polynomial time algorithm.