论文部分内容阅读
XML (eXtensible Markup Language)是被w3c基于标准的广义标记语言所创建,被用作定义语义标记。在Web服务、电子商务、数字图书馆等诸多网络相关应用领域已经成为描述数据的事实上的标准。为了方便用户从海量的XML数据中提取他们所需要的信息,许多XML数据查询算法应运而生,使得XML数据查询成为XML数据管理领域的一个热点。本文将这些XML数据查询算法按照查询模式描述的不同分为两类,即XML结构查询和XML关键字查询。前者多采用了正则表达式的描述方法,偏向于传统的结构化的查询方式,能够清楚的表述用户的查询意图；后者融入了信息检索领域常用的查询思想和方法,允许用户仅仅输入关键字就能够进行查询。XML结构查询算法根据精确的查询条件,能够输出理想的查询结果。然而,该算法对进行查询的用户也提出了更高的要求,即不仅要熟悉结构查询算法所采用的查询语言,而且还要了解待查询的XML文档树结构。以上要求对于绝大多数用户而言是不切实际的,所以从用户的角度出发,XML关键字查询是一种能够被广泛使用的查询方法。XML关键字查询方式中最关键的问题是如何求解包含所有关键字的最小XML片段,即SLCA (Smallest Lowest Common Ancestors)问题。目前已有许多求解算法,包括Stack、ILE、SE、LISA和LISA II等。ILE和SE在与Stack的实验对比中表现得效率更高,适合需要频繁I／O操作的海量XML查询,他们仅需要顺序读取XML数据一遍；相比ILE和SE, LISA和LISAⅡ在轻量级XML查询中,无论是在理论分析上还是试验对比中都表现出了更好的性能。然而,LISA不仅需要频繁扫描节点,而且需要引入集合交操作,耗费了大量CPU周期。LISA II虽然在避免不必要扫描方面改进了LISA算法,但却使用了自己独有的编码,不仅引入了编码映射,而且也使得该算法的通用性大大削弱。这两种算法即便作为一种仅在内存中执行的算法,以上缺点也影响了查询速度。为此,本文提出一种轻量级的、使用XML关键字查询通用的Dewey编码的新算法,BCS (Binary Comparative Search Algorithm),即二分比较查找求解包含XML关键字的最小片段问题。该算法有效地提高了搜索效率,对于数据量较大的XML树中,搜索效率提高尤其明显。BCS无论在理论分析上还是试验对比中,都表现出了较好的性能,是一种可行的最小包含关键字片段求解算法。作为一种新的XML关键字查询算法,BCS具有查询简便快捷、普通用户使用门槛较低、用户友好等的特点,但是也会存在查准率相对于XML结构查询算法较低的XML关键字查询的先天缺陷。