热爱互联网

分解成3NF模式集

好吧,这个哥最后一个想实现的数据库算法了,写的过程中可以用前面写过的算法来验证各种数据。。。
比如: 这个将关系模式 R 无损分解且保持依赖地分解成 3NF 模式集 的算法,那么就可以用这个结果去测试
无损分解的测试 , 判断是第几范式 以及 判断是否保持函数依赖 的代码 ….. 各代码相互测试了比较多的数据。。。
其实这些算法中 有很多相同的代码,调用了很多共同的函数,原本是想以类的形式囊括所有的算法的,,,,,不想写了。
就这样了,哥做数据库课设去,嚯嚯。

将关系模式 R 无损分解 且 保持依赖地 分解成 3NF 模式集。
代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
/*
    将关系模式 R 无损分解成  且  保持依赖地分解成 3NF 模式集
    (方法见课本)
*/
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
 
string R; //关系模式
vector< pair<string,string> > F; // 函数依赖集(FD)
vector<string>subset; //关系模式 R 的所有子集
char *temp; //求所有子集的辅助变量
vector<string>candidate_key; // 所有的候选键
vector<string>super_key; //所有的超键
 
/*********************************************************************/
bool _includes(string s1,string s2){ //判断 s2 的每个元素是否都存在于 s1
	 sort(s1.begin(),s1.end());
	 sort(s2.begin(),s2.end());
	 return includes(s1.begin(),s1.end(),s2.begin(),s2.end()); // includes函数是基于有序集合的,所以先排序
}
bool _equal(string s1,string s2){ //判断两个集合是否相同
     sort(s1.begin(),s1.end());
     sort(s2.begin(),s2.end());
     s1.erase( unique(s1.begin(),s1.end()),s1.end()); //排序去重之后判断是否相等即可
     s2.erase( unique(s2.begin(),s2.end()),s2.end());
     return s1==s2;
}
string get_attribute_closure(const string &X, const vector< pair<string,string> > &F){ //返回属性集X的闭包
	   string ans(X); //初始化 ans
	   string temp;
	   bool *vis = new bool[F.size()];
	   fill(vis,vis+F.size(),0);
	   do{
			temp=ans;
			for(int i=0;i!=F.size();++i){
				if(!vis[i] && _includes(ans,F[i].first) ){
					 vis[i]=1;
					 ans += F[i].second;
				}
			}
	   }while(temp!=ans); // ans 无任何改变时终止循环
 
	   delete []vis;
	   vis=NULL;
	   //删掉重复的
	   sort(ans.begin(),ans.end());
	   ans.erase( unique(ans.begin(),ans.end()),ans.end() );
	   return ans;
}
void _all_subset(int pos,int cnt,int num){ // get_all_subset()的辅助函数
     if(num<=0){
         temp[cnt]='';
         subset.push_back(temp);
         return ;
     }
     temp[cnt]=R[pos];
     _all_subset(pos+1,cnt+1,num-1);
     _all_subset(pos+1,cnt,num-1);
}
void get_all_subset(const string &R){ //求关系模式R的所有子集,保存在subset中
     subset.clear();
     temp=NULL;
     temp=new char[R.size()];
     _all_subset(0,0,R.length());
     delete []temp;
     temp=NULL;
}
bool is_candidate_key(const string &s){ //判断 s 是否是候选键
     for(int i=0;i!=candidate_key.size();++i)
         if(_includes(s,candidate_key[i])) //如果s包含了已知的候选键,那么s就不是候选键
             return false;
     return true;
}
 
bool cmp_length(const string &s1,const string &s2){ //对 subset 以字符串长度排序
     return s1.length()<s2.length();
}
void get_candidate_key(const string &R, const vector< pair<string,string> > &F){//求关系模式 R基于F的所有候选键
     get_all_subset(R);
     sort(subset.begin(),subset.end(),cmp_length);
     candidate_key.clear();
     super_key.clear();
     for(int i=0;i!=subset.size();++i){
         if( _includes( get_attribute_closure(subset[i],F), R) ){
             super_key.push_back(subset[i]);
             if(is_candidate_key(subset[i]))
                 candidate_key.push_back(subset[i]);
         }
     }
}
 
typedef vector<pair<string,string> > vpss;
vpss get_minimum_rely(const vpss &F){ //返回 F 的依赖集
     vpss G(F);
     //使 G 中每个 FD 的右边均为单属性
     for(int i=0;i!=G.size();++i){
         if(G[i].second.length()>1){
             string f=G[i].first, s=G[i].second,temp;
             G[i].second=s[0];
             for(int j=1;j<s.length();++j){
                 temp=s[j];
                 G.push_back( make_pair(f,temp) );
             }
         }
     }
 
     int MAXN=0;
     for(int i=0;i!=G.size();++i)
         if(G[i].first.length()>MAXN)
             MAXN=G[i].first.length();
     bool *del=new bool[MAXN];
 
     //在 G 的每个 FD 中消除左边冗余的属性
     for(int i=0;i!=G.size();++i){
         if(G[i].first.length()>1){
             fill(del,del+G[i].first.length(),0);
             for(int j=0;j!=G[i].first.length();++j){ //对于第i个FD,判断是否可消除first的第j个属性
                 string temp;
                 del[j]=1;
                 for(int k=0;k!=G[i].first.length();++k)
                     if(!del[k])
                         temp+=G[i].first[k];
                 if( ! _includes(get_attribute_closure(temp,G),G[i].second) ) //不可删除
                     del[j]=0;
             }
             string temp;
             for(int j=0;j!=G[i].first.length();++j)
                 if(!del[j])
                    temp+=G[i].first[j];
             G[i].first=temp;
         }
     }
     delete []del;
     del=NULL;
 
     //必须先去重
     sort(G.begin(),G.end());
     G.erase( unique(G.begin(),G.end()),G.end());
 
     //在 G 中消除冗余的 FD
     vpss ans;
     for(int i=0;i!=G.size();++i){ //判断第i个 FD 是否冗余
         vpss temp(G);
         temp.erase(temp.begin()+i);
         if( ! _includes(get_attribute_closure(G[i].first,temp),G[i].second) ) //第 i 个 FD 不是冗余
             ans.push_back(G[i]);
     }
     return ans;
}
string _difference(string a,string b){ //先去重,再返回 a 和 b 的差集,即 a-b
       string c;
       c.resize(a.size());
       sort(a.begin(),a.end());
       a.erase( unique(a.begin(),a.end()),a.end());
       sort(b.begin(),b.end());
       string::iterator It=set_difference(a.begin(),a.end(),b.begin(),b.end(),c.begin());
       c.erase(It,c.end());
       return c;
}
/***************将关系模式 R  无损分解且保持依赖地的分解成 3NF 模式集 *****************/
vector<string> split_to_3nf(const string &R, const vector< pair<string,string> > &F){
     vector< pair<string,string> > FF = get_minimum_rely(F); //保存 F的最小依赖集到 FF
     // 把左部相同的 FD 用合并性合并起来
     map<string,string> mp;
     for(int i=0;i!=FF.size();++i){
         if(mp.find(FF[i].first) == mp.end() )
             mp[ FF[i].first ] = FF[i].second;
         else
             mp[ FF[i].first ] += FF[i].second;
     }
 
     FF.resize(mp.size());
     int id=0;
     map<string,string>::iterator It;
     for(It=mp.begin(); It != mp.end(); ++It){
         FF[id].first=It->first;
         FF[id++].second=It->second;
     }
     // 每个 FD x->y 去构成一个模式 xy
     vector<string> P;
     for(int i=0;i!=FF.size();++i)
         P.push_back(FF[i].first+FF[i].second);
 
     get_candidate_key(R,F); //得到 R 的候选键
     //在构成的模式集中,如果每个模式都不包含 R 的候选键,那么把候选键作为一个模式放入到模式集中
     //这样得到的模式集是关系模式 R 的一个分解,并且这个分解既是无损分解,有能保持 FD .
     for(int i=0;i!=candidate_key.size();++i){
         int flag=0;
         for(int j=0;j!=P.size();++j){
             if( _includes(P[j],candidate_key[i]) ){
                 flag=1;
                 break;
             }
         }
         if(!flag)
             P.push_back(candidate_key[i]);
     }
     sort(P.begin(),P.end());
     P.erase( unique(P.begin(),P.end()),P.end());
     return P;
}
 
/********************************************************************/
 
void init(){ //初始化
	 R="";
	 F.clear();
}
void inputR(){   //输入关系模式 R
	 cout<<"请输入关系模式 R:"<<endl;
	 cin>>R;
}
void inputF(){  //输入函数依赖集 F
	 int n;
	 string temp;
	 cout<<"请输入函数依赖的数目:"<<endl;
	 cin>>n;
	 cout<<"请输入"<<n<<"个函数依赖:(输入形式为 a->b ab->c) "<<endl;
	 for(int i=0;i<n;++i){
		 pair<string,string>ps;
		 cin>>temp;
		 int j;
		 for(j=0;j!=temp.length();++j){ //读入 ps.first
			 if(temp[j]!='-'){
				 if(temp[j]=='>')
					break;
				 ps.first+=temp[j];
			 }
		 }
		 ps.second.assign(temp,j+1,string::npos); //读入 ps.second
		 F.push_back(ps); //读入ps
	 }
}
/**************************************************************************/
int main(){
	while(1){
 
		 init();
		 inputR();
		 inputF();
 
		 vector<string> ans=split_to_3nf(R,F);
		 cout<<"将关系模式 R 无损分解且保持依赖地分解成 3NF 模式集,如下:"<<endl;
		 for(int i=0;i!=ans.size();++i)
		     cout<<ans[i]<<endl;
 
	}
 
	return 0;
}
 
/* 可用另几个代码测试 下面的分解是否满足 无损分解且保持函数依赖的 3NF 模式集
test:
    input sample
 
    abcde
    2
    a->b
    c->d
 
    abc
    2
    a->b
    bc->a
 
    abcdef
    4
    ab->ef
    d->e
    e->f
    cd->ef
 
    abcdef
    2
    ab->cd
    bc->ef
 
    abcdef
    4
    ab->ef
    c->d
    d->e
    bc->de
 
    output sample
 
    ab
    ace
    cd
 
    ab
    abc
 
    abcd
    abe
    de
    ef
 
    abcd
    bcef
 
    abc
    abef
    cd
    de
 
*/

8 Comments

  • Posted 25/04/2019 at 13:41 | Permalink

    – Hair Color: Color with the linbgerie is likely to be why is contrast together with your hair.
    These days, you are able tto select from lots of
    different types of sexy lingerie to help you think that
    a goddess. You decide tto take out your tenderneszs and affections to demonstrate your gratitude
    for the sweet days he’d given you iin the past years.

  • Posted 04/07/2019 at 07:45 | Permalink

    I blog frequently and I really thank you for your information. This article has truly peaked my interest.
    I will take a note of your blog and keep checking for new details about once a week.
    I subscribed to your Feed too.

  • Posted 09/07/2019 at 04:49 | Permalink

    Having read this I believed it was really enlightening. I appreciate you finding
    the time and effort to put this content together. I once again find myself personally spending way
    too much time both reading and leaving comments. But so what,
    it was still worth it!

  • Posted 10/07/2019 at 08:20 | Permalink

    Hello there! I coᥙld have sworn I’ve ƅeen too this site befοre but aftеr reading through sօme оf tthe post Ӏ realized іt’s nnew tο me.

    Аnyways, I’m Ԁefinitely glad I found it andd I’ll be book-marking and checking Ьack often!

  • Posted 11/07/2019 at 06:57 | Permalink

    Many people take advantage of such programs, in particular
    when flower purchases are manufactured often. In some cases, with well constructed websites, you’ll be able
    to often include additional items like balloons,
    champagne, chocolates, teddy bears or a quantity of add-on gifts.

    There are many ideas and methods you possibly can male these moments
    andd eevents special.

  • Posted 13/07/2019 at 16:47 | Permalink

    When someone writes an piece of writing he/she keeps the
    idea of a user in his/her mind that how a user can know
    it. Therefore that’s why this article is great. Thanks!

  • Posted 14/07/2019 at 02:39 | Permalink

    Many ppeople benefit frdom such programs, particularly if flower purchases are produced often.
    There are no particular flowers which iis often used limited to presenting oon birthdays.
    You can ask extra questions if you wish to or request customisations tto bouquets where available.

  • Posted 15/07/2019 at 15:33 | Permalink

    As this is definitely an occasion when the individual will go
    vvia a great deal of pain, suffering, panic and anxiety, something as simple as getting flowers can help a good
    deal in cheering up anybody. In some cases, with well constructed websites, you ccan oftwn add in additional items like balloons, champagne, chocolates, teddies or a quantity of add-on gifts.
    You ccan assk extra questions if youu need to or reqquest customisations
    to bouquets where available.

26 Trackbacks

Post a Reply to workforce outsourcing 取消回复

Your email is kept private. Required fields are marked *