在网格数据组织中使用概念

摘要：商业企业每天产生大量的网格数据，作为网页信息交换的实际标准，最重要的挑战之一是如何有效地进行数据搜索，数据搜索可以以链接的方式进行。一些研究人员已经研究出了演算法，以减少搜索过程中产生的无效信息。另一些研究人员引入了记录法，可以进行相关元素的定位，无需搜索原始网格文档，通过记录的方式完成搜索过程。文中介绍的方法是基于正在被搜索的数据的概念，以及对网格数据库的内容搜索及关键字搜索，使用概念搜索可以提高搜索效率。
关键词：网格；搜索；最佳化；演算；网页描述语言WSDL

    半结构化数据在网页中的高级应用越来越普遍，商业企业每天生产及消费大量的数据。网格作为网页上半结构化的数据具有相当复杂的内部结构，有时还被提取出来作为命令树。
    在大多数的网格搜索语言中，网格查询的结构以链接的形式出现，网格元素的价值被用作选择谓词的一部分。有效链接模式匹配是网格数据库中网格搜索程序的关键。
    笔者概述了一种创新方式，将数据的概念考虑进来进行网格搜索，介绍了在网格数据库中进行关键词搜索的一种有效的演算法。该方法的实质是，如果数据的概念是已知的，那么数据的概念可以用于搜索最佳化。
    首先定义一个数据模型，称之为CRD—FS。半结构化的数据对象-关系-属性模式，包括概念数据模型的实体，以及层次结构网格数据。有了CRD—FS数据模型，许多网格数据库的概念可以明确的被呈现，但是不能被WSDL及网格模式所识别。

1 相关工作
    X路径是通过网格文档中的元素及属性，在网格文档中发现信息的一种语言，同UNIX文档系统中的目录相似。例如，通过X路径的表示：／院系／课程[代码=＼cs4221"]／学生、学生姓名。可以表示为＼cs4221"课程的学生的名字。一条X路径的搜索可以经树状图表表示，称为链接方式。X路径被作为链接形式搜索的方式被呈现。
    Chippimolchai et al．发展了一种演绎数据库中概念搜索的最佳化框架。他们概述了一种演算方法，可以将搜索转换成查询及完整性约束，这些整体性约束是从真实世界产生的，不能从网格模式或WSDLs．中产生。

2 CRD-FS数据模型
    半结构化的对象，关系，属性数据模式有4个基本概念：对象类，关系类别，属性及参考，包括4个图表：模式图表、距离图表、功能独立性图表及层次图表。
    一个CRD—FS模式图表代表着作为标签的一个对象类。对象类之间的联系类型被描述为标签姓名(对象类清单)，N，P，C"，此处的姓名指示了关系类型的名称，对象类是参与到关系类型中的对象类清单，N是一个整数，标明了关系类型的程度，P和C是关系类型中的参与限制，定义了使用标准的最小及最大的符号。两个对象类之间的边缘可以有多于一个的这样的关系类型标签去标明对象类所参与的不同的关系类型。关系类的属性或者关系类型是有标签圆圈所注解的。对象类的标识符像填充的圆圈一样被注解，所有的属性都应当并强制的，单值的，包含一个"?"，标明这是单值的，可选的，或者是一个"+"标明多值并且是被请求的，或者是一个"*"，标明其实可选多值的。对象类的属性可以从一个关系类型中相区分出来。前者没有边缘标签，当后者的关系类型的名称属于自己的标签边缘时。
    属性的名字，代码和学生编号分别是对象类院系、课程和学生的标识符。每个学生都有其独有的学生编号。标题的属性、标记、地址和业余爱好都是可选的。业余爱好是多属性，而学生姓名是必需的。这里有两种关系类型，被称之为dc and cs．前者是对象类部门同课程之间的二进制关系类型，后者是课程同学生之间的二进制关系类型。一个院系可以由一个或更多的(1：n)课程，一项课程属于一个或只一个院系(1：1)。一门课程可以由零个或更多(0：n)学生；一名学生可以选修一门或更多课程。学生同标记之间的边缘上的标签cs标明标记是关系类型cs的单独价值属性。也就是说，一门课程中一名学生的属性标记。从这些约束条件中，可以派生出{课程；学生}→标记。

3 搜索过程中概念的使用
    概念是通过CRD-FS模式进行优化链接模式，从而用3个链接查询来进行搜索评估的。
    搜索1：找出等同于"s123"的学生元素的学生姓名值，X路径表示为：／／student[@stuNo="s123"]／stuName
    利用CRD—FS模式，可以知道学生姓名是学生对象类的一个单一值属性，学生编号是学生的身份标识，因此学生编号→学生姓名。为了处理搜索，我们只需要找出带有学生编号属性的网格中的第一个学生元素即可。
    此外，Wu et al．已经提议了一种演算方式，它集中搜索内容或具有概念信息值。
    搜索2：找出所有学生的平均分。
    解答该搜索处理器需要了解学生编号是对象类学生的标识符，并且要将课程同学生之间的关系类的单值属性标记出来。
    搜索3：找出课程中所有学生所取得的分数。
    为了正确完成以上搜索，用户需要明白学生编号是学生的标识符，代码是课程的标识符，标记是课程与学生之间关系类型的单值，每一门课程仅仅由一个院系所提供，每一门课程在网格文档中仅仅出现一次。当WSDLs模式无法捕捉所有所需概念时，该信息可以在CRD-FS模式图表中被捕捉。
    有了CRD—FS数据模型所捕捉的概念，我们可以解释网格询问是否正确，是否可以提高搜索评估性能。利用存储在CRD-FS模式图表中的概念，图解搜索语言GLASS能够自动生成搜索所用的X搜索，用户没有必要去编写X搜索询问。

4 网格中的内容搜索
    网格文档中处理一个链接模式的搜索包括结构搜索及内容搜索。大多数现有的演算方法无法将内容同结构搜索相区分。在结构处理期间，它们将内容节点同元素节点一样处理，搜索所询问的实际值需要依赖于原始文档。我们提议将带有相关表格的一个新的演算值(VERT)提取来克服这些局限。VERT技术是生成相关表格以便来存储文档内容，而不是将他们像节点那样进行处理和标记。笔者所说的演算是基于文档的概念信息。因为越多的概念被捕捉，笔者就可以进一步优化表格及询问这样可以极大的提高效率。
    例如，考虑带有包含标签的网格树。可以将数值内容同关系标签中的母标签一同存储，而不是为每个网格标签和数值内容存储标签数据流。有了这些关系表，当用户在发出一个链接搜索时，系统就能够自动将其重写至搜索中，这里节点价格大于15，他们的PC关系被称之为>15的价格节点所取代。可以在表格Rprice中执行至带有数值的所有价格元素当中。其性能结构以书本的标签数据流为基础。ISBN以及价格’> 15，以这种方式，可节省所有大于15的数值内容的数据流的成本，以及在合并标签数据流之间的结构的成本。用这种方式，当处理链接搜索时，也可以节省书本对象同其价值属性之间的结构及其价格。
    最终，基于由ORASS所捕捉到的概念，标题，价格等是书本对象类的唯一价值属性，能够将这些属性的内容价值premerge到一个单独的带有书本对象标签的关联表格，有了premerged表格，可以对链接搜索作出回答。在premerged表格上仅仅可以完成一种有效的选择。

5 网格中关键字连同概念的搜索
    关键字的近似搜索是搜索网格数据库的一种友好方式。该区域多数前期所做的努力都是集中于网格关键字近似搜索。网格的数据模式普遍都很简单并且有效。然而，它们并不捕捉数据库中的联系，例如身份参考。相反，是基于图表模式的捕捉联系的技术，不过这些大多对于计算来说都是无效的。许多现有的技术并不开发模式信息，这些信息通常是以数据库的形式出现。没有了模式信息，关键词近似技术在结果中呈现的可能性会很小，并且它们所返回的结果是不相关的。例如，LCA对于基于树状模式的关键字近似搜索会很大一部分返回到其全部数据库的根部。
    笔者建议的是一种互连对象模式，可以充分开发网格性能并且在模式出现时标注出其模式信息。在我们的模型中，数据库管理员为结果标识出感兴趣的对象类及同兴趣对象之间的概念性连接。
    有了感兴趣的对象类，关于关键字近似搜索最具直觉结果的是含有所有关键字的兴趣对象的清单。较之众所周知的LCA概念(Lowest Comm on Ancestor)，将这些兴趣清单称之为ICA(Interested Common Ancestor)。同样，用IRA(Interested Related Ancestors)概念来捕获兴趣对象及包含更多相关结果。一个IRA结果是一对包含所有关键字的对象，并且同概念性连接是联系在一起的。例如，为了搜索"网格搜索程
序"，带有标题"搜索程序"的标题以及引用或被"网格"所引用的论文被看作是IRA对象。
    就执行时间和结果质量而言，实验性的评估标明该方法要优于大多现存的学术系统。

6 结论
    半结构化数据组织中的重要区域之一就是提供可以进行有效数据搜索的演算。本文中概述了一个最佳化方案，在数据已知的时候可以被引用。介绍了一种数据模型，在ORASS中可以呈现出必要的概念，并且已完成的最佳化方案进行描述，展示了当概念被包含在内的时候，链接方式是如何最佳化的。如何处理历史链接演算中的价值，概念性的连接与对象类之间如何被运用在关键字接近的搜索中。
    今后将研究如何使用ORASS中捕捉的其他概念进行链接方式询问的进一步优化，这些优化方案哪些地方是有价值的，通过实验来表明处理速度的提高。特别的信息是如何同最优化方式所链接的，如母子、始祖一后裔关系，否定，节点的指令，恒定值及节点输出。