基于PHP计算属性集的闭包

2014-12-18王小兵于思江

电子科技 2014年3期

王小兵，于思江

(1.西安电子科技大学计算机学院，陕西西安 710071;2.西安邮电大学财务处，陕西西安 710121)

关系模型具有严格的数学理论基础，规范化理论在数据库逻辑设计中具有重要的作用。关系属性之间存在的约束关系通过数据依赖体现出来［1］。函数依赖是一种常见的数据依赖，在模式设计的过程中，通常需要判定某一个特定的函数依赖是否成立。然而，计算函数依赖集闭包的方法过于复杂，是一个NPC难题，可以借助于计算属性集闭包进行简化。

计算属性集闭包一般需要使用集合操作，如判等、并。如果使用一般高级语言，如C、C++，虽然效率较高，但需要定义集合操作［2］，代码量较大，不易于实现与维护。若使用专用的语言，如 Matlab［3］、Mathematica［4］，可以用数组或表来描述函数依赖集，借助于语言自带的集合操作，可方便地实现计算，但函数依赖的描述并不直观［3－4］。PHP是一种通用的脚本语言，适用于Web开发，可生成用户浏览的网页［5］。PHP语言中的数组具有集合的特性，并且支持经典的并、交、差等操作，能够实现属性集闭包的计算。另外，PHP程序可在Web服务器软件中运行，还可以和C程序一样独立运行。

本文介绍了函数依赖、逻辑蕴含、函数依赖集闭包与属性集闭包的相关定义与算法，基于PHP中的数组实现了计算属性集闭包的函数Closure，并通过一个具体的程序实例来说明函数依赖集的初始化与Closure函数的调用方法。

1 相关定义与算法

本文讨论涉及到函数依赖、逻辑蕴含、函数依赖集闭包F+与属性集闭包X+F，它们的定义［1］及相互联系介绍如下。

定义1 R(U)是属性集U上的关系模式。X，Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数确定Y或Y函数依赖于X，记作 X→Y。

定义2 对于满足一组函数依赖F的关系R＜U，F＞，其任何一个关系r，若函数依赖X→Y都成立，则称F逻辑蕴含X→Y。

定义3 在关系模式R＜U，F＞中为F所逻辑蕴含的函数依赖的全体叫作 F的闭包(Closure)，记为F+。

F+包含了给定函数依赖集F所蕴含的属性集U上的全部函数依赖。判定一个函数依赖X→Y是否成立，即是计算F+，再判定其是否包含X→Y。然而，根据Armstrong公理系统计算F+是一个NPC问题，需要通过其它的方法进行简化。

判定X→Y是否成立，只需要计算出X+F，再判定Y是否为其子集。该方法计算的仅是X能够函数确定的所有属性，较前一种方法无目标的计算F+大幅减少了计算量，从而使问题得到了简化。

算法1 求属性集X(X⊆U)关于U上的函数依赖集F的闭包X+F。

输入:X，F，U

输出:XF+

(1)令 X(0)=X，i=0;

(3)X(i+1)=B∪X(i);

(4)判断X(i+1)=X(i)吗?

(5)如相等或X(i)=U则X(i)就是XF+，算法终止;

(6)若否，则i=i+1，返回第(2)步。

2 PHP实现Closure函数

PHP是一种服务器端的嵌入式HTML脚本语言。最初时称作Personal Home Page Tools，当PHP使用范围日趋广泛后，它被认为是PHP:Hypertext Preprocessor的缩写。PHP一般适用于Web开发，用户通过浏览器向服务器发送执行PHP程序的请求，解释器解释运行后，用户可以浏览网页形式的输出结果。PHP可以在Web服务器软件，如IIS、Apache等中运行，还可以直接运行，如执行php.exe compute.php将compute.php的结果输出到屏幕。

PHP支持的数组具有数据集合的特性，支持修改、删除、排序、查询、并、交、差等操作，为计算属性集闭包提供了足够的前提条件。函数依赖X→Y可以通过PHP中的一个二维数组来表示，例如AB→C对应array(array(‘A’，‘B’)，array(‘C’))。计算属性集闭包涉及到的数组函数介绍如下。

array array_diff(array array1，array array2 ［，array...］):返回一个数组，该数组包括了所有在array1中但不在任何其它参数数组中的值。

array array_merge(array array1，array array2 ［，array...］):将两个或多个数组的单元合并起来，一个数组中的值附加在前一个数组的后面。返回作为结果的数组。

array array_unique(array array):接受 array作为输入并返回没有重复值的新数组。

int count(mixed var［，int mode］):返回 var中的单元数目，通常是一个 array(任何其它类型都只有一个单元)。mode参数设为 COUNT_RECURSIVE(或1)，count()将递归地对数组计数，默认值是0。

基于上述的数组函数和算法1，定义PHP函数Closure在Closure.php中，如下所示。输入参数$U为全体属性数组，$F为全体函数依赖数组，$X为需要计算闭包的属性集数组。输出为$X在$F上的属性集闭包。

若array_diff($U，$X)为空数组，则$U是$X的子集，而$X肯定是$U的子集，所以此时$U与$X 相等，算法终止。若 array_diff($F［$i］［0］，$X)为空数组，则第$i个函数依赖的左部是$X的子集，则该函数依赖的右部应该加入到结果$X中，通过 array_merge($X，$F［$i］［1］)来实现，然后调用array_unique排除当中重复的属性。3程序实例

例1 已知关系模式R＜U，F＞，其中U={A，B，C，D，G，H}，F={AB→C，C→AB，B→D，D→B，A→G，G→H，H→A}，求(AB)+F。

编写调用Closure函数的程序compute.php如下