XML在图书查询系统中的实现技术，本文主要内容关键词为：查询系统论文,图书论文,技术论文,XML论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
【分类号】 G250.76
1 引言
由于XML结合了HTML和SGML两者的优点，同时克服了它们的不足，因此，XML自诞生之日起就获得了广泛的关注，使其具有广阔的应用前景，尤其在网络上得到了迅速的普及，使XML成为Intenet以及各种信息集成中的数据交换格式[1,2]。另外，XML结构的灵活性，是它与关系数据库的最大差别，为此，XML也被人们普遍认为是一种典型的半结构数据[3,4]。
Petri网是一种具有数学描述能力，又有图形直观表示的模型工具，这主要体现在它不仅能描述系统的静态行为，而且能刻画系统的动态特性，尤其擅长描述和分析那些含有并发成份的复杂系统。Petri网能从组织结构、控制和管理的角度，精确描述系统中事件之间的依赖和不依赖关系[5,6]。
XML和Petri网怎样应用于图书查询系统是本文着重探讨的问题。
2 思路
本文的思路在于把XML的结构和XML的数据分别建立模型，根据XML的DTD结构建立描述XML语义结构的Petri网模型，而XML的数据则存放在根据Petri网模型的结构生成的关系数据库中。具体实现技术可以从以下三个方面论述：
(1)XML DTD描述了XML数据应遵守的路径结构，它的信息量通常比XML本身小得多。利用DTD建立XML语义路径模型，描述XML语义结构。
(2)采用Petri网建模XML语义结构模型。在Petri网模型中，库所与库所之间通过变迁连接，利用变迁的自点燃能力和并发能力提高路径表达式的查询效率。
(3)根据Petri网模型的结构生成存储XML数据的关系数据库模型，将XML的查询问题最终转化为关系数据库中数据的查询操作。
3 Petri网模型定义
3.1 XML的DTD结构
DTD是一套关于XML文档中标记符的语法规则。DTD主要由元素声明、属性声明、记法声明和实体声明组成。元素声明由元素内容模型来描述，该模型中的内容采取一组正则路径表达式(RPE)的形式。RPE中出现的元字符有：“*”、“＋”、“？”、“，”、“｜”、“（）”和“#PCDATA”，其中决定XML语义路径构成的元字符是：“，”、“｜”和“（）”。下面是典型的XML图书列表的DTD示例。
3.2 XML语义结构的Perri网模型
(1)Petrl网基本概念[7,8]
在图1中，用短划线表示变迁(T)，用圆圈表示库所(P)，变迁之间、库所之间不能有有向弧，变迁与库所之间连接有向弧，由此构成的有向二分图称作网。网的某些库所中标上若干黑点，称谓托肯(M)，从而构成Petri网。
图1 一个简单的Petri网
(2)描述XML语义结构的Petri网模型
定义：Petri网是一个多元组
E：是DTD中元素和属性名称的有限集合。
P：是库所的有限集合。库所对应DTD中的元素或属性名称。
T：是变迁的有限集合。变迁对应DTD中的元素声明中RPE的“（）”操作符、“｜”操作符或属性声明。
M(p)：是p的一个标记值，反映了该库所在当前操作中拥有的托肯情况。
对应于元素名称为τ的库所定义为虚库所。τ不构成XML语义路径的成分。在图2的Petri网模型中，可以把p[,11]虚库所看作是p[,8]库所状态的持续。因此，在建立XML语义路径结构的Petri网模型时，利用虚库所，可以将任何复杂的元素声明简化为若干条简单的元素声明。
图2 Petri网模型
4 生成关系数据库模型
考虑到XML图书列表的DTD示例中一些元素后面带有通配符，还有一些元素之间存在或选关系，另外还考虑到图2所示的Petri网模型中定义了虚库所。因此，综合以上两种考虑，在进行关系数据库设计时，首先要建适当数量的数据表，同时，在对数据表进行规范化处理后，要保证所有数据表都能满足第二范式，力求大多数数据表满足第三范式[9]。
根据图2所示，在关系数据库模型的设计中，共建五张数据表，关系模式分别为：书表(
，书号，书名，出版社，价格）；作者表(,PID，作者）；评注作者表(,PID，作者，身份）；标题内容表(,PID，标题，内容）；简评表(,PID，简评），其中划线部分为各数据表的主键。
除了作者表的PID字段（外键）与其同一级的书表的ID字段（主键）相关联以外，其它各张数据表的PID字段与其上一级的数据表的ID字段相关联。具体的多表关联方式为：
a.书表.ID＝作者表.PID
b.书表.ID＝评注作者表.PID
c.评注作者表.ID＝标题内容表.PID
d.评注作者表.ID＝简评表.PID
上述关系数据库模型的设计均满足数据库关系完整性设计和数据库规范化设计[10]。
5 路径表达式的查询方法
(4)当没有变迁可点燃时，将库所中的托肯转化为关系数据库中的SQL语句，并优化SQL语句。
：
“&”是一个替换符，&y是将y的字符串内容替换在&y所在位置。
在from项中，存在多个数据表时，对于相同的数据表只取一个，其余的都删除。对于不同的数据表，牵涉到多个数据表的查询，在定义数据表的关系模式时已经确定了多个数据表之间的关联，可将联接条件加入到where项中。
(5)在关系数据库上执行SQL语句，生成关系数据库形式的查询结果，再结合Petri网的语义结构，最终生成查询结果的XML文档。
6 系统设计方案以及实现技术
根据前面所提及的XML图书列表示例，设计一套基于Petri网的XML图书查询系统。最终，给用户提供一个应用软件，用户只要输入查询的路径表达式，就可以对基于Petri网的XML图书查询系统进行快速的数据查询并自动输出查询结果的XML文档。
Petri网模型和数据表在内部处理时使用，对用户来说是不透明的，而面对用户的只是XML文档的DTD结构、XML文档本身以及查询结果的XML文档。若要用户了解Petri网方面的知识，用户的负担就加大了。
使用VB.NET对用户使用界面和Petri网模型的结构进行程序设计，并将XML的数据导入事先根据Petri网模型的结构设计好的Access2003中去。在VB.NET中，通过ADO.NET来进行数据访问。
6.1 Petri网数据结构描述
Structure PetriP
′库所
Dim t()As Integer
′点燃以该库所为输入库所的变迁
Dim Element As String ′库所对应的元素
Dim Table As String′该元素存储的数据表名
Dim Field As String′该元素所存储的字段
End Structure
Structure PetriT
′变迁
Dim OutP()As Integer
′变迁输出的库所
End Structure
6.2 Petri网涉及到的公用变量描述
Dim p() As PetriP′petri中的库所
Dim T() As PetriT′petri中的变迁
Dim SqlP(0) As SqlElement ′返回符合查询条件的库所所涉及的字段、条件、表名以及库所索引
6.3 Petri网算法描述
(1)构造petri网
Public Sub New()
ReDimp(14)定义库所数组
′输入每个库所的相关数据：
P(1).Element＝“图书列表”
ReDimp(1).t(1)
p(1).t(1)=1
p(2).Element＝“书”
ReDimp(2).t(2)
p(2).t(1)=2
p(2).t(2)=3
P(3).Element＝“书号”
p(3).Table＝“书表”
p(3).Field＝“书号”
p(4).Element＝“作者”
p(4).Table＝“作者表”
p(4).Field＝“作者”
p(5).Element＝“书名”
p(5).Table＝“书表”
p(5).Field＝“书名”
p(6).Element＝“出版社”
p(6).Table＝“书表”
p(6).Field＝“出版社”
p(7).Element＝“价格”
p(7).Table＝“书表”
p(7).Field＝“价格”
p(8).Element＝“评注”
ReDim p(8).t(1)
p(8).t(1)=4
p(9).Element＝“作者”
p(9).Table＝“评注作者表”
p(9).Field＝“作者”
p(10).Element＝“身份”
p(10).Table＝“评注作者表”
p(10).Field＝“身份”
P(11).Element＝“τ”
ReDim p(11).t(2)
P(11).t(1)=5
p(11).t(2)=6
p(12).Element＝“标题”
p(12).Table＝“标题内容表”
p(12).Field＝“标题”
p(13).Element＝“内容”
p(13).Table＝“标题内容表”
p(13).Field＝“内容”
p(14).Element＝“简评”
p(14).Table＝“简评表”
p(14).Field＝“简评”
ReDim T(6)′定义变迁数组
′输入每个变迁的相关数据：
ReDim T(1).OutP(1)
T(1).OutP(1)=2
ReDimT(2).OutP(1)
T(2).OutP(1)=3
ReDimT(3).OutP(5)
T(3).OutP(1)=4
T(3).OutP(2)=5
T(3).OutP(3)=6
T(3).OutP(4)=7
T(3).OutP(5)=8
ReDim T(4).OutP(3)
T(4).OutP(1)=9
T(4).OutP(2)=10
T(4).OutP(3)=11
ReDimT(5).OutP(2)
T(5).OutP(1)=12
T(5).OutP(2)=13
ReDimT(6).OutP(1)
T(6).OutP(1)=14
End Sub
(2)petri网工作模式——两个重要函数
Private Function checkT(ByVal xPath As String,ByVal con As String,ByVal tIndex As Integer)As Integer
主要参数：
xPath为语义路径
tlndex为变迁数组索引
返回：变迁输出并符合语义路径的库所
功能：检查变迁T(tlndex)所输出的库所，并调用checkP函数
Private Function checkP(ByVal xPath As String,ByVal con As String,ByVal plndex As Integer)As Integer
主要参数：
xPath为语义路径
plndex为库所数组索引
返回：库所P(pIndex)点燃的变迁
功能：
①返回库所P(pIndex)需要点燃的变迁，并调用checkT函数；
②点燃库所P(pIndex)所需点燃的变迁，每点燃一个变迁就新开一个进程；
③检查语义路径是否符合条件；
④如果该库所符合查询条件就把其索引记录在SqlP()中。
(3)petri网程序流程
①调用sub new()构造一个Petri网；
②输入查询条件，并进行预处理；
③调用Function CheckP()检查初始库所。本阶段会把符合查询条件的库所索引记录在数组SqlP()中；
④根据数组SqlP()，生成SQL语句；
⑤执行SQL语句；
⑥生成查询的XML文档。
(4)Petri网设计特点
本程序构造了一个Petri网类，把所有操作封装在Petri网类中，尽可能使之高内聚低耦合。在Petri网变迁点燃的设计中，利用两个重要函数交叉递归来完成。库所每点燃一个变迁就会新开启一个进程。如果该进程不符合语义路径，就让该进程湮灭，这样就实现了Petri网的并行处理。需要说明的是，在此种类型的Petri网模型中，每个变迁不存在同时使用两次。
7 系统分析以及实验结果
7.1 规模分析
Petri网是根据XML的DTD结构建立起来的XML语义结构模型，而XML数据则存放在根据petri网模型的结构生成的关系数据库中。因此，Petri网的规模不受XML中的数据量及数据量变化的影响。Petfi网不仅规模小，而且常驻内存，结构稳定。若XML文档共包含m个不同的元素名和属性名，则Petri网的空间复杂度只有O(m)。
7.2 路径表达式查询效率分析
Petri网模型不仅具有良好的层次结构，而且层次的深度也很小。若层次深度为n，查询处理花费在Petri网上的时间复杂度为O(n)。一方面，Petri网的变迁点燃具有并发操作的能力；另一方面，Petri网的变迁点燃只发生在与查询路径相关的变迁与库所上，这就比树结构上所有结点依次搜索的效率高得多。
随着XML数据量的增加，查询处理花费在Petri网上的时间代价并不增加，查询时间的总代价增加很小，这主要受关系数据库的查询时间影响。
7.3 系统查询时间比较
对XML图书查询系统使用基于Petri网的查询方法和使用基于树结构的遍历查询方法分别进行查询操作。查询条件选取（图书列表／书／价格，”＞90.00”），而Q1至Q8是实验中8个不同查询路径，如图3所示。
图3 15000本自XML图书的查询时间比较
8 结语
通过对大量实验数据的分析，可以看出，在XML图书查询系统中，当书的数目大于一定数目时，不管是对简单路径表达式进行查询，还是对复杂路径表达式或者多个路径表达式进行查询，基于Petri网的查询时间总是快于基于树结构的遍历查询时间，由此得出结论：Petri网实现了XML路径表达式的准确定位，并且有效地提高了路径表达式的查询效率。
作为进一步的研究，可以把在XML DTD上建立的Petri网模型推广到在XML Schema上建立Petri网模型。
收稿日期：2006-07-25