计算机科学 ›› 2015, Vol. 42 ›› Issue (Z11): 438-443.
刘科,杨红丽,赵瑞芳,廖湖声,陈瑶,秦胜潮
LIU Ke, YANG Hong-li, ZHAO Rui-fang, LIAO Hu-sheng, CHEN Yao and QIN Sheng-chao
摘要: Twig模式最小化作为XML查询优化的一个重要方面,由于在进行最小化的过程中通常要利用XML Schema中的约束信息,因此被称为Schema特征。为了简化运用传统方法提取Schema特征的过程,以及确保提取过程的正确性, 提出了一种自动提取Schema特征的模型检查算法。在Schema的形式模型的基础上,利用扩展的CTL公式表示Schema特征,提出算法以检查Schema模型是否满足要求的特征。由于扩展了CTL公式,所提算法不但可以检查孩子、子孙等前向的Schema特征,而且可以检查双亲、祖先等后向特征。最后,实现了支持该算法的模型检查器。
[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 |
No related articles found! |
|