Độ phức tạp của các thuật toán chuẩn hóa phụ thuộc Boole dương

Abstract

In relational databases, data dependencies represent the integrity constraints between the sets of attributes. The data dependencies play an important role to keep data in a database be reflected the reality. In various kinds of data dependencies, the class of positive Boolean dependencies is more general, including functional dependencies, multi-valued dependencies, generalized positive Boolean dependencies, differential dependencies, generalized differential dependencies, etc.

In this paper, we present some new results related to the class of positive Boolean dependencies in databases. There are the membership problem and the non-redundant conjunctive normal form. The main results in the paper are representing and computing complexity of algorithms for membership problem and for converting a given set of positive Boolean dependencies to a non-redundant set of conjunctive normal forms. It is shown that the membership problem for a set of positive Boolean dependencies are NP- Complete.