Responsive image

问题 C: 数学?

问题 C: 数学?

时间限制: 1 Sec  内存限制: 128 MB
提交: 2  解决: 2
[提交][状态][讨论版][命题人:]

题目描述

        在 数学中,有很多种关系模式,与,或,非,并,差等等,下面给你一个新的关系模式,根据这个新的关系模式得到一个结果。

        设R(U)是一个新的关系模式,U={ A1,A2, ……, An}。其中Ai是关系的属性,X,Y是U的子集。函数依赖 X->Y 定义了数据库中属性集X与Y的依赖关系。根据Armstrong公理,函数依赖满足:

(1)     自反律:若Ai∈X,  则 X->Ai .   特别地,Ai ->Ai .

(2)     增广律:若 X->Y,  则 ZX->ZY.      (ZX 是指集合Z与X的并集 )

(3)     传递律:若 X->Y,  Y->Z,  则 X->Z.

(4)     分解律:若 X->Y,  则 X->Ai        ( 若属性Ai∈Y  )

(5)     合并律:若 X->Y,  X->Z,  则 X->YZ.

 已知 F 是关系模式R(U)上的函数依赖集,利用Armstrong公理系统可以推导出更多的函数依赖。设X是属性集U={ A1,A2, ……, An} 的子集, 定义X关于F的闭包XF+

XF+={ Ai | 若X->Ai可以通过Armstrong公理导出}
对于给定的U , F ,X, 请求出XF+

输入描述

第一行: T        表示以下有T组测试数据             ( 1≤T ≤5 )

对每组数据,

      第1行: n  m  k       n 表示U中属性个数( 1≤n≤26 ), 用大写字母表示

                              m表示X中属性个数( 1≤m≤26 )

                              k个函数依赖  (1≤ k ≤ 20 )

      第2行:  字符串U      n个大写字母

第3行:  字符串X      m个大写字母

接下来有K行,每行有两个字符串 S T,用一个空格隔开。 表示 S->T

输出描述

对每组测试数据,输出占一行输出XF+,要求按字母序输出。

样例输入

1
6 2 4
ABGDCI
AD
A  B
BD  I
AG  C
C  D

样例输出

ABDI
[提交][状态]
ACM算法攻关部