计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2009年
23期
144-148
,共5页
可扩展标记语言%树模式查询%文档类型定义(DTD)约束
可擴展標記語言%樹模式查詢%文檔類型定義(DTD)約束
가확전표기어언%수모식사순%문당류형정의(DTD)약속
目前大部分 XML 查询语言都使用树模式来匹配待查询的 XML 文档树以得到所需要的、与模式树相吻合的查询结果,此效率在很大程度上取决于 XML 模式树的大小,那么尽可能快速地查找并删除查询模式树中的冗余节点就变得十分重要.重点讨论 DTD 约束下树模式的最小化问题,将 DTD 兄弟约束 SC 拓展成扩展兄弟约束 ESC,使其能够表达 DTD 约束中的祖先一后代关系;并指出只包含{ESC/,//,∏,*}的查询树模式的最小化问题的复杂度是指数级的,且当模式树是分支受限的时候,其最小化问题的复杂度是多项式时间的;最后给出了一个多项式时间的受限分支的模式树最小化算法.
目前大部分 XML 查詢語言都使用樹模式來匹配待查詢的 XML 文檔樹以得到所需要的、與模式樹相吻閤的查詢結果,此效率在很大程度上取決于 XML 模式樹的大小,那麽儘可能快速地查找併刪除查詢模式樹中的冗餘節點就變得十分重要.重點討論 DTD 約束下樹模式的最小化問題,將 DTD 兄弟約束 SC 拓展成擴展兄弟約束 ESC,使其能夠錶達 DTD 約束中的祖先一後代關繫;併指齣隻包含{ESC/,//,∏,*}的查詢樹模式的最小化問題的複雜度是指數級的,且噹模式樹是分支受限的時候,其最小化問題的複雜度是多項式時間的;最後給齣瞭一箇多項式時間的受限分支的模式樹最小化算法.
목전대부분 XML 사순어언도사용수모식래필배대사순적 XML 문당수이득도소수요적、여모식수상문합적사순결과,차효솔재흔대정도상취결우 XML 모식수적대소,나요진가능쾌속지사조병산제사순모식수중적용여절점취변득십분중요.중점토론 DTD 약속하수모식적최소화문제,장 DTD 형제약속 SC 탁전성확전형제약속 ESC,사기능구표체 DTD 약속중적조선일후대관계;병지출지포함{ESC/,//,∏,*}적사순수모식적최소화문제적복잡도시지수급적,차당모식수시분지수한적시후,기최소화문제적복잡도시다항식시간적;최후급출료일개다항식시간적수한분지적모식수최소화산법.
