【摘要】 准标识符是影响k-匿名方法有效性的关键因素.在视图发布过程中,求解准标识符所面临的问题是如何在已发布的视图集合中找出与待发布视图相关的全部视图.将已发布的视图集合与待发布的视图映射为一个超图,寻找相关视图集问题可被转化为在超图中求解特定结点间的全部通路问题.首先,给出了视图集向超图的映射方法及有关引理和定理,提出了基于超图的相关视图集求解算法;其次,研究了基本表中属性间不存在函数依赖和存在函数依赖两种情况下准标识符的组成结构,归纳出它们的特征,在此基础上,给出了基于相关视图集的准标识符求解算法.最后,对所提算法进行了正确性证明和时间复杂度分析.更多还原

【Abstract】 Quasi-identifier is a key factor to impact the validity of k-anonymity method.If the quasi-identifier is not identified correctly,the publishing view may still disclose secret information although it has been k-anonymized on the quasi-identifier.In the procedure of publishing views,an important problem concerning identifying quasi-identifiers is how to find all the views relevant to the publishing view from the set of published views.By mapping the set of published views and the publishing view into a hypergraph,the problem of finding the set of relevant views can be converted to searching for all the paths containing special edge between two given nodes in the hypergraph.In this paper,at first,the method mapping all the views to hypergraph and the related lemma and deciding theorems are presented;the algorithm for finding the set of relevant views based on hypergraph is proposed too.Secondly,the composing structures of the quasi-identifiers for the basic table with FDs and without FDs are studied respectively,and the characters of quasi-identifiers are generalized.Then,the algorithms to identify quasi-identifiers of the publishing view based on the set of relevant views for the cases with and without FDs are proposed.At last,the correctness of all the algorithms are proved,and the time complexity of these algorithms are analyzed.The algorithms finding the set of relevant views and quasi-identifiers can ensure the successful application of the k-anonymity method.更多还原