XML数据库查询优化及相关技术研究
|
摘要
随着互联网的快速发展，出现了大量的Web数据。这些Web数据多以XML文档形式出现。如何有效存储、处理XML文档和从大量XML文档中检索有用信息，已成为数据库研究领域的一个重要研究课题。本文的研究工作主要围绕XML数据库的查询优化技术展开，重点研究基于模式信息和语义信息的XML查询优化技术。
针对XML文档的模式信息不精确的特点，提出了基于模糊决策树的XML模式抽取方法。分析了已有XML模式抽取算法的缺点和存在的问题，提出抽取XML近似模式的方法。用一阶Datalog作为XML的表示，用自增量的聚类算法将各实例对象聚类得到模式中的对象，建立模糊决策树来确定模式中各对象的近似模式，解决了模式抽取中的多边和缺边问题。
提出了基于粗糙集的XML数据依赖关系的发现方法。重点讨论了函数依赖和多值依赖关系。给出了XML函数依赖和XML多值依赖的定义。还给出了基于粗糙集的XML函数依赖和XML多值依赖关系的判定定理。基于判定定理，提出了XML函数依赖和XML多值依赖的发现算法。
提出了基于DTD的正则路径表达式查询优化方法。给出了扩展正则表达式的定义，实现对DTD模式树的简化。给出了交结点的定义，提出简路径和补路径两个查询优化策略。该方法通过对XML查询语句的重写，实现对XML语言级上的查询优化。
提出了一种基于树代数的XML代数系统及其逻辑优化策略。给出了一种XML代数的描述，以模式树作为操作对象，定义了操作范围和三类操作符。针对XML查询处理及优化的问题，提出五种XML查询优化策略。针对XML压缩数据库，引入新的解压操作符，将ETA代数扩展到XML压缩数据库上。
提出了基于访问控制的XML查询优化方法。给出了一种高安全的XML访问控制模型，该模型基于访问控制视图，可解决隐推理和结构信息隐藏问题。利用XML访问控制视图实现对XML查询的重写，主要采用剪枝技术，实现XML语言级上的查询优化。
With the rapid development of the Internet, a large number of Web data emerges on the Internet. The Web data formats as XML documents. It becomes an important research topic of database, how to store effectively and process large XML documents, and how to retrieve information from them. The research work in this thesis revolved around query optimization techniques on XML database, focusing on the research of the XML query optimization technology based on schema and semantic information.
For the characters of inaccurate schema, a method of schema mining of XML based on fuzzy decision trees is proposed. Based on analysis of the problems and defects of existing methods of schema mining, the concept of approximate schema is proposed. XML documents are expressed on a monadic Datalog program. Using an incremental clustering method, the approximate schema is constructed by clustering objects with similar incoming and outgoing edge patterns. The perfect schema of the classified objects based on fuzzy decision tree is obtained. It can overcome the defects of the schema mining including two patterns of excess and deficit.
A method of discovering data dependency of XML based on rough sets is proposed. Data dependency is an important concept in database research, included of functional dependency and multivalued dependency. The notions of functional dependency and multivalued dependency in XML are given. The determinant theorems on XML functional dependency and XML multivalued dependency based on indiscernibility relation of rough sets are given. Based on these theorems, the algorithms of discovering data dependency are proposed.
An algorithm of query optimization of regular path expression based on DTD is proposed. The concept of extended regular path expression is defined, and is used to reduce the DTD. The concept of entrance-node is defined. Based on the entrance-node notion, two kinds of regular path expression optimizing principles are proposed, named path shorten and path complementing. Using these two kinds
针对XML文档的模式信息不精确的特点，提出了基于模糊决策树的XML模式抽取方法。分析了已有XML模式抽取算法的缺点和存在的问题，提出抽取XML近似模式的方法。用一阶Datalog作为XML的表示，用自增量的聚类算法将各实例对象聚类得到模式中的对象，建立模糊决策树来确定模式中各对象的近似模式，解决了模式抽取中的多边和缺边问题。
提出了基于粗糙集的XML数据依赖关系的发现方法。重点讨论了函数依赖和多值依赖关系。给出了XML函数依赖和XML多值依赖的定义。还给出了基于粗糙集的XML函数依赖和XML多值依赖关系的判定定理。基于判定定理，提出了XML函数依赖和XML多值依赖的发现算法。
提出了基于DTD的正则路径表达式查询优化方法。给出了扩展正则表达式的定义，实现对DTD模式树的简化。给出了交结点的定义，提出简路径和补路径两个查询优化策略。该方法通过对XML查询语句的重写，实现对XML语言级上的查询优化。
提出了一种基于树代数的XML代数系统及其逻辑优化策略。给出了一种XML代数的描述，以模式树作为操作对象，定义了操作范围和三类操作符。针对XML查询处理及优化的问题，提出五种XML查询优化策略。针对XML压缩数据库，引入新的解压操作符，将ETA代数扩展到XML压缩数据库上。
提出了基于访问控制的XML查询优化方法。给出了一种高安全的XML访问控制模型，该模型基于访问控制视图，可解决隐推理和结构信息隐藏问题。利用XML访问控制视图实现对XML查询的重写，主要采用剪枝技术，实现XML语言级上的查询优化。
With the rapid development of the Internet, a large number of Web data emerges on the Internet. The Web data formats as XML documents. It becomes an important research topic of database, how to store effectively and process large XML documents, and how to retrieve information from them. The research work in this thesis revolved around query optimization techniques on XML database, focusing on the research of the XML query optimization technology based on schema and semantic information.
For the characters of inaccurate schema, a method of schema mining of XML based on fuzzy decision trees is proposed. Based on analysis of the problems and defects of existing methods of schema mining, the concept of approximate schema is proposed. XML documents are expressed on a monadic Datalog program. Using an incremental clustering method, the approximate schema is constructed by clustering objects with similar incoming and outgoing edge patterns. The perfect schema of the classified objects based on fuzzy decision tree is obtained. It can overcome the defects of the schema mining including two patterns of excess and deficit.
A method of discovering data dependency of XML based on rough sets is proposed. Data dependency is an important concept in database research, included of functional dependency and multivalued dependency. The notions of functional dependency and multivalued dependency in XML are given. The determinant theorems on XML functional dependency and XML multivalued dependency based on indiscernibility relation of rough sets are given. Based on these theorems, the algorithms of discovering data dependency are proposed.
An algorithm of query optimization of regular path expression based on DTD is proposed. The concept of extended regular path expression is defined, and is used to reduce the DTD. The concept of entrance-node is defined. Based on the entrance-node notion, two kinds of regular path expression optimizing principles are proposed, named path shorten and path complementing. Using these two kinds
引文
[1] Bray T, Paoli J, Sperberg C M, et al. Extensible Markup Language (XML) 1.0. W3C Recommendation, 1998. http://www. w3. org/TR/REC-xml
[2] Daniela F, Donald K. A Performance Evaluation of Alternative Mapping Schemes for Storing XML Data in a Relational Database. Technical Report 3684, INRIA, March 1999
[3] Meike K, Holger M. XML and Object-Relational Database Systems - Enhancing Structural Mappings Based on Statistics. Selected Papers From the 3rd International Workshop WebDB 2000 on the World Wide Web and Databases, 2000:151-170P
[4] Florescu D, Kossmann D. Storing and Querying XML Data Using an RDBMS. IEEE Data Engineering, 1999, 22(3):27-34P
[5] Ioana M, Daniela F, Donald K. Pushing XML Queries Inside Relational Databases, Inria Rapport de recherch6, No. 4112, 2001
[6] Michael J. Review - Relational Databases for Querying XML Documents: Limitations and Opportunities. ACM SIGMOD Digital Review, 2000
[7] Shanmugasundaram J, Shekita E J, Barr R, et al. Efficiently Publishing Relational Data as XML Documents. Proceedings of VLDB, 2000
[8] Roy G, Jennifer W. Dataguides: Enabling Query Formulation and Optimization in Semistructured Databases. Technical Report, Stanford, 1997
[9] Chan C Y, Felber P, Garofalakis M, et al. Efficient Filtering of XML Documents with XPath Expressions. Technical Report, Bell Labs, June 2001
[10] Sara C, Yaron K, Yakov A. et al. EquiX - A Search and QueryLanguage for XML. JASIST, 2002, 53(6):454-466P
[11] Hyoseop Shin, Minsoo Lee. An Efficient Branch Query Rewriting Algorithm for XML Query Optimization. OTM Conferences (2) 2005: 1629-1639P
[12] McHugh J, Widom J, Abiteboul S, et al. Indexing Semistructured Data. Technical Report, Stanford University, 1998
[13] Felix W. A Survey of Indexing Techniques for Semistructured Documents. Technical Report, University of Munich, 2002
[14] Chan C Y, Garofalakis M, Rastogi R. RE-Tree: An Efficient Index Structure for Regular Expressions. Technical Report, Bell Laboratories, Memorandum, February 2002
[15] Yoon J, Raghavan V, Yenu C. BitCube: A Three Dimensional Bitmap Indexing for XML Documents. The 13th International Conference on Scientific and Statistical Database Management, FairFax, VA, 2001
[16] Haifeng Jiang, Hongjun Lu, Wei Wang, et al. XR-Tree: Indexing XML Data for Efficient Structural Joins. The 19th International Conference on Data Engineering, 2003
[17] 孔令波，唐世渭，杨冬青，王腾蛟，高军．XML数据索引技术．软件学报．2005，16(12)：2063-2079页
[18] 罗道锋，孟小峰，蒋瑜．XML数据扩展前序编码的更新方法．软件学报．2005，16(5)：810-818页
[19] 何震瀛，李建中，王朝坤．一种XML数据库的数据模型．软件学报．2006，17(4)：759-769页
[20] Bourret R. XML and Database. http://www.rpbourret.com/xml/XMLAndDatabase.htm
[21] Quanzhong Li and Bongki Moon. Indexing and Querying XML Data for Regular Path Expressions. Proceedings of the 27th International Conference on Very Large Databases (VLDB'2001), Rome, Italy,??2001:361-370P
[22] Denilson Barbosa, Attila Barta, Alberto O. Mendelzon, George A. Mihaila, Flavio Rizzolo, and Patricia Rodriguez-Guianolli. ToX-the Toronto XML Engine. In Workshop on Information Integration on the Web, 2001:66-73P
[23] J. McHugh, S. Abiteboul, R. Goldman. Lore: A Database Management System for Semistructured Data. ACMSIGMOD Record, 1997, 26(3):54-66P
[24] 罗道锋，蒋瑜，孟小峰．OrientXh：一种有效的XQuery查询代数．软件学报．2004，15(11)：1648-1660页
[25] Liefke H, Suciu D. XMill: An Efficient Compressor for XML Data. Proceedings of SIGMOD, 2000:153-164P
[26] Cheney J. Compressing XML with Multiplexed Hierarchical PPM Models. Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, 2001: 163-172P
[27] 王宏志，李建中，何震瀛．一种压缩XML数据仓库的存储策略．第19届中国数据库学术会议论文集，2002
[28] 陈敏敏，胡蓉，唐常杰．对源于数据库的XML文件的结构制导压缩技术．第19届中国数据库学术会议论文集，2002
[29] Aditya N. Using Hardcoded Hedge Automata for Compressing Structured Documents. Echnical Report, No. TR-IISc-CSA-2002-1, Department of Computer Science and Automation, IISc, July 2002
[30] Levene M, Wood P T. XML Structure Compression. Proceedings of the 2nd International Workshop on the Web Dynamics, 2002
[31] 王腾蛟，高军，杨冬青，唐世渭，刘云峰．面向XPath执行的XML数据流压缩方法．软件学报．2005，16(5)：869-877页
[32] 骆吉洲，李建中．一种有效的关系数据库压缩方法．软件学报．2005，16(2)：205-214页
[33] Tolani P M, Haritsa J R. XGRIND: A Query-Friendly XML Compressor.Proceedings of ICDE, 2002: 225-234P
[34] Min K, Park M J, Chung C W. XPRESS: A Queriable Compression for XML Data. Proc. of the ACM SIGMOD International Conference on Management of Data, June 2003:122-133P
[35] Buneman P, Grohe M, Koch C. Path Queries on Compressed XML. Proceedings of Int. Conference on Very Large Data Bases (VLDB'03), 2003: 41-152P
[36] Buneman P, Choi B, Fan W, et al. Vectorizing and Querying Large XML Repositories. Proceedings of ICDE, 2005:261-272P
[37] Shurug Al-Khalifa, H. V. Jagadish, Jignesh M. Patel, et al. Structural Joins: A Primitive for Efficient XML Query Pattern Matching, the 18th International Conference on Data Engineering (ICDE'02), 2002:141-152P
[38] Park C, Min J, Chung C. Structural Function Inlining Technique for Structurally Recursive XML Queries. Proceedings of 28th VLDB, 2002:83-94P
[39] Shu-Yao Chien, Zografoula Vagena, Donghui Zhang, Vassilis J. Tsotras, Carlo Zaniolo. Efficient Structural Joins on Indexed XML Documents. Proceedings of 28th VLDB, 2002:83-94P
[40] Haifeng Jiang, Hongjun Lu, Wei Wang, Beng Chin Ooi. XR-Tree: Indexing XML Data for Efficient Structural Joins. the 19th International Conference on Data Engineering (ICDE'03), 2003:253-264P
[41] Raghav Kaushik, Rajasekar Krishnamurthy, J. F. Naughton, Raghu Ramakrishnan. On the Integration of Structure Indexes and Inverted Lists. Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, 2004:779-790P
[42] Nan Tang, Jeffrey Xu Yu, Kam-Fai Wong, et al. Accelerating XML Structural Join by Partitioning. DEXA 2005:280-289P
[43] Nan Tang, Jeffrey Xu Yu, Kam-Fai Wong, et al. Fast Structural Join with a Location Function. DASFAA 2006:777-786P
[44] Hongzhi Wang, Wei Wang, Xuemin Lin, et al. Labeling Scheme and Structural Joins for Graph-Structured XML Data. APWeb 2005: 277-289P
[45] Nicolas Bruno, Nick Koudas, Divesh Srivastava. Hoiistic twig joins:optimal XML pattern matching. Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, 2002:310-321P
[46] Haifeng Jiang, Wei Wang, Hongjun Lu, Jeffrey Xu Yu. Holistic twig Joins on Indexed XML Documents. Proceedings of 29th VLDB, 2003:273-284P
[47] Haifeng Jiang, Wei Wang, Hongjun Lu. Efficient Processing of Twig Queries with OR-Predicates. Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, 2004:59-70P
[48] Jiaheng Lu, Ting Chen, Tok Wang Ling. Efficient Processing of Twig Queries with Parent Child Edges. Proceedings of the 2004 ACM CIKM International Conference on Information and Knowledge Management, 2004:533-542P
[49] Hongqiang Wang, Jianzhong Li, Hongzhi Wang. Clustered Absolute Path Index for XML Document: On Efficient Processing of Twig Queries. APWeb Workshops 2006:1-10P
[50] Jiaheng Lu, Tok Wang Ling, Tian Yu, et al. Efficient Processing of Ordered XML Twig Pattern. DEXA 2005:300-309P
[51] 吕建华，王国仁，于戈．XML数据的路径表达式查询优化技术．软件学报．2003，14(9)：1615-1620页
[52] RPE query processing and optimization techniques for XML databases. Source, Journal of Computer Science and Technologyarchive, March 2004,19(2):224-238P
[53] Guoren Wang, Mengchi Liu. Query Processing and Optimization for Regular Path Expressions. CAiSE 2003:30-45P
[54] Dun-Ren Che. Accomplishing Deterministic XML Query Optimization. Journal of Computer Science and Technology, 2005, 20(3): 357-366P
[55] Ning Zhang. XML Query Processing and Optimization. EDBT Workshops 2004, Heraklion, Crete, Greece, 2004:112-120P
[56] Leonid Novak, Alexandre Zamulin. Algebraic Semantics of XML Schema. ADBIS 2005: 209-222P
[57] Wood P T. Minimising Simple XPath Expressions. Proceedings of the 4th WebDB International workshop on the web and database, 2001:13-18P
[58] Ramanan P. Efficient Algorithms for Minimizing Tree Pattern Queries. Proceedings of the 21th ACM SIGMOD International Conference on Management of Data, 2002:299-309P
[59] Miklau G and Suciu D. Containment and Equivalence for a Fragment of XPath. Journal of the ACM, 2004, 51(1):2-45P
[60] Schwentick T. XPath Query Containment. ACM SIGMOD Record, 2004, 33(1):101-109P
[61] A. Y. Halevy. Answering queries using views:A survey. The VLDB Journal, 2001,10(4):270-294P
[62] Wu Y, Patel J M, Jagadish H V. Estimating Answer Sizes for XML Queries. Proceedings of the 8th EDBT International Conference on Data Engineering. 2002:590-608P
[63] Wang Wei, Jiang Haifeng, Lu Hongjun, et al. Containment Join Size Estimation. Proceedings of the 22th ACM SIGMOD International Conference on Management of Data. 2003:145-165P
[64] 王宇, 孟小峰, 王珊. OrientX中的统计信息收集方法研究. 第20届 全国数据库学术会议论文集，计算机科学，2003：94-98页
[65] Yuqing Wu, JigneshM. Patel, H. V. Jagadish. Structural Join Order Selection for XML Query Optimization. In: Proc. 19th Int. Conf. on Data Engineering, 2003
[66] 曲卫民，孙乐，孙玉芳．XML数据查询中值匹配查询代价估计算法．软件学报．2005，16(4)：561-569页
[67] Andrei Arion, Veronique Benzaken, Ioana Manolescu. XML Access Modules: Towards Physical Data Independence in XML Databases. XIME-P 2005, Baltimore, Maryland, USA
[68] D. Beneventano, S. Bergamaschi. Extensional Knowledge for Semantic Query Optimization in a Mediator Based System. Proc. Int'l Workshop on Foundations of Models for Information Integration, Sept. 2001
[69] Hong Su, Elke A. Rundensteiner, Murali Mani. Semantic Query Optimization in an Automata-Algebra Combined XQuery Engine over XML Streams. VLDB 2004:1293-1296P
[70] Marko Smiljanic, Maurice van Keulen, Willem Jonker. Formalizing the XML Schema Matching Problem as a Constraint Optimization Problem. DEXA 2005:333-342P
[71] Xia Yang, Mong Li Lee, Tok Wang Ling, et al. A Semantic Approach to Query Rewriting for Integrated XML Data. ER 2005: 417-432P
[72] Chen ZY, Gehrke J, Korn F. Query optimization in compressed database systems. In: Sellis T, ed. Proc. of the ACM SIGMOD Intl Conf. on the Management of Data. New York: ACM Press, 2001: 271-282P
[73] Chen ZY. Building compressed database system. Ph. D. Thesis. New York: Connell University, 2002
[74] 孟小峰．Web数据管理研究综述．计算机研究与发展．2001，38(4)：385-395页[75] Chawathe S, Garcia M H, Hammer J, et al. The TSIMMIS Project: Integration of Heterogenous Information Sources. Proceedings of the 10th Meeting of the Information Processing Society of Japan, 1994:7-18P
[76] Msrcelo Arenas, Leonid Libkin. A Normal Form for XML Documents. Proceedings of ACM Symposium on Principles of Database Systems(PODS). 2002:85-96P
[77] 张忠平．基于约束的XML数据库模式规范化研究．复旦大学博士学位论文．2004
[78] Schlieder T. Schema-Driven Evaluation of ApproXQL Queries. Technical Report B 02-01, Freie Universitat Berlin, February 2002
[79] Bonifati S C. Comparative Analysis of Five XML Query Languages. ACM SIGMOD Record, 2000, 29(1):68-79P
[80] Abiteboul S, Quass D, McHugh J, et al. The Lorel Query Language for Semistructured Data. International Journal on Digital Libraries, 1997, 1(1):68-88P
[81] Deutsch A, et al. XML-QL: A Query Language for XML. http://www.w3.org/TR/1998/NOTE-xml-ql-19980819/
[82] Don C, Jonathan R, Daiela F. Quilt: An XML Query Language for Heterogeneous Data Sources. Lecture Notes in Computer Science, Springer-Verlag. 2001:199-234P
[83] Don C, James C, Daniela F, et al. XQuery 1.0: An XML Query Language. W3C Working Draft, 2001. http://www.w3.org/TR/xquery
[84] World Wide Web Consortium, XML Path Language (XPath) Version 1.0. W3C Recommendation, Nov. 16, 1999. http://www.w3.org/TR/xpath.xml
[85] Mignet L, Barbosa, D Yeltri. The XML Web: a first study. In proceedings of the twelfth international conference on World??Wide Web, 2003: 500-510
[86] P. Bueman, S. Davidson, G. Hillebrand, and D. Suciu. A query language and optimization techniques for unstructured data. In Proceedings of ACM SIGMOD International Conference on Management of Data, 1996
[87] R. Goldman and J. Widom. Dataguides: Enabling query formulation and optimization in semistructured databases. In Proceedings of the 23rd International Conference on Very Large Data Bases, 1997: 436-445P
[88] R. Goldman and J. Widom. Approximate dataguides. Technical report, Stanford University, 1998
[89] S. Nestorov, S. Abiteboul, and R. Motwani. Inferring structure in semistructured data. In Proceedings of the Workshop on Management of Semistructured Data, 1997
[90] S. Nestorov, S. Abiteboul, and R. Motwani. Extracting schema from semistructured data. In Proceedings of ACM SIGMOD International Conference on Management of Data, Seattle, WA, 1998: 295-306P
[91] Wang Qiuyue, Jeffrey Xu Yu, Huang Jinhui. Approximate Graph Schema Extraction for Semi-structured Data. In proc. Of EDBT 2000, Germany, March 2000
[92] J.R. Quinlan. Induction on decision trees. Machine Learning, 1986:81-106P
[93] L.A. Zadeh. Fuzzy sets. Information and Control, 1965: 407-428P
[94] Cezary Z. Janikow. Fuzzy decision trees: Issues and methods. IEEE Transactions on Systems, Man, and Cybernetics, 1998,28(1): 1-14P
[95] L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth & Brooks Advanced Books and Software, Pacific Grove, CA, 1984
[96] Pawlak Z. Rough Sets. International Journal of Information and Computer Science. 1982, 11(5)
[97] Millist W. Vincent, Jixue Liu, and Chengfei Liu. Strong functional dependenmcies and their applicatiopn to normal forms in XML. ACM Trans. Database Syst. 2004, 29(3):445-462 P
[98] Millist W. Vincent, Jixue Liu, and Chengfei Liu. Multivalued Dependencies and a 4NF for XML. CAiSE 2003:14-29P
[99] Millist W. Vincent, Jixue Liu: Functional Dependencies for XML. APWeb 2003:22-34P
[100] Millist W. Vincent, Jixue Liu: Multivalued Dependencies in XML. BNCOD 2003:4-18P
[101] Jixue Liu, Millist W. Vincent, Chengfei Liu, Mukesh K. Mohania: Checking Multivalued Dependencies in XML. APWeb 2005:320-332P
[102] Millist W. Vincent, Jixue Liu: Checking Functional Dependency Satisfaction in XML. XSym 2005:4-17P
[103] P. Buneman, S. Davidson, W. Fan, and C. Hara. Reasoning about keys for xml. In International Workshop on Database Programming Languages, 2001
[104] P. Buneman, W. Fan, and S. Weinstein. Path constraints on structured and semistructured data. In Proc. ACM PODS Conference, 1998:129-138P
[105] W. Fan and J. Simeon. Integrity constraints for xml. In Proc. ACM PODS Conference, 2000:23-24P
[106] 张忠平，曹顺良，李荣，朱扬勇．基于约束的XML模式规范化研究．计算机科学．2003，30(增刊)：35-40页
[107] 吴永辉．用于XML模式和DTD规范化设计的层次模式设计．软件学报．2004，15(7)：1099-1106页
[108] 谈子敬，施伯乐．函数依赖和规范化在关系和XML间的传播．软件学报．2005，16(4)：533-539页[109] 王国胤编著. Rough 集理论与知识获取.西安:西安交通大学出版社, 2001
[110] Berkeley DB XML2. 2. http://www. sleepycat. com/products/bdbxml. html
[111] Schmidt A, Waas F, Kersten M, et al. The XML Benchmark Project. Technical Report, INSR0103, 2001
[112] Beech D, Malhotra A, and Rys M. A Formal DataModel and Algebra for XML. http://www-db. standford. edu/dbseminar/Archive/FallY99/malhot ra- stld001.htm
[113] Christophides V, Cluet S, Simeon J. On Wrappping Query Languages and Efficient XML Integration. Proceedigs of the 19th ACM SIGMOD International Conference on Management of Data. 2000:14-19P
[114] Fermandez M, Simeon J, Wadler P. An Algebra for XML Query. Proceedings of the 20th FSTTCS International Conference on Foundation of Sofeware Technology and Theoretical Computer Science, 2000:11-45P
[115] Galanis L, Viglas E, DeWitt D J, et al. Following the Paths of XML Data: An Algebraic framework for XML Query Evaluation. http://www. cs. wisc, edu/niagara/
[116] Buneman P, Fernandez M, Suciu D. UnQL: A Query Language and Algebra for Semistructred Data Based on Structural Recursion. The VLDB Journal. 2000, 9(1):76-110P
[117] Beeri C, Tazban Y. SAL: An Algebra for Semistructured Data and XML. The second ACM SIGMOD Workshop on the web and Databases, 1999:37-42P
[118] Jagadish H, Lakshmanan L, Srivastava D. TAX: A Tree Algebra for XML. The 8th International Workshop on Database Programming Languages, 2001:149-164P
[119] Hui Zhang. XML Query Processing and Optimization. Ph. D. Thesis, Waterloo, Ontario, Canada: Waterloo University, 2003
[120] Balakrishna R. Iyer and David Wilhite. Data compression support in database Proceedings of VLDB, 1994:275-286P
[121] Jonathan Goldstein, Raghu Ramakrishnan, and Uri Shaft. Compressing relations and indexes. Proceedings of ICDE, 1998:370-379P
[122] Westmann T, Kossmann, Helmer S, and Moerkotte G. The implementation and performance of compressed database. SIGMOD Record29(3), 2000
[123] Oasis. eXtensible Access Control Markup Language (XACML). http://www.oasis-open.org/committees/xcaml
[124] S. Hada and M. Kudo. XML access control language: Provisional authorization for XML documents. http://www.trl.ibm.com/projects/xml/xacl/xacl-spec.html
[125] E. Damiani, S. di Vimercati, S. Paraboschi, and P. Samarati. A fine-grained access control system for XML documents. TISSEC, 2002, 5(2):169-202P
[126] 李斓，何永忠，冯登国．面向XML文档的细粒度强制访问控制模型．软件学报．2004，15(10)：1528-1537页
[127] R. Sandhu, E. J. Coyne, H. L. Feinstein. Role based access control models. IEEE Computer, 1996, 29(2):38-47P
[128] W. Fan, C-Y. Chan, and M. Garofalakis. Secure XML Querying with Security Views. In SIGMOD, 2004
[129] Irini Fundulaki, Maarten Marx. Specifying Access Control Policies for XML Documents with XPath. In SACMAT, 2004
[130] Lan Li, Xinghao Jiang, and Jianhua Li. Enforce Mandatory Access Control Policy on XML Documents. ICICS 2005:336-349P
[2] Daniela F, Donald K. A Performance Evaluation of Alternative Mapping Schemes for Storing XML Data in a Relational Database. Technical Report 3684, INRIA, March 1999
[3] Meike K, Holger M. XML and Object-Relational Database Systems - Enhancing Structural Mappings Based on Statistics. Selected Papers From the 3rd International Workshop WebDB 2000 on the World Wide Web and Databases, 2000:151-170P
[4] Florescu D, Kossmann D. Storing and Querying XML Data Using an RDBMS. IEEE Data Engineering, 1999, 22(3):27-34P
[5] Ioana M, Daniela F, Donald K. Pushing XML Queries Inside Relational Databases, Inria Rapport de recherch6, No. 4112, 2001
[6] Michael J. Review - Relational Databases for Querying XML Documents: Limitations and Opportunities. ACM SIGMOD Digital Review, 2000
[7] Shanmugasundaram J, Shekita E J, Barr R, et al. Efficiently Publishing Relational Data as XML Documents. Proceedings of VLDB, 2000
[8] Roy G, Jennifer W. Dataguides: Enabling Query Formulation and Optimization in Semistructured Databases. Technical Report, Stanford, 1997
[9] Chan C Y, Felber P, Garofalakis M, et al. Efficient Filtering of XML Documents with XPath Expressions. Technical Report, Bell Labs, June 2001
[10] Sara C, Yaron K, Yakov A. et al. EquiX - A Search and QueryLanguage for XML. JASIST, 2002, 53(6):454-466P
[11] Hyoseop Shin, Minsoo Lee. An Efficient Branch Query Rewriting Algorithm for XML Query Optimization. OTM Conferences (2) 2005: 1629-1639P
[12] McHugh J, Widom J, Abiteboul S, et al. Indexing Semistructured Data. Technical Report, Stanford University, 1998
[13] Felix W. A Survey of Indexing Techniques for Semistructured Documents. Technical Report, University of Munich, 2002
[14] Chan C Y, Garofalakis M, Rastogi R. RE-Tree: An Efficient Index Structure for Regular Expressions. Technical Report, Bell Laboratories, Memorandum, February 2002
[15] Yoon J, Raghavan V, Yenu C. BitCube: A Three Dimensional Bitmap Indexing for XML Documents. The 13th International Conference on Scientific and Statistical Database Management, FairFax, VA, 2001
[16] Haifeng Jiang, Hongjun Lu, Wei Wang, et al. XR-Tree: Indexing XML Data for Efficient Structural Joins. The 19th International Conference on Data Engineering, 2003
[17] 孔令波，唐世渭，杨冬青，王腾蛟，高军．XML数据索引技术．软件学报．2005，16(12)：2063-2079页
[18] 罗道锋，孟小峰，蒋瑜．XML数据扩展前序编码的更新方法．软件学报．2005，16(5)：810-818页
[19] 何震瀛，李建中，王朝坤．一种XML数据库的数据模型．软件学报．2006，17(4)：759-769页
[20] Bourret R. XML and Database. http://www.rpbourret.com/xml/XMLAndDatabase.htm
[21] Quanzhong Li and Bongki Moon. Indexing and Querying XML Data for Regular Path Expressions. Proceedings of the 27th International Conference on Very Large Databases (VLDB'2001), Rome, Italy,??2001:361-370P
[22] Denilson Barbosa, Attila Barta, Alberto O. Mendelzon, George A. Mihaila, Flavio Rizzolo, and Patricia Rodriguez-Guianolli. ToX-the Toronto XML Engine. In Workshop on Information Integration on the Web, 2001:66-73P
[23] J. McHugh, S. Abiteboul, R. Goldman. Lore: A Database Management System for Semistructured Data. ACMSIGMOD Record, 1997, 26(3):54-66P
[24] 罗道锋，蒋瑜，孟小峰．OrientXh：一种有效的XQuery查询代数．软件学报．2004，15(11)：1648-1660页
[25] Liefke H, Suciu D. XMill: An Efficient Compressor for XML Data. Proceedings of SIGMOD, 2000:153-164P
[26] Cheney J. Compressing XML with Multiplexed Hierarchical PPM Models. Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, 2001: 163-172P
[27] 王宏志，李建中，何震瀛．一种压缩XML数据仓库的存储策略．第19届中国数据库学术会议论文集，2002
[28] 陈敏敏，胡蓉，唐常杰．对源于数据库的XML文件的结构制导压缩技术．第19届中国数据库学术会议论文集，2002
[29] Aditya N. Using Hardcoded Hedge Automata for Compressing Structured Documents. Echnical Report, No. TR-IISc-CSA-2002-1, Department of Computer Science and Automation, IISc, July 2002
[30] Levene M, Wood P T. XML Structure Compression. Proceedings of the 2nd International Workshop on the Web Dynamics, 2002
[31] 王腾蛟，高军，杨冬青，唐世渭，刘云峰．面向XPath执行的XML数据流压缩方法．软件学报．2005，16(5)：869-877页
[32] 骆吉洲，李建中．一种有效的关系数据库压缩方法．软件学报．2005，16(2)：205-214页
[33] Tolani P M, Haritsa J R. XGRIND: A Query-Friendly XML Compressor.Proceedings of ICDE, 2002: 225-234P
[34] Min K, Park M J, Chung C W. XPRESS: A Queriable Compression for XML Data. Proc. of the ACM SIGMOD International Conference on Management of Data, June 2003:122-133P
[35] Buneman P, Grohe M, Koch C. Path Queries on Compressed XML. Proceedings of Int. Conference on Very Large Data Bases (VLDB'03), 2003: 41-152P
[36] Buneman P, Choi B, Fan W, et al. Vectorizing and Querying Large XML Repositories. Proceedings of ICDE, 2005:261-272P
[37] Shurug Al-Khalifa, H. V. Jagadish, Jignesh M. Patel, et al. Structural Joins: A Primitive for Efficient XML Query Pattern Matching, the 18th International Conference on Data Engineering (ICDE'02), 2002:141-152P
[38] Park C, Min J, Chung C. Structural Function Inlining Technique for Structurally Recursive XML Queries. Proceedings of 28th VLDB, 2002:83-94P
[39] Shu-Yao Chien, Zografoula Vagena, Donghui Zhang, Vassilis J. Tsotras, Carlo Zaniolo. Efficient Structural Joins on Indexed XML Documents. Proceedings of 28th VLDB, 2002:83-94P
[40] Haifeng Jiang, Hongjun Lu, Wei Wang, Beng Chin Ooi. XR-Tree: Indexing XML Data for Efficient Structural Joins. the 19th International Conference on Data Engineering (ICDE'03), 2003:253-264P
[41] Raghav Kaushik, Rajasekar Krishnamurthy, J. F. Naughton, Raghu Ramakrishnan. On the Integration of Structure Indexes and Inverted Lists. Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, 2004:779-790P
[42] Nan Tang, Jeffrey Xu Yu, Kam-Fai Wong, et al. Accelerating XML Structural Join by Partitioning. DEXA 2005:280-289P
[43] Nan Tang, Jeffrey Xu Yu, Kam-Fai Wong, et al. Fast Structural Join with a Location Function. DASFAA 2006:777-786P
[44] Hongzhi Wang, Wei Wang, Xuemin Lin, et al. Labeling Scheme and Structural Joins for Graph-Structured XML Data. APWeb 2005: 277-289P
[45] Nicolas Bruno, Nick Koudas, Divesh Srivastava. Hoiistic twig joins:optimal XML pattern matching. Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, 2002:310-321P
[46] Haifeng Jiang, Wei Wang, Hongjun Lu, Jeffrey Xu Yu. Holistic twig Joins on Indexed XML Documents. Proceedings of 29th VLDB, 2003:273-284P
[47] Haifeng Jiang, Wei Wang, Hongjun Lu. Efficient Processing of Twig Queries with OR-Predicates. Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, 2004:59-70P
[48] Jiaheng Lu, Ting Chen, Tok Wang Ling. Efficient Processing of Twig Queries with Parent Child Edges. Proceedings of the 2004 ACM CIKM International Conference on Information and Knowledge Management, 2004:533-542P
[49] Hongqiang Wang, Jianzhong Li, Hongzhi Wang. Clustered Absolute Path Index for XML Document: On Efficient Processing of Twig Queries. APWeb Workshops 2006:1-10P
[50] Jiaheng Lu, Tok Wang Ling, Tian Yu, et al. Efficient Processing of Ordered XML Twig Pattern. DEXA 2005:300-309P
[51] 吕建华，王国仁，于戈．XML数据的路径表达式查询优化技术．软件学报．2003，14(9)：1615-1620页
[52] RPE query processing and optimization techniques for XML databases. Source, Journal of Computer Science and Technologyarchive, March 2004,19(2):224-238P
[53] Guoren Wang, Mengchi Liu. Query Processing and Optimization for Regular Path Expressions. CAiSE 2003:30-45P
[54] Dun-Ren Che. Accomplishing Deterministic XML Query Optimization. Journal of Computer Science and Technology, 2005, 20(3): 357-366P
[55] Ning Zhang. XML Query Processing and Optimization. EDBT Workshops 2004, Heraklion, Crete, Greece, 2004:112-120P
[56] Leonid Novak, Alexandre Zamulin. Algebraic Semantics of XML Schema. ADBIS 2005: 209-222P
[57] Wood P T. Minimising Simple XPath Expressions. Proceedings of the 4th WebDB International workshop on the web and database, 2001:13-18P
[58] Ramanan P. Efficient Algorithms for Minimizing Tree Pattern Queries. Proceedings of the 21th ACM SIGMOD International Conference on Management of Data, 2002:299-309P
[59] Miklau G and Suciu D. Containment and Equivalence for a Fragment of XPath. Journal of the ACM, 2004, 51(1):2-45P
[60] Schwentick T. XPath Query Containment. ACM SIGMOD Record, 2004, 33(1):101-109P
[61] A. Y. Halevy. Answering queries using views:A survey. The VLDB Journal, 2001,10(4):270-294P
[62] Wu Y, Patel J M, Jagadish H V. Estimating Answer Sizes for XML Queries. Proceedings of the 8th EDBT International Conference on Data Engineering. 2002:590-608P
[63] Wang Wei, Jiang Haifeng, Lu Hongjun, et al. Containment Join Size Estimation. Proceedings of the 22th ACM SIGMOD International Conference on Management of Data. 2003:145-165P
[64] 王宇, 孟小峰, 王珊. OrientX中的统计信息收集方法研究. 第20届 全国数据库学术会议论文集，计算机科学，2003：94-98页
[65] Yuqing Wu, JigneshM. Patel, H. V. Jagadish. Structural Join Order Selection for XML Query Optimization. In: Proc. 19th Int. Conf. on Data Engineering, 2003
[66] 曲卫民，孙乐，孙玉芳．XML数据查询中值匹配查询代价估计算法．软件学报．2005，16(4)：561-569页
[67] Andrei Arion, Veronique Benzaken, Ioana Manolescu. XML Access Modules: Towards Physical Data Independence in XML Databases. XIME-P 2005, Baltimore, Maryland, USA
[68] D. Beneventano, S. Bergamaschi. Extensional Knowledge for Semantic Query Optimization in a Mediator Based System. Proc. Int'l Workshop on Foundations of Models for Information Integration, Sept. 2001
[69] Hong Su, Elke A. Rundensteiner, Murali Mani. Semantic Query Optimization in an Automata-Algebra Combined XQuery Engine over XML Streams. VLDB 2004:1293-1296P
[70] Marko Smiljanic, Maurice van Keulen, Willem Jonker. Formalizing the XML Schema Matching Problem as a Constraint Optimization Problem. DEXA 2005:333-342P
[71] Xia Yang, Mong Li Lee, Tok Wang Ling, et al. A Semantic Approach to Query Rewriting for Integrated XML Data. ER 2005: 417-432P
[72] Chen ZY, Gehrke J, Korn F. Query optimization in compressed database systems. In: Sellis T, ed. Proc. of the ACM SIGMOD Intl Conf. on the Management of Data. New York: ACM Press, 2001: 271-282P
[73] Chen ZY. Building compressed database system. Ph. D. Thesis. New York: Connell University, 2002
[74] 孟小峰．Web数据管理研究综述．计算机研究与发展．2001，38(4)：385-395页[75] Chawathe S, Garcia M H, Hammer J, et al. The TSIMMIS Project: Integration of Heterogenous Information Sources. Proceedings of the 10th Meeting of the Information Processing Society of Japan, 1994:7-18P
[76] Msrcelo Arenas, Leonid Libkin. A Normal Form for XML Documents. Proceedings of ACM Symposium on Principles of Database Systems(PODS). 2002:85-96P
[77] 张忠平．基于约束的XML数据库模式规范化研究．复旦大学博士学位论文．2004
[78] Schlieder T. Schema-Driven Evaluation of ApproXQL Queries. Technical Report B 02-01, Freie Universitat Berlin, February 2002
[79] Bonifati S C. Comparative Analysis of Five XML Query Languages. ACM SIGMOD Record, 2000, 29(1):68-79P
[80] Abiteboul S, Quass D, McHugh J, et al. The Lorel Query Language for Semistructured Data. International Journal on Digital Libraries, 1997, 1(1):68-88P
[81] Deutsch A, et al. XML-QL: A Query Language for XML. http://www.w3.org/TR/1998/NOTE-xml-ql-19980819/
[82] Don C, Jonathan R, Daiela F. Quilt: An XML Query Language for Heterogeneous Data Sources. Lecture Notes in Computer Science, Springer-Verlag. 2001:199-234P
[83] Don C, James C, Daniela F, et al. XQuery 1.0: An XML Query Language. W3C Working Draft, 2001. http://www.w3.org/TR/xquery
[84] World Wide Web Consortium, XML Path Language (XPath) Version 1.0. W3C Recommendation, Nov. 16, 1999. http://www.w3.org/TR/xpath.xml
[85] Mignet L, Barbosa, D Yeltri. The XML Web: a first study. In proceedings of the twelfth international conference on World??Wide Web, 2003: 500-510
[86] P. Bueman, S. Davidson, G. Hillebrand, and D. Suciu. A query language and optimization techniques for unstructured data. In Proceedings of ACM SIGMOD International Conference on Management of Data, 1996
[87] R. Goldman and J. Widom. Dataguides: Enabling query formulation and optimization in semistructured databases. In Proceedings of the 23rd International Conference on Very Large Data Bases, 1997: 436-445P
[88] R. Goldman and J. Widom. Approximate dataguides. Technical report, Stanford University, 1998
[89] S. Nestorov, S. Abiteboul, and R. Motwani. Inferring structure in semistructured data. In Proceedings of the Workshop on Management of Semistructured Data, 1997
[90] S. Nestorov, S. Abiteboul, and R. Motwani. Extracting schema from semistructured data. In Proceedings of ACM SIGMOD International Conference on Management of Data, Seattle, WA, 1998: 295-306P
[91] Wang Qiuyue, Jeffrey Xu Yu, Huang Jinhui. Approximate Graph Schema Extraction for Semi-structured Data. In proc. Of EDBT 2000, Germany, March 2000
[92] J.R. Quinlan. Induction on decision trees. Machine Learning, 1986:81-106P
[93] L.A. Zadeh. Fuzzy sets. Information and Control, 1965: 407-428P
[94] Cezary Z. Janikow. Fuzzy decision trees: Issues and methods. IEEE Transactions on Systems, Man, and Cybernetics, 1998,28(1): 1-14P
[95] L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth & Brooks Advanced Books and Software, Pacific Grove, CA, 1984
[96] Pawlak Z. Rough Sets. International Journal of Information and Computer Science. 1982, 11(5)
[97] Millist W. Vincent, Jixue Liu, and Chengfei Liu. Strong functional dependenmcies and their applicatiopn to normal forms in XML. ACM Trans. Database Syst. 2004, 29(3):445-462 P
[98] Millist W. Vincent, Jixue Liu, and Chengfei Liu. Multivalued Dependencies and a 4NF for XML. CAiSE 2003:14-29P
[99] Millist W. Vincent, Jixue Liu: Functional Dependencies for XML. APWeb 2003:22-34P
[100] Millist W. Vincent, Jixue Liu: Multivalued Dependencies in XML. BNCOD 2003:4-18P
[101] Jixue Liu, Millist W. Vincent, Chengfei Liu, Mukesh K. Mohania: Checking Multivalued Dependencies in XML. APWeb 2005:320-332P
[102] Millist W. Vincent, Jixue Liu: Checking Functional Dependency Satisfaction in XML. XSym 2005:4-17P
[103] P. Buneman, S. Davidson, W. Fan, and C. Hara. Reasoning about keys for xml. In International Workshop on Database Programming Languages, 2001
[104] P. Buneman, W. Fan, and S. Weinstein. Path constraints on structured and semistructured data. In Proc. ACM PODS Conference, 1998:129-138P
[105] W. Fan and J. Simeon. Integrity constraints for xml. In Proc. ACM PODS Conference, 2000:23-24P
[106] 张忠平，曹顺良，李荣，朱扬勇．基于约束的XML模式规范化研究．计算机科学．2003，30(增刊)：35-40页
[107] 吴永辉．用于XML模式和DTD规范化设计的层次模式设计．软件学报．2004，15(7)：1099-1106页
[108] 谈子敬，施伯乐．函数依赖和规范化在关系和XML间的传播．软件学报．2005，16(4)：533-539页[109] 王国胤编著. Rough 集理论与知识获取.西安:西安交通大学出版社, 2001
[110] Berkeley DB XML2. 2. http://www. sleepycat. com/products/bdbxml. html
[111] Schmidt A, Waas F, Kersten M, et al. The XML Benchmark Project. Technical Report, INSR0103, 2001
[112] Beech D, Malhotra A, and Rys M. A Formal DataModel and Algebra for XML. http://www-db. standford. edu/dbseminar/Archive/FallY99/malhot ra- stld001.htm
[113] Christophides V, Cluet S, Simeon J. On Wrappping Query Languages and Efficient XML Integration. Proceedigs of the 19th ACM SIGMOD International Conference on Management of Data. 2000:14-19P
[114] Fermandez M, Simeon J, Wadler P. An Algebra for XML Query. Proceedings of the 20th FSTTCS International Conference on Foundation of Sofeware Technology and Theoretical Computer Science, 2000:11-45P
[115] Galanis L, Viglas E, DeWitt D J, et al. Following the Paths of XML Data: An Algebraic framework for XML Query Evaluation. http://www. cs. wisc, edu/niagara/
[116] Buneman P, Fernandez M, Suciu D. UnQL: A Query Language and Algebra for Semistructred Data Based on Structural Recursion. The VLDB Journal. 2000, 9(1):76-110P
[117] Beeri C, Tazban Y. SAL: An Algebra for Semistructured Data and XML. The second ACM SIGMOD Workshop on the web and Databases, 1999:37-42P
[118] Jagadish H, Lakshmanan L, Srivastava D. TAX: A Tree Algebra for XML. The 8th International Workshop on Database Programming Languages, 2001:149-164P
[119] Hui Zhang. XML Query Processing and Optimization. Ph. D. Thesis, Waterloo, Ontario, Canada: Waterloo University, 2003
[120] Balakrishna R. Iyer and David Wilhite. Data compression support in database Proceedings of VLDB, 1994:275-286P
[121] Jonathan Goldstein, Raghu Ramakrishnan, and Uri Shaft. Compressing relations and indexes. Proceedings of ICDE, 1998:370-379P
[122] Westmann T, Kossmann, Helmer S, and Moerkotte G. The implementation and performance of compressed database. SIGMOD Record29(3), 2000
[123] Oasis. eXtensible Access Control Markup Language (XACML). http://www.oasis-open.org/committees/xcaml
[124] S. Hada and M. Kudo. XML access control language: Provisional authorization for XML documents. http://www.trl.ibm.com/projects/xml/xacl/xacl-spec.html
[125] E. Damiani, S. di Vimercati, S. Paraboschi, and P. Samarati. A fine-grained access control system for XML documents. TISSEC, 2002, 5(2):169-202P
[126] 李斓，何永忠，冯登国．面向XML文档的细粒度强制访问控制模型．软件学报．2004，15(10)：1528-1537页
[127] R. Sandhu, E. J. Coyne, H. L. Feinstein. Role based access control models. IEEE Computer, 1996, 29(2):38-47P
[128] W. Fan, C-Y. Chan, and M. Garofalakis. Secure XML Querying with Security Views. In SIGMOD, 2004
[129] Irini Fundulaki, Maarten Marx. Specifying Access Control Policies for XML Documents with XPath. In SACMAT, 2004
[130] Lan Li, Xinghao Jiang, and Jianhua Li. Enforce Mandatory Access Control Policy on XML Documents. ICICS 2005:336-349P