XML Schema特征提取算法

计算机科学 ›› 2015, Vol. 42 ›› Issue (Z11): 438-443.

• 软件工程与数据库技术 • 上一篇下一篇

XML Schema特征提取算法

刘科,杨红丽,赵瑞芳,廖湖声,陈瑶,秦胜潮

北京工业大学计算机学院北京100124,北京工业大学计算机学院北京100124,北京工业大学计算机学院北京100124,北京工业大学软件学院北京100124,北京工业大学计算机学院北京100124,提赛德大学计算机学院米德尔斯堡TS1 3BA

出版日期:2018-11-14 发布日期:2018-11-14
基金资助:
本文受北京市自然科学基金:面向XQuery语言的树模式查询技术研究(4122011)资助

XML Schema Features Extraction Algorithm

LIU Ke, YANG Hong-li, ZHAO Rui-fang, LIAO Hu-sheng, CHEN Yao and QIN Sheng-chao

Online:2018-11-14 Published:2018-11-14

摘要/Abstract

摘要： Twig模式最小化作为XML查询优化的一个重要方面,由于在进行最小化的过程中通常要利用XML Schema中的约束信息,因此被称为Schema特征。为了简化运用传统方法提取Schema特征的过程,以及确保提取过程的正确性, 提出了一种自动提取Schema特征的模型检查算法。在Schema的形式模型的基础上,利用扩展的CTL公式表示Schema特征,提出算法以检查Schema模型是否满足要求的特征。由于扩展了CTL公式,所提算法不但可以检查孩子、子孙等前向的Schema特征,而且可以检查双亲、祖先等后向特征。最后,实现了支持该算法的模型检查器。

关键词: XML Schema特征,模型检查,时态逻辑

Abstract: As an important aspect of XML query optimization－Twig pattern minimizing,usually needs to take advantage of the constraints of XML Schema during the minimization process,so it is called Schema features.To simplify the traditional methods of extracting Schema features,and to ensure the accuracy of the extraction process,we proposed a model-checking algorithm to extract XML Schema features automatically.Based on the formal model of an XML Schema,we used an extended CTL formula to express Schema features,and proposed an algorithm to check if an XML Schema model satisfies CTL formula.Due to the expansion of CTL formulas,the proposed algorithm can not only express the prior Schema features,but also represent parents,ancestors and other backward features.Finally,we realizaed a aids tool for our methods.

Key words: XML schema features,Model checking,Temporal logic

刘科,杨红丽,赵瑞芳,廖湖声,陈瑶,秦胜潮. XML Schema特征提取算法[J]. 计算机科学, 2015, 42(Z11): 438-443. https://doi.org/

LIU Ke, YANG Hong-li, ZHAO Rui-fang, LIAO Hu-sheng, CHEN Yao and QIN Sheng-chao. XML Schema Features Extraction Algorithm[J]. Computer Science, 2015, 42(Z11): 438-443. https://doi.org/

参考文献

[1] Jagadish H,Lakshmanan L,Srivastava D,et al.Tax:A tree algebra for xml[C]∥Database Programming Languages.Sprin-ger,2002:149-164
[2] Boag S,Chamberlin D,Fernández M F,et al.Xquery 1.0:An xml query language[J].IBM Systems Journal,2005,1(4):597-615
[3] World Wide Web Consortium.XQuery1.0 and XPath2.0 Formal Semantics[DB/OL].http://www.w3org/TF/xquery-semantics/
[4] Amer-Yahia S,Cho S R,Lakshmanan L V S,et al.Tree pattern query minimization[J].The International Journal on Very Large Data Bases,2002,11(4):315-331
[5] Paparizos S,Patel J M,Jagadish H V.Sigopt:Using schema to optimize xml query processing[C]∥IEEE 23rd International Conference on Data Engineering,2007(ICDE 2007).IEEE,2007:1456-1460
[6] Chen D,Chan C Y.Minimization of tree pattern queries withconstraints[C]∥Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data.ACM,2008:609-622
[7] Che D.An efficient algorithm for tree pattern query minimization under broad integrity constraints[J].International Journal of Web Information Systems,2007,3(3):231-256
[8] Lee K H,Whang K Y,Han W S.Xmin:Minimizing tree pattern queries with minimality guarantee[J].World Wide Web,2010,13(3):343-371
[9] Clarke E M,Schlingloff B H.Model checking[M]∥Handbook of Automated Reasoning.2000:1367-1522
[10] Afanasiev L,Franceschet M,Marx M,et al.CTL model checking for processing simple xpath queries[C]∥Proceedings of 11th International Symposium on Temporal Representation and Reasoning,2004(TIME 2004).IEEE,2004:117-124
[11] Libkin L,Sirangelo C.Reasoning about xml with temporal logics and automata[C]∥Logic for Programming,Artificial Intelligence,and Reasoning.Springer Berlin Heidelberg,2008:97-112
[12] Libkin L.Logics for unranked trees:An overview[C]∥ICALP’ International Colloquium on Automata,Lauguages,and Programming.2005:35-50
[13] Arenas M,Barcel′o P,Libkin L.Combining temporal logics for querying XML documents[C]∥Manuscript,International Conference on Database Theory-ICDT.2007:359-373
[14] Neven F.Automata theory for XML researchers[J].ACM Sigmod Record,2002,31(3):39-46
[15] Schwentick T.Automata for XML—a survey[J].Journal ofComputer and System Sciences,2007,73(3):289-315
[16] Huth M,Ryan M.面向计算机科学的数理逻辑系统建模与推理[M].北京:机械工业出版社,2007
[17] 刘科,杨红丽,廖湖声,等.基于模型检查的 XML Schema 特征提取[J].计算机应用与软件,2012,29(11):160-164
[18] Schreiber E L.A CUDD Tutorial[DB/OL].http://docslide.us/documents/schreiber-cudd-tutorial.html
[19] 张剑妹,陶世群,梁吉业.XML结构完整性约束下的路径表达式的最小化[J].软件学报,2009,20(11):2977-2987
[20] 刘科.Twig模式优化动作生成方法研究[D].北京:北京工业大学,2013
[21] Apache XML.Project.Xerces C++ Parser[DB/OL].https://xerces.apache.org/xerces-c/charter.html

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

XML Schema特征提取算法

XML Schema Features Extraction Algorithm

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

Metrics

本文评价

推荐阅读 0