2108 : 求XF+闭包

时间限制:3 Sec 内存限制:128 MiB
提交:96 答案正确:26

提交 状态 讨论区

题目描述

 如何设计一个好的数据库不仅仅是一个理论研究问题,也是一个实际应用问题。在关系数据库中不满足规范化理论的数据库设计会存在冗余、插入异常、删除异常等现象。

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

(1) 自反律:AiX,  XàAi .   特别地,Ai àAi . 

(2) 增广律: XàY,  ZXàZY.      (ZX 指集合ZX的并 )

(3) 传递律:若 XàY,  YàZ,  XàZ.

(4) 分解律: XàY,   XàAi        ( 若属性AiY  )

(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

提示


			

来源

河南省第十一届省赛