Active XML数据管理基础问题研究
|
摘要
Active XML(Active eXtensible Markup Language)的提出,能够有效的解决当前分布式数据管理中存在的数据源异构性、交互性及自主性问题,为分布式Web数据管理提供了新的发展方向。AXML文档是一部分数据直接给出,另一部分数据以Web服务调用方式隐含给出的XML文档,通过触发这这些服务调用,可以获得其包含的隐含信息来扩充文档内容。AXML模式定义了符合约束条件的AXML文档集合。
AXML数据管理需要考虑如下基础问题:(1)AXML数据交换是AXML的主要应用方式,而数据交换之前必须判定给定AXML文档通过触发其包含的服务调用是否能够转换成为符合目标模式要求的文档实例,从而引出了文档重写问题;(2)在某些情况下,还要考虑符合给定源模式的全部文档是否能够重写为目标模式实例,这就需要考虑模式之间的兼容性,该问题为模式重写问题;(3)AXML数据交换过程中,通常以查询方式来实现数据请求,而查询可满足性判定是执行给定查询的前提条件,通过判定给定查询的可满足性,可以过滤掉一部分不可满足查询,从而提高查询的执行效率;(4)保证AXML文档为有效文档是AXML数据管理的关键,也是AXML数据交换、文档查询的先决条件。
本文基于树自动机理论,对AXML数据交换中存在的AXML文档重写和模式重写、AXML文档查询可满足性、AXML文档有效性检验问题进行了深入研究,目的是对上述问题提出有效的解决方法,从而让AXML能够更好的服务于分布式数据管理。
第一,研究了AXML文档重写和模式重写问题。AXML文档重写问题是指判定给定文档通过触发其包含的服务调用是否能够将其转换成为符合目标模式的文档实例。AXML文档重写问题分为可能重写和安全重写,AXML文档可能重写是判定给定文档是否能够重写为目标模式的某一文档实例;AXML文档安全重写是判定给定文档的全部可生成文档是否能够重写为符合目标模式的文档实例。AXML模式重写问题是指判定符合给定源模式的全部文档是否能够重写为目标模式实例。首先,基于传统树自动机理论,定义了用于抽象描述AXML文档树的ADTA机(AXML DocumentTree Automata),基于ADTA机,给出了多项式时间复杂度的AXML文档可能重写判定算法,给出了算法的正确性证明;在ADTA机的基础上,定义了ADTA机补自动机,提出了多项式时间复杂度的AXML文档安全重写判定算法,给出了算法的正确性证明;然后,定义了用于描述AXML模式的ASTAr机(AXML Schema Tree Automata for Rewriting),给出了ASTAr机构造算法,ASTAr机定义了所有符合给定AXML模式约束的AXML文档集合;最后,通过分析AXML模式包含与模式重写的关系,基于ASTAr机,提出了多项式时间复杂度的AXML模式重写判定算法,分析了算法的正确性和有效性。
第二,研究了模式约束下的AXML文档树模式查询可满足性问题。AXML文档查询可满足性问题是指判定符合给定模式约束的AXML文档是否满足给定查询表达式。首先,给出了AXML文档查询可满足性的形式化定义;然后,定义了用于抽象AXML模式的ASTAq机(AXML SchemaTree Automata for Queries),用于描述符合给定AXML模式约束的文档集合,定义了抽象树模式查询的TPQA机(Tree Pattern Query Automata),TPQA机描述了包含满足给定树模式查询表达式路径的文档集合;最后,基于ASTAq机和TPQA机,针对XPath树模式查询片段{“/,//,[ ]”},提出了一种多项式时间的AXML文档查询可满足性检验算法,分析了算法的正确性和有效性。
第三,研究了AXML文档有效性检验问题。AXML文档有效性检验问题是指给定AXML文档及其服务调用规范,检验文档是否符合目标模式。定义了用于抽象AXML模式的ASTAv机(AXML Schema Tree Automata forValidation),该树自动机描述符合目标模式约束的文档集合,能够完成对给定文档当前状态的有效性检验;基于ASTAv机,通过分析服务规范与目标模式之间的关系,提出了一种多项式时间的AXML文档有效性检验算法,分析了算法的正确性和有效性。
The presentation of Active XML(AXML for short) addresses the problems ofheterogeneity, interoperability and autonomy occurring in data management at thescale of the Web and becomes a new powerful tool for distributed data management.An AXML document is an XML document where some of the data is given explicitlywhile other parts are defined only intentionally by means of embedded calls to Webservices. When one of these calls is invoked, its results will be returned to enrich theoriginal document.
The problem of AXML data management consists of the following problems:(1)AXML Data exchange is the main application and the sender must decide whetherthe given AXML document can be rewritten into a new one conforming to the gargetschema by invoking the embedded service calls, which introduced schema rewriting;(2)The applications sometimes may consider whether all the documents conformingto the original schema can be rewritten to the target schema, named schema rewrit-ing; (3)In AXML data exchange, applications often ask data in querying manner andsatisfiability is the first condition before executing the given query. After deciding thesatisfiability of querying AXML documents, the unsatisfied ones will be refused andimprove the efficiency of queries. (4)Validation of AXML documents is the key ofAXML data management and the first condition of AXML data exchange and query-ing documents.
Based on tree automata theory, document rewriting and schema rewriting, sat-isfiability of querying documents and validation of documents that are studied in thethesis. The goal of this thesis is to propose efficient algorithms to address these prob-lems and make AXML to be suitable for data management of the Web.
First, problems of AXML document rewriting and schema rewriting are studied.AXML document rewriting is to decide whether the given document can be translatedto the new one conforming the garget schema by invoking some service calls embed-ded in it. AXML document rewriting contains two types: possible rewriting and saferewriting. The former is to decide whether the given document can be rewritten intoanother one conforming to the target schema; the latter is to decide whether the set of produced documents from the given AXML document can be rewritten to the docu-ments conforming to the garget schema. Schema rewriting is to decide whether all thedocuments conforming to the given AXML schema can be translated to the new onesof the target schema. Firstly, the AXML Document Tree Automata (ADTA) used torepresent AXML documents is defined, together with the building algorithm. Basedon ADTA and the defined complement of ADTA, both of algorithms, performed inpolynomial time, for deciding AXML document possible rewriting and safe rewritingare presented and the correction of them are analyzed. Secondly, the AXML SchemaTree Automata for rewriting (ASTAr) used to represent AXML schemas is also de-fined, together with the building algorithm is presented. Finally, based on ASTAr, analgorithm for deciding AXML schema rewriting is proposed which is performed inpolynomial time by analyzing the relationship between the AXML schema contain-ment and schema rewriting; the correction and efficiency are also given.
Second, problem of satisfiability of querying AXML documents conforming toa given AXML schema is studied. For the efficient evaluation of a query over anAXML document, one should check whether there exists an (A)XML document ob-tained from the original one by invoking some Web services, on which the queryhas a non-empty answer. firstly, the formal definition of satisfiability of queryingAXML documents is defined. Then, a new tree automaton, named AXML SchemaTree Automata for Queries (ASTAq), is defined which can efficiently represent the setof AXML documents conforming to the given schema; a TPQA (Tree Pattern QueryAutomaton) is also defined which can represent the document set of satisfying querypathes of the given tree pattern query. Finally, based on ASTAq and TPQA, an al-gorithm for checking satisfiability of tree pattern queries for AXML documents thatruns polynomial time is proposed and experiments were made to verify the utility ofsatisfiability checking.
Third, the problem of validating AXML documents is studied. Validation ofAXML document is to check whether a given AXML document with service callsspecification conforms the target schema. A new tree automaton, named AXMLSchema Tree Automaton for validation (ASTAv), is defined which can efficientlyrepresent the set of AXML documents conforming to the given schema and checkthe validation of the current state of an AXML document. Based on ASTAv, an al-gorithm is proposed for checking AXML validation performing in polynomial time through analyzing the relationship between the service calls specification and the tar-get schema. Finally, the experiment results show that our algorithm gives rise to anefficient validation method for AXML documents.
AXML数据管理需要考虑如下基础问题:(1)AXML数据交换是AXML的主要应用方式,而数据交换之前必须判定给定AXML文档通过触发其包含的服务调用是否能够转换成为符合目标模式要求的文档实例,从而引出了文档重写问题;(2)在某些情况下,还要考虑符合给定源模式的全部文档是否能够重写为目标模式实例,这就需要考虑模式之间的兼容性,该问题为模式重写问题;(3)AXML数据交换过程中,通常以查询方式来实现数据请求,而查询可满足性判定是执行给定查询的前提条件,通过判定给定查询的可满足性,可以过滤掉一部分不可满足查询,从而提高查询的执行效率;(4)保证AXML文档为有效文档是AXML数据管理的关键,也是AXML数据交换、文档查询的先决条件。
本文基于树自动机理论,对AXML数据交换中存在的AXML文档重写和模式重写、AXML文档查询可满足性、AXML文档有效性检验问题进行了深入研究,目的是对上述问题提出有效的解决方法,从而让AXML能够更好的服务于分布式数据管理。
第一,研究了AXML文档重写和模式重写问题。AXML文档重写问题是指判定给定文档通过触发其包含的服务调用是否能够将其转换成为符合目标模式的文档实例。AXML文档重写问题分为可能重写和安全重写,AXML文档可能重写是判定给定文档是否能够重写为目标模式的某一文档实例;AXML文档安全重写是判定给定文档的全部可生成文档是否能够重写为符合目标模式的文档实例。AXML模式重写问题是指判定符合给定源模式的全部文档是否能够重写为目标模式实例。首先,基于传统树自动机理论,定义了用于抽象描述AXML文档树的ADTA机(AXML DocumentTree Automata),基于ADTA机,给出了多项式时间复杂度的AXML文档可能重写判定算法,给出了算法的正确性证明;在ADTA机的基础上,定义了ADTA机补自动机,提出了多项式时间复杂度的AXML文档安全重写判定算法,给出了算法的正确性证明;然后,定义了用于描述AXML模式的ASTAr机(AXML Schema Tree Automata for Rewriting),给出了ASTAr机构造算法,ASTAr机定义了所有符合给定AXML模式约束的AXML文档集合;最后,通过分析AXML模式包含与模式重写的关系,基于ASTAr机,提出了多项式时间复杂度的AXML模式重写判定算法,分析了算法的正确性和有效性。
第二,研究了模式约束下的AXML文档树模式查询可满足性问题。AXML文档查询可满足性问题是指判定符合给定模式约束的AXML文档是否满足给定查询表达式。首先,给出了AXML文档查询可满足性的形式化定义;然后,定义了用于抽象AXML模式的ASTAq机(AXML SchemaTree Automata for Queries),用于描述符合给定AXML模式约束的文档集合,定义了抽象树模式查询的TPQA机(Tree Pattern Query Automata),TPQA机描述了包含满足给定树模式查询表达式路径的文档集合;最后,基于ASTAq机和TPQA机,针对XPath树模式查询片段{“/,//,[ ]”},提出了一种多项式时间的AXML文档查询可满足性检验算法,分析了算法的正确性和有效性。
第三,研究了AXML文档有效性检验问题。AXML文档有效性检验问题是指给定AXML文档及其服务调用规范,检验文档是否符合目标模式。定义了用于抽象AXML模式的ASTAv机(AXML Schema Tree Automata forValidation),该树自动机描述符合目标模式约束的文档集合,能够完成对给定文档当前状态的有效性检验;基于ASTAv机,通过分析服务规范与目标模式之间的关系,提出了一种多项式时间的AXML文档有效性检验算法,分析了算法的正确性和有效性。
The presentation of Active XML(AXML for short) addresses the problems ofheterogeneity, interoperability and autonomy occurring in data management at thescale of the Web and becomes a new powerful tool for distributed data management.An AXML document is an XML document where some of the data is given explicitlywhile other parts are defined only intentionally by means of embedded calls to Webservices. When one of these calls is invoked, its results will be returned to enrich theoriginal document.
The problem of AXML data management consists of the following problems:(1)AXML Data exchange is the main application and the sender must decide whetherthe given AXML document can be rewritten into a new one conforming to the gargetschema by invoking the embedded service calls, which introduced schema rewriting;(2)The applications sometimes may consider whether all the documents conformingto the original schema can be rewritten to the target schema, named schema rewrit-ing; (3)In AXML data exchange, applications often ask data in querying manner andsatisfiability is the first condition before executing the given query. After deciding thesatisfiability of querying AXML documents, the unsatisfied ones will be refused andimprove the efficiency of queries. (4)Validation of AXML documents is the key ofAXML data management and the first condition of AXML data exchange and query-ing documents.
Based on tree automata theory, document rewriting and schema rewriting, sat-isfiability of querying documents and validation of documents that are studied in thethesis. The goal of this thesis is to propose efficient algorithms to address these prob-lems and make AXML to be suitable for data management of the Web.
First, problems of AXML document rewriting and schema rewriting are studied.AXML document rewriting is to decide whether the given document can be translatedto the new one conforming the garget schema by invoking some service calls embed-ded in it. AXML document rewriting contains two types: possible rewriting and saferewriting. The former is to decide whether the given document can be rewritten intoanother one conforming to the target schema; the latter is to decide whether the set of produced documents from the given AXML document can be rewritten to the docu-ments conforming to the garget schema. Schema rewriting is to decide whether all thedocuments conforming to the given AXML schema can be translated to the new onesof the target schema. Firstly, the AXML Document Tree Automata (ADTA) used torepresent AXML documents is defined, together with the building algorithm. Basedon ADTA and the defined complement of ADTA, both of algorithms, performed inpolynomial time, for deciding AXML document possible rewriting and safe rewritingare presented and the correction of them are analyzed. Secondly, the AXML SchemaTree Automata for rewriting (ASTAr) used to represent AXML schemas is also de-fined, together with the building algorithm is presented. Finally, based on ASTAr, analgorithm for deciding AXML schema rewriting is proposed which is performed inpolynomial time by analyzing the relationship between the AXML schema contain-ment and schema rewriting; the correction and efficiency are also given.
Second, problem of satisfiability of querying AXML documents conforming toa given AXML schema is studied. For the efficient evaluation of a query over anAXML document, one should check whether there exists an (A)XML document ob-tained from the original one by invoking some Web services, on which the queryhas a non-empty answer. firstly, the formal definition of satisfiability of queryingAXML documents is defined. Then, a new tree automaton, named AXML SchemaTree Automata for Queries (ASTAq), is defined which can efficiently represent the setof AXML documents conforming to the given schema; a TPQA (Tree Pattern QueryAutomaton) is also defined which can represent the document set of satisfying querypathes of the given tree pattern query. Finally, based on ASTAq and TPQA, an al-gorithm for checking satisfiability of tree pattern queries for AXML documents thatruns polynomial time is proposed and experiments were made to verify the utility ofsatisfiability checking.
Third, the problem of validating AXML documents is studied. Validation ofAXML document is to check whether a given AXML document with service callsspecification conforms the target schema. A new tree automaton, named AXMLSchema Tree Automaton for validation (ASTAv), is defined which can efficientlyrepresent the set of AXML documents conforming to the given schema and checkthe validation of the current state of an AXML document. Based on ASTAv, an al-gorithm is proposed for checking AXML validation performing in polynomial time through analyzing the relationship between the service calls specification and the tar-get schema. Finally, the experiment results show that our algorithm gives rise to anefficient validation method for AXML documents.
引文
1 A. Gupta. Integration of Information Systems: Bridging HeterogeneousDatabases. Piscataway, NJ, USA: IEEE Press, 1989
2 G. Wiederhold. Intelligent Integration of Information. SIGMOD’93: Proceed-ings of the 1993 ACM SIGMOD international conference on Management ofdata, Washington, D.C., USA. New York, NY, USA: ACM, 1993:434–437
3孟小峰. Web数据管理研究综述.计算机研究与发展. 2001, 38(4):385–395
4 T. Bray, J. Paoli, C. M. Sperberg-McQueen. Extensible Markup Language(XML) 1.0. 1998. http://www.w3.org/TR/1998/
5 T. Lahiri, S. Abiteboul, J. Widom. Ozone: Integrating Structured and Semistruc-tured Data. DBPL’99: Revised Papers from the 7th International Workshop onDatabase Programming Languages, Kinloch Rannoch, Scotland, UK. London,UK: Springer-Verlag, 2000:297–323
6 D. Draper, A. Y. Halevy, D. S. Weld. The Nimble XML Data IntegrationSystem. Proceedings of the 17th International Conference on Data Engineer-ing, Heidelberg, Germany. Washington, DC, USA: IEEE Computer Society,2001:155–160
7 I. Manolescu, D. Florescu, D. Kossmann. Answering XML Queries on Het-erogeneous Data Sources. VLDB’01: Proceedings of the 27th InternationalConference on Very Large Data Bases, Roma, Italy. San Francisco, CA, USA:Morgan Kaufmann Publishers Inc., 2001:241–250
8 Simple Object Access Protocol(SOAP). http://www.w3.org/TR/soap
9 Web Services Definition Language(WSDL). http://www.w3.org/TR/wsdl
10 The Napster Homepage. http://www.napster.com
11 The Gnutella Homepage. http://www.gnutella.com
12 S. Abiteboul, O. Benjelloun, I. Manolescu, et al. Active XML: Peer-to-PeerData and Web Services Integration. VLDB 2002: Proceedings of 28th Interna-tional Conference on Very Large Data Bases, August 20-23, 2002, Hong Kong,China. Morgan Kaufmann, 2002:1087–1090
13 S. Abiteboul, J. Baumgarten, A. Bonifati, et al. Managing DistributedWorkspaces with Active XML. VLDB’2003: Proceedings of the 29th Interna-tional Conference on Very Large Data Bases, Berlin, Germany. Morgan Kauf-mann, 2003:1061–1064
14 S. Abiteboul, O. Benjelloun, T. Milo. Web Services and Data Integration.The Third International Conference on Web Information Systems Engineer-ing (WISE’02), Singapore. Los Alamitos, CA, USA: IEEE Computer Society,2002:3–6
15 T. Milo, S. Abiteboul, B. Amann, et al. Exchanging Intensional XML Data.SIGMOD’03: Proceedings of the 2003 ACM SIGMOD international confer-ence on Management of data, San Diego, California, USA. New York, NY,USA: ACM Press, 2003:289–300
16 A. Muscholl, T. Schwentick, L. Segoufin. Active Context Free Games. Proceed-ing of the 21st International Symposium on Theoretical Aspects of ComputerScience(STACS), Saarbru¨cken, Germany. 2004:452–464
17 S. Abiteboul, T. Milo, O. Benjelloun. Regular Rewriting of Active XML andUnambiguity. PODS’05: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, Baltimore,Maryland. New York, NY, USA: ACM Press, 2005:295–303
18 S. Abiteboul, O. Benjelloun, B. Cautis, et al. Lazy Query Evaluation for ActiveXML. SIGMOD’04: Proceedings of the 2004 ACM SIGMOD internationalconference on Management of data, Paris, France. New York, NY, USA: ACMPress, 2004:227–238
19 S. Abiteboul, O. Benjelloun, T. Milo. Actvie XML and Active Query An-swers. Flexible Query Answering Systems, Lecture Notes in Computer Science.2004:17–27
20 S. Abiteboul, P. Bourhis, B. Marinoiu. Active Documents: Satisfiability ofQueries and View Maintenance. Tech. rep., INRIA Gemo Report, 2008
21 S. Abiteboul, L. Segoufin, V. Vianu. Static Analysis of Active XML Sys-tems. PODS’08: Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. New York, NY, USA:ACM, 2008:221–230
22 S. Abiteboul, O. Benjelloun, T. Milo. Positive Active XML. PODS’04: Pro-ceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium onPrinciples of database systems, Paris, France. New York, NY, USA: ACM Press,2004:35–45
23 S. Abiteboul. Turing the Network Into a Database with Active XML. EuropeanConference on Object-Oriented Programming, Nantes, France. 2006:203–205
24 S. Abiteboul, A. Bonifati, G. Cobena, et al. Dynamic XML Documents withDistribution and Replication. SIGMOD’03: Proceedings of the 2003 ACMSIGMOD international conference on Management of data, San Diego, Cali-fornia, USA. New York, NY, USA: ACM Press, 2003:527–538
25 D. Biswas. Active XML Replication and Recovery. CISIS-2008: Second Inter-national Conference on Complex, Intelligent and Software Intensive Systems,Barcelona, Spain. 2008
26 E. Canaud, S. Benbernou, M.-S. Hacid. Managing Trust in Active XML.SCC’04: Proceedings of the 2004 IEEE International Conference on ServicesComputing, Shanghai China. 2004:41–48
27 S. Abiteboul, B. Marinoiu. Distributed Monitoring of Peer to Peer Systems.WIDM’07: Proceedings of the 9th annual ACM international workshop onWeb information and data management, Lisbon, Portugal. New York, NY, USA:ACM, 2007:41–48
28 D. Biswas, I.-G. Kim. Atomicity for P2P Based XML Repositories. ICDE2007: Proceedings of the 23rd International Conference on Data EngineeringWorkshops, Istanbul, Turkey. IEEE Computer Society, 2007:363–370
29 I.-G. Kim. Static Verification of Access Control Model for AXML Documents.WAIM 2007: 8th International Conference, on Web-Age Information Manage-ment, Huang Shan, China. Springer, 2007:687–696
30 S. Abiteboul, O. Benjelloun, T. Milo. The Active XML Project: An Overview.The VLDB Journal. 2008, 17(5):1019–1040
31 O. Benjelloun. Active XML: A Data-centric Perspective on Web Services. IN-RIA, Ph.D. thesis. 2004
32 A. Y. Levy, A. Rajaraman, J. J. Ordille. Querying Heterogeneous InformationSources Using Source Descriptions. VLDB’96: Proceedings of the 22th Inter-national Conference on Very Large Data Bases, Mumbai(Bombay), India. SanFrancisco, CA, USA: Morgan Kaufmann Publishers Inc., 1996:251–262
33 H. Garcia-Molina, Y. Papakonstantinou, D. Quass, et al. The Tsimmis Approachto Mediation: Data Models and Languages. Journal of Intelligent InformationSystems. 1997, 8(2):117–132
34 Y. Papakonstantinou, V. Vassalos. Query Rewriting for Semistructured Data.SIGMOD’99: Proceedings of the 1999 ACM SIGMOD international confer-ence on Management of data, Dallas, Texas, Philadelphia, Pennsylvania, USA.New York, NY, USA: ACM, 1999:455–466
35 G. Gardarin, A. Mensch, A. Tomasic. An Introduction to the E-XML Data In-tegration Suite. EDBT’02: Proceedings of the 8th International Conferenceon Extending Database Technology, Prague, Czech Republic. London, UK:Springer-Verlag, 2002:297–306
36 Y. Papakonstantinou, V. R. Borkar, M. Orgiyan, et al. XML Queries and Algebrain the Enosys Integration Platform. Data & Knowledge Engineering. 2003,44(3):299–322
37 S. Abiteboul, R. Hull, V. Vianu, (Editors) Foundations of Databases: The Logi-cal Level. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc.,1995
38 H. Molina, J. D.Ullman, J. Widom. Database Systems: The Complete Book.Beijing: China Machine Press, 2003
39 G. Weikum. Infrastructure for Advanced E-services. IEEE Data EngineeringBulletin. 2001, 24(1):1–70
40 R. H. Halstead. Multilisp: A Language for Concurrent Symbolic Computation.ACM Transactions on Programming Languages and Systems. 1985, 7(4):501–
53841 L. Cardelli. Abstractions for Mobile Computation. Secure Internet Program-ming. Springer, 1999, 1603:51–94
42 L. Cardelli, A. D. Gordon. Mobile Ambients. Theory Computer Science. 2000,240(1):177–213
43 Web Services Flow Language(WSFL1.0). http://www.ibm.com/developerworks/library/ws-ref4
44 Web Services for Business Process Design. http://www.gotdotnet.com/team/xml_wsspecs/xlang-c.
45 R. Hull, M. Benedikt, V. Christophides, et al. E-services: A Look Behindthe Curtain. PODS’03: Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, San Diego,California, USA. New York, NY, USA: ACM, 2003:1–14
46 V. Christophides, R. Hull, A. Kumar, et al. Work?ow Mediation Using Vor-teXML. IEEE Data Eng. Bull. 2001, 24(1):40–45
47 J. D.Ullman, J. Widom. A First Course in Database Systems, Second Edition.second edn. Beijing: China Machine Press, 2006
48 R. G. G. Cattell, D. K. Barry, D. Bartels, et al. The Object Database Standard:Odmg 2.0. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1997
49 The PHP Hypertext Preprocessor. http://www.php.net
50 SUN’s Java Server Pages. http://java.sun.com/products/jsp
51 J. McHugh, S. Abiteboul, R. Goldman, et al. Lore: A Database ManagementSystem for Semistructured Data. ACM SIGMOD Record. 1997, 26(3):54–66
52 A. Bonifati, S. Ceri, S. Paraboschi. Pushing Reactive Services to XML Repos-itories Using Active Rules. Proceedings of the Tenth International World WideWeb Conference, Hong Kong, China. 2001:633–641
53 A. Bonifati, D. Braga, A. Campi, et al. Active XQuery. 18th InternationalConference on Data Engineering (ICDE’02), San Jose, California, USA. IEEEComputer Society, 2002:403–418
54 S. Abiteboul, B. Amann, A. Bonifati, et al. Active Views for Electronic Com-merce. VLDB’99: Proceedings of the 25th International Conference on VeryLarge Data Bases, Edinburgh, Scotland, UK. San Francisco, CA, USA: MorganKaufmann Publishers Inc., 1999:138–149
55 T. Ozsu, P. Valduriez. Principles of Distributed Database Systems. second edn.Beijing: Tsinghua University Press, 2002
56 S. Abiteboul. Distributed Information Management with XML and Web Ser-vices. Fundamental Approaches to Software Engineering, 7th InternationalConference, FASE 2004, Barcelona, Spain. Springer, 2004:1–11
57 S. Abiteboul, I. Manolescu, E. Taropa. A Framework for Distributed XML DataManagement. 10th International Conference on Extending Database Technol-ogy, Munich, Germany. 2006:1049–1058
58 R. Fagin, P. G. Kolaitis, R. J. Miller, et al. Data Exchange: Semantics andQuery Answering. ICDT’03: Proceedings of the 9th International Conferenceon Database Theory, Siena, Italy. London, UK: Springer-Verlag, 2003:207–224
59 R. Fagin, P. G. Kolaitis, L. Popa. Data Exchange: Getting to the Core. PODS’03: Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGARTsymposium on Principles of database systems,San Diego, California. NewYork, NY, USA: ACM, 2003:90–101
60 R. Fagin, P. G. Kolaitis, W.-C. Tan, et al. Composing Schema Mappings:Second-Order Dependencies to the Rescue. PODS’04: Proceedings of thetwenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles ofdatabase systems, Paris, France. New York, NY, USA: ACM, 2004:83–94
61 P. G. Kolaitis. Schema Mappings, Data Exchange, and Metadata Manage-ment. PODS’05: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, Baltimore, Maryland,USA. New York, NY, USA: ACM Press, 2005:61–75
62 R. Fagin. Inverting Schema Mappings. Proceedings of the Twenty-Fifth ACMSIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems,June 26-28, 2006, Chicago, Illinois, Maryland, USA. ACM, 2006:50–59
63 M. Arenas, P. Barcelo′, R. Fagin, et al. Locally Consistent Transformations andQuery Answering in Data Exchange. PODS’04: Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of databasesystems, Paris, France. New York, NY, USA: ACM, 2004:229–240
64 C. Yu, L. Popa. Constraint-based XML Query Rewriting for Data Integra-tion. SIGMOD’04: Proceedings of the 2004 ACM SIGMOD internationalconference on Management of data, Paris, France. New York, NY, USA: ACM,2004:371–382
65 P. G. Kolaitis, J. Panttaja, W. C. Tan. The Complexity of Data Exchange. Pro-ceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposiumon Principles of Database Systems, June 26-28, 2006, Chicago, Illinois, Mary-land, USA. ACM, 2006:30–39
66 G. Gottlob, A. Nash. Data Exchange: Computing Cores in Polynomial Time.Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Sympo-sium on Principles of Database Systems, June 26-28, 2006, Chicago, Illinois,Maryland, USA. Springer-Verlag, 2006:40–49
67 M. Arenas, L. Libkin. XML Data Exchange: Consistency and Query Answer-ing. PODS’05: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems,Baltimore, Maryland.New York, NY, USA: ACM Press, 2005:13–24
68高永兵,胡文江,靳荣. Active XML文档重写机制的研究.计算机技术与发展. 2008, 18(3):85–88
69 J. Hidders. Satisfiability of XPath Expressions. The 9th International Workshopon Data Base Programming Languages, Potsdam, Germany. 2003:21–36
70 L. V. S. Lakshmanan, G. Ramesh, H. Wang, et al. On Testing Satisfiability ofTree Pattern Queries. Proceedings of the Thirtieth International Conference onVery Large Data Bases, Toronto, Canada. 2004:120–131
71 M. Benedikt, W. Fan, F. Geerts. XPath Satisfiability in the Presence ofDTDs. PODS’05: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, Baltimore, Maryland.New York, NY, USA: ACM Press, 2005:25–36
72 G. Gottlob, C. Koch, R. Pichler. Efficient Algorithms for Processing XPathQueries. ACM Transactions on Database Systems. 2005, 30(2):444–491
73 P. T. Wood. Containment for XPath Fragments under DTD Constraints. ICDT’03: Proceedings of the 9th International Conference on Database Theory,Siena, Italy. London, UK: Springer, 2003, 2572:300–314
74 M. Murata, D. Lee, M. Mani, et al. Taxonomy of XML Schema LanguagesUsing Formal Language Theory. ACM Transactions of Internet Technology.2005, 5(4):660–704
75徐德智,吴敏. XML自动机的构造及实用化研究.计算机学报. 2003,26(4):471–476
76 B. Bouchou, M. H. F. Alves, D. Laurent, et al. Extending Tree Automata toModel XML Validation under Element and Attribute Constraints. ICEIS 2003:Proceedings of the 5th International Conference on Enterprise Information Sys-tems, April 22-26, 2003, Angers, France. 2003:184–190
77 A. Balmin, Y. Papakonstantinou, V. Vianu. Incremental Validation of XMLDocuments. ACM Transactions on Database Systems (TODS). 2004,29(4):710–751
78 D. Barbosa, A. O. Mendelzon, L. Libkin, et al. Efficient Incremental Valida-tion of XML Documents. ICDE’04: Proceedings of the 20th InternationalConference on Data Engineering, Boston, USA. Washington, DC, USA: IEEEComputer Society, 2004:671–682
79 L. Segoufin, V. Vianu. Validating Streaming XML Documents. PODS’02:Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposiumon Principles of database systems, Madison, Wisconsin, USA. New York, NY,USA: ACM Press, 2002:53–64
80 C. Chitic, D. Rosu. On Validation of XML Streams Using Finite State Ma-chines. WebDB’04: Proceedings of the 7th International Workshop on theWeb and Databases, Paris, France. New York, NY, USA: ACM, 2004:85–90
81 N. Alon, T. Milo, F. Neven, et al. Typechecking XML Views of RelationalDatabases. ACM Transactions on Computational Logic. 2003, 4(3):315–354
82 N. Alon, T. Milo, F. Neven, et al. XML with Data Values: Typechecking Revis-ited. Journal of Computer and System Sciences. 2003, 66(4):688–727
83 D. Suciu. Typechecking for Semistructured Data. DBPL’01: Revised Papersfrom the 8th International Workshop on Database Programming Languages,Potsdam, Germany. London, UK: Springer-Verlag, 2002:1–20
84 D. Suciu. The XML Typechecking Problem. ACM SIGMOD Record. 2002,31(1):89–96
85 T. Milo, D. Suciu, V. Vianu. Typechecking for XML Transformers. Journal ofComputer and System Sciences. 2003, 66(1):66–97
86 W. Martens, F. Neven. Typechecking Top-down Uniform Unranked Tree Trans-ducers. ICDT’03: Proceedings of the 9th International Conference on DatabaseTheory, Siena, Italy. London, UK: Springer-Verlag, 2002:64–78
87 W. Martens, F. Neven. Frontiers of Tractability for Typechecking Simple XMLTransformations. PODS’04: Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. New York,NY, USA: ACM, 2004:23–34
88 H. Comon, M. Dauchet, R. Gilleron, et al. Tree Automata Techniques andApplications. Available on: http://www.grappa.univ-lille3.fr/tata, 2007. Release October, 12th 2007
89 V. Vianu. A Web Odyssey: From Codd to XML. PODS’01: Proceedingsof the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principlesof database systems, Santa Barbara, California, USA. New York, NY, USA:ACM, 2001:1–15
90 F. Neven. Automata Theory for XML Researchers. ACM SIGMOD Record.2002, 31(3):39–46
91 F. Neven. Automata, Logic, and XML. Computer Science Logic, 16th Inter-national Workshop, CSL 2002, 11th Annual Conference of the EACSL, Ed-inburgh, Scotland, UK, September 22-25, 2002, Proceedings. Springer, 2002,2471:2–26
92 T. Schwentick. Trees, Automata and XML. PODS’04: Proceedings of thetwenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles ofdatabase systems, Paris, France. New York, NY, USA: ACM, 2004:222–222
93 A. Bruggemann-Klein, M. Murata, D. Wood. Regular Tree and Regular HedgeLanguages Over Unranked Alphabets. Tech. rep., HKUST-TCSC-2001-0, TheHong Kong University of Science and Technology, 2001
94 H. Hosoya, B. C. Pierce. Regular Expression Pattern Matching for XML. Jour-nal of Functional Programming. 2003, 13(6):961–1004
95 F. Neven, T. Schwentick. Query Automata. PODS’99: Proceedings ofthe eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principlesof database systems, Philadelphia, Pennsylvania, USA. New York, NY, USA:ACM, 1999:205–214
96 F. Neven, T. Schwentick. XPath Containment in the Presence of Disjunction,DTDs, and Variables. ICDT’03: Proceedings of the 9th International Confer-ence on Database Theory, Siena, Italy. Springer, 2003, 2572:315–329
97 G. Miklau, D. Suciu. Containment and Equivalence for a Fragment of XPath.Journal of ACM(JACM). 2004, 51(1):2–45
98高军,杨冬青,唐世谓,等.一种基于DTD的XPath逻辑优化方法.软件学报. 2004, 15(12):1860–1868
99高军,杨冬青,唐世谓,等.基于树自动机的XPath在XML数据流上的高效执行.软件学报. 2005, 16(2):223–232
100 T. Bray, J. Paoli, C. M. Sperberg-McQueen, et al. The Extensible MarkupLanguage(XML) 1.0 (4nd Edition). 2006. http://www.w3.org/TR/REC-xml
101 I. O. for Standardization. Iso 8879:1986 Information Processing– Text andOffice Systems– Standard Generalized Markup Language (SGML). Geneva,Switzerland: International Organization for Standardization, 1986
102 The Hypertext Markup Language. http://www.w3.org/TR/html
103 S. Cluet, C. Delobel, J. Sime′on, et al. Your Mediators Need Data Conversion!ACM SIGMOD Record. 1998, 27(2):177–188
104 H. Hosoya, B. C. Pierce. XDuce: A Statically Typed XML Processing Lan-guage. ACM Transactions on Internet Technology. 2003, 3(2):117–148
105 RELAX (regular Language Description for XML). http://www.xml.gr.jp/relax
106 The XML Schema Specification. http://www.w3.org/TR/XML/Schema
107 XML Path Language(XPath) Version 1.0. http://www.w3c.org/TR/xpath
108 XQuery 1.0: An XML Query Language. http://www.w3c.org/TR/xquery
109 XSL Transformations (XSLT) Version 1.0. http://www.w3c.org/TR/xslt
110 M. Benedikt, W. Fan, G. Kuper. Structural Properties of XPath Fragments.Theoretical Computer Science. 2005, 336(1):3–31
111 S. Amer-Yahia, S. Cho, L. V. S. Lakshmanan, et al. Tree Pattern Query Mini-mization. The VLDB Journal. 2002, 11(4):315–331
112 Universal Description, Discovery and Integration of Business for theWeb(UDDI). http://uddi.xml.org/uddi-org
113 A. Bru¨ggemann-Klein, D. Wood. One-unambiguous Regular Languages. In-formation and Computation. 1998, 142(2):182–206
114 W. Martens. Static Analysis of XML Transformation and Schema Languages.University of Limburg, Ph.D. thesis. 2006
115 T. J. Green, A. Gupta, G. Miklau, et al. Processing XML Streams with Deter-ministic Automata and Stream Indexes. ACM Transactions on Database Sys-tems. 2004, 29(4):752–788
116高军,杨冬青,唐世谓,等.一种XML数据流之上持续查询执行器的增量维护方法.计算机研究与发展. 2005, 42(5):771–776
117 Y. Papakonstantinou, V. Vianu. DTD Inference for Views of XML Data. PODS’00: Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART sympo-sium on Principles of database systems, Dallas, Texas, USA. New York, NY,USA: ACM Press, 2000:35–46
118 J. E. Hopcroft, R. Motwani, J. D. Ullman. Introduction to Automata Theory,Languages, and Computation. second edn. Beijing: Tsinghua University Press,2002, 46–66
119 A. Tozawa, M. Hagiya. XML Schema Containment Checking Based on Semi-implicit Techniques. Implementation and Application of Automata, 8th Inter-national Conference, Santa Barbara, CA, USA. 2003:213–225
120 H. Seidl. Deciding Equivalence of Finite Tree Automata. SIAM Journal ofComputing. 1990, 19(3):424–437
121 H. Seidl. Haskell Overloading is DEXPTIME-complete. Information Process-ing Letters. 1994, 52(2):57–60
122 L. J. Stockmeyer, A. R. Meyer. Word Problems Requiring ExponentialTime(preliminary Report). STOC’73: Proceedings of the fifth annual ACMsymposium on Theory of computing, Austin, Texas, USA. New York, NY,USA: ACM, 1973:1–9
123 W. Fan, L. Libkin. On XML Integrity Constraints in the Presence of DTDs.Journal of the ACM. 2002, 49(3):368–406
124 T. Milo, D. Suciu. Type Inference for Queries on Semistructured Data. PODS’99: Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART sympo-sium on Principles of database systems. New York, NY, USA: ACM, 1999:215–226125 D. Barbosa, A. O. Mendelzon, J. Keenleyside, et al. Toxgene: An ExtensibleTemplate-based Data Generator for XML. WebDB2002: Fifth InternationalWorkshop on the Web and Databases, Madison, Wisconsin. New York, NY,USA: ACM Press, 2002:49–54
126 Apache Org. http://xml.apache.org/xalan-j
127 M. Arenas, L. Libkin. A Normal Form for XML Documents. ACM Transactionson Database Systems. 2004, 29(1):195–232
128 SAX 2.0.2: The Simple API for XML. http://www.saxproject.org/
129 Document Object Model (DOM) Level 3 Validation Specification. http://www.w3.org/TR/2004/REC-DOM-Level-3-Val-20040127/
2 G. Wiederhold. Intelligent Integration of Information. SIGMOD’93: Proceed-ings of the 1993 ACM SIGMOD international conference on Management ofdata, Washington, D.C., USA. New York, NY, USA: ACM, 1993:434–437
3孟小峰. Web数据管理研究综述.计算机研究与发展. 2001, 38(4):385–395
4 T. Bray, J. Paoli, C. M. Sperberg-McQueen. Extensible Markup Language(XML) 1.0. 1998. http://www.w3.org/TR/1998/
5 T. Lahiri, S. Abiteboul, J. Widom. Ozone: Integrating Structured and Semistruc-tured Data. DBPL’99: Revised Papers from the 7th International Workshop onDatabase Programming Languages, Kinloch Rannoch, Scotland, UK. London,UK: Springer-Verlag, 2000:297–323
6 D. Draper, A. Y. Halevy, D. S. Weld. The Nimble XML Data IntegrationSystem. Proceedings of the 17th International Conference on Data Engineer-ing, Heidelberg, Germany. Washington, DC, USA: IEEE Computer Society,2001:155–160
7 I. Manolescu, D. Florescu, D. Kossmann. Answering XML Queries on Het-erogeneous Data Sources. VLDB’01: Proceedings of the 27th InternationalConference on Very Large Data Bases, Roma, Italy. San Francisco, CA, USA:Morgan Kaufmann Publishers Inc., 2001:241–250
8 Simple Object Access Protocol(SOAP). http://www.w3.org/TR/soap
9 Web Services Definition Language(WSDL). http://www.w3.org/TR/wsdl
10 The Napster Homepage. http://www.napster.com
11 The Gnutella Homepage. http://www.gnutella.com
12 S. Abiteboul, O. Benjelloun, I. Manolescu, et al. Active XML: Peer-to-PeerData and Web Services Integration. VLDB 2002: Proceedings of 28th Interna-tional Conference on Very Large Data Bases, August 20-23, 2002, Hong Kong,China. Morgan Kaufmann, 2002:1087–1090
13 S. Abiteboul, J. Baumgarten, A. Bonifati, et al. Managing DistributedWorkspaces with Active XML. VLDB’2003: Proceedings of the 29th Interna-tional Conference on Very Large Data Bases, Berlin, Germany. Morgan Kauf-mann, 2003:1061–1064
14 S. Abiteboul, O. Benjelloun, T. Milo. Web Services and Data Integration.The Third International Conference on Web Information Systems Engineer-ing (WISE’02), Singapore. Los Alamitos, CA, USA: IEEE Computer Society,2002:3–6
15 T. Milo, S. Abiteboul, B. Amann, et al. Exchanging Intensional XML Data.SIGMOD’03: Proceedings of the 2003 ACM SIGMOD international confer-ence on Management of data, San Diego, California, USA. New York, NY,USA: ACM Press, 2003:289–300
16 A. Muscholl, T. Schwentick, L. Segoufin. Active Context Free Games. Proceed-ing of the 21st International Symposium on Theoretical Aspects of ComputerScience(STACS), Saarbru¨cken, Germany. 2004:452–464
17 S. Abiteboul, T. Milo, O. Benjelloun. Regular Rewriting of Active XML andUnambiguity. PODS’05: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, Baltimore,Maryland. New York, NY, USA: ACM Press, 2005:295–303
18 S. Abiteboul, O. Benjelloun, B. Cautis, et al. Lazy Query Evaluation for ActiveXML. SIGMOD’04: Proceedings of the 2004 ACM SIGMOD internationalconference on Management of data, Paris, France. New York, NY, USA: ACMPress, 2004:227–238
19 S. Abiteboul, O. Benjelloun, T. Milo. Actvie XML and Active Query An-swers. Flexible Query Answering Systems, Lecture Notes in Computer Science.2004:17–27
20 S. Abiteboul, P. Bourhis, B. Marinoiu. Active Documents: Satisfiability ofQueries and View Maintenance. Tech. rep., INRIA Gemo Report, 2008
21 S. Abiteboul, L. Segoufin, V. Vianu. Static Analysis of Active XML Sys-tems. PODS’08: Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. New York, NY, USA:ACM, 2008:221–230
22 S. Abiteboul, O. Benjelloun, T. Milo. Positive Active XML. PODS’04: Pro-ceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium onPrinciples of database systems, Paris, France. New York, NY, USA: ACM Press,2004:35–45
23 S. Abiteboul. Turing the Network Into a Database with Active XML. EuropeanConference on Object-Oriented Programming, Nantes, France. 2006:203–205
24 S. Abiteboul, A. Bonifati, G. Cobena, et al. Dynamic XML Documents withDistribution and Replication. SIGMOD’03: Proceedings of the 2003 ACMSIGMOD international conference on Management of data, San Diego, Cali-fornia, USA. New York, NY, USA: ACM Press, 2003:527–538
25 D. Biswas. Active XML Replication and Recovery. CISIS-2008: Second Inter-national Conference on Complex, Intelligent and Software Intensive Systems,Barcelona, Spain. 2008
26 E. Canaud, S. Benbernou, M.-S. Hacid. Managing Trust in Active XML.SCC’04: Proceedings of the 2004 IEEE International Conference on ServicesComputing, Shanghai China. 2004:41–48
27 S. Abiteboul, B. Marinoiu. Distributed Monitoring of Peer to Peer Systems.WIDM’07: Proceedings of the 9th annual ACM international workshop onWeb information and data management, Lisbon, Portugal. New York, NY, USA:ACM, 2007:41–48
28 D. Biswas, I.-G. Kim. Atomicity for P2P Based XML Repositories. ICDE2007: Proceedings of the 23rd International Conference on Data EngineeringWorkshops, Istanbul, Turkey. IEEE Computer Society, 2007:363–370
29 I.-G. Kim. Static Verification of Access Control Model for AXML Documents.WAIM 2007: 8th International Conference, on Web-Age Information Manage-ment, Huang Shan, China. Springer, 2007:687–696
30 S. Abiteboul, O. Benjelloun, T. Milo. The Active XML Project: An Overview.The VLDB Journal. 2008, 17(5):1019–1040
31 O. Benjelloun. Active XML: A Data-centric Perspective on Web Services. IN-RIA, Ph.D. thesis. 2004
32 A. Y. Levy, A. Rajaraman, J. J. Ordille. Querying Heterogeneous InformationSources Using Source Descriptions. VLDB’96: Proceedings of the 22th Inter-national Conference on Very Large Data Bases, Mumbai(Bombay), India. SanFrancisco, CA, USA: Morgan Kaufmann Publishers Inc., 1996:251–262
33 H. Garcia-Molina, Y. Papakonstantinou, D. Quass, et al. The Tsimmis Approachto Mediation: Data Models and Languages. Journal of Intelligent InformationSystems. 1997, 8(2):117–132
34 Y. Papakonstantinou, V. Vassalos. Query Rewriting for Semistructured Data.SIGMOD’99: Proceedings of the 1999 ACM SIGMOD international confer-ence on Management of data, Dallas, Texas, Philadelphia, Pennsylvania, USA.New York, NY, USA: ACM, 1999:455–466
35 G. Gardarin, A. Mensch, A. Tomasic. An Introduction to the E-XML Data In-tegration Suite. EDBT’02: Proceedings of the 8th International Conferenceon Extending Database Technology, Prague, Czech Republic. London, UK:Springer-Verlag, 2002:297–306
36 Y. Papakonstantinou, V. R. Borkar, M. Orgiyan, et al. XML Queries and Algebrain the Enosys Integration Platform. Data & Knowledge Engineering. 2003,44(3):299–322
37 S. Abiteboul, R. Hull, V. Vianu, (Editors) Foundations of Databases: The Logi-cal Level. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc.,1995
38 H. Molina, J. D.Ullman, J. Widom. Database Systems: The Complete Book.Beijing: China Machine Press, 2003
39 G. Weikum. Infrastructure for Advanced E-services. IEEE Data EngineeringBulletin. 2001, 24(1):1–70
40 R. H. Halstead. Multilisp: A Language for Concurrent Symbolic Computation.ACM Transactions on Programming Languages and Systems. 1985, 7(4):501–
53841 L. Cardelli. Abstractions for Mobile Computation. Secure Internet Program-ming. Springer, 1999, 1603:51–94
42 L. Cardelli, A. D. Gordon. Mobile Ambients. Theory Computer Science. 2000,240(1):177–213
43 Web Services Flow Language(WSFL1.0). http://www.ibm.com/developerworks/library/ws-ref4
44 Web Services for Business Process Design. http://www.gotdotnet.com/team/xml_wsspecs/xlang-c.
45 R. Hull, M. Benedikt, V. Christophides, et al. E-services: A Look Behindthe Curtain. PODS’03: Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, San Diego,California, USA. New York, NY, USA: ACM, 2003:1–14
46 V. Christophides, R. Hull, A. Kumar, et al. Work?ow Mediation Using Vor-teXML. IEEE Data Eng. Bull. 2001, 24(1):40–45
47 J. D.Ullman, J. Widom. A First Course in Database Systems, Second Edition.second edn. Beijing: China Machine Press, 2006
48 R. G. G. Cattell, D. K. Barry, D. Bartels, et al. The Object Database Standard:Odmg 2.0. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1997
49 The PHP Hypertext Preprocessor. http://www.php.net
50 SUN’s Java Server Pages. http://java.sun.com/products/jsp
51 J. McHugh, S. Abiteboul, R. Goldman, et al. Lore: A Database ManagementSystem for Semistructured Data. ACM SIGMOD Record. 1997, 26(3):54–66
52 A. Bonifati, S. Ceri, S. Paraboschi. Pushing Reactive Services to XML Repos-itories Using Active Rules. Proceedings of the Tenth International World WideWeb Conference, Hong Kong, China. 2001:633–641
53 A. Bonifati, D. Braga, A. Campi, et al. Active XQuery. 18th InternationalConference on Data Engineering (ICDE’02), San Jose, California, USA. IEEEComputer Society, 2002:403–418
54 S. Abiteboul, B. Amann, A. Bonifati, et al. Active Views for Electronic Com-merce. VLDB’99: Proceedings of the 25th International Conference on VeryLarge Data Bases, Edinburgh, Scotland, UK. San Francisco, CA, USA: MorganKaufmann Publishers Inc., 1999:138–149
55 T. Ozsu, P. Valduriez. Principles of Distributed Database Systems. second edn.Beijing: Tsinghua University Press, 2002
56 S. Abiteboul. Distributed Information Management with XML and Web Ser-vices. Fundamental Approaches to Software Engineering, 7th InternationalConference, FASE 2004, Barcelona, Spain. Springer, 2004:1–11
57 S. Abiteboul, I. Manolescu, E. Taropa. A Framework for Distributed XML DataManagement. 10th International Conference on Extending Database Technol-ogy, Munich, Germany. 2006:1049–1058
58 R. Fagin, P. G. Kolaitis, R. J. Miller, et al. Data Exchange: Semantics andQuery Answering. ICDT’03: Proceedings of the 9th International Conferenceon Database Theory, Siena, Italy. London, UK: Springer-Verlag, 2003:207–224
59 R. Fagin, P. G. Kolaitis, L. Popa. Data Exchange: Getting to the Core. PODS’03: Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGARTsymposium on Principles of database systems,San Diego, California. NewYork, NY, USA: ACM, 2003:90–101
60 R. Fagin, P. G. Kolaitis, W.-C. Tan, et al. Composing Schema Mappings:Second-Order Dependencies to the Rescue. PODS’04: Proceedings of thetwenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles ofdatabase systems, Paris, France. New York, NY, USA: ACM, 2004:83–94
61 P. G. Kolaitis. Schema Mappings, Data Exchange, and Metadata Manage-ment. PODS’05: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, Baltimore, Maryland,USA. New York, NY, USA: ACM Press, 2005:61–75
62 R. Fagin. Inverting Schema Mappings. Proceedings of the Twenty-Fifth ACMSIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems,June 26-28, 2006, Chicago, Illinois, Maryland, USA. ACM, 2006:50–59
63 M. Arenas, P. Barcelo′, R. Fagin, et al. Locally Consistent Transformations andQuery Answering in Data Exchange. PODS’04: Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of databasesystems, Paris, France. New York, NY, USA: ACM, 2004:229–240
64 C. Yu, L. Popa. Constraint-based XML Query Rewriting for Data Integra-tion. SIGMOD’04: Proceedings of the 2004 ACM SIGMOD internationalconference on Management of data, Paris, France. New York, NY, USA: ACM,2004:371–382
65 P. G. Kolaitis, J. Panttaja, W. C. Tan. The Complexity of Data Exchange. Pro-ceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposiumon Principles of Database Systems, June 26-28, 2006, Chicago, Illinois, Mary-land, USA. ACM, 2006:30–39
66 G. Gottlob, A. Nash. Data Exchange: Computing Cores in Polynomial Time.Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Sympo-sium on Principles of Database Systems, June 26-28, 2006, Chicago, Illinois,Maryland, USA. Springer-Verlag, 2006:40–49
67 M. Arenas, L. Libkin. XML Data Exchange: Consistency and Query Answer-ing. PODS’05: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems,Baltimore, Maryland.New York, NY, USA: ACM Press, 2005:13–24
68高永兵,胡文江,靳荣. Active XML文档重写机制的研究.计算机技术与发展. 2008, 18(3):85–88
69 J. Hidders. Satisfiability of XPath Expressions. The 9th International Workshopon Data Base Programming Languages, Potsdam, Germany. 2003:21–36
70 L. V. S. Lakshmanan, G. Ramesh, H. Wang, et al. On Testing Satisfiability ofTree Pattern Queries. Proceedings of the Thirtieth International Conference onVery Large Data Bases, Toronto, Canada. 2004:120–131
71 M. Benedikt, W. Fan, F. Geerts. XPath Satisfiability in the Presence ofDTDs. PODS’05: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, Baltimore, Maryland.New York, NY, USA: ACM Press, 2005:25–36
72 G. Gottlob, C. Koch, R. Pichler. Efficient Algorithms for Processing XPathQueries. ACM Transactions on Database Systems. 2005, 30(2):444–491
73 P. T. Wood. Containment for XPath Fragments under DTD Constraints. ICDT’03: Proceedings of the 9th International Conference on Database Theory,Siena, Italy. London, UK: Springer, 2003, 2572:300–314
74 M. Murata, D. Lee, M. Mani, et al. Taxonomy of XML Schema LanguagesUsing Formal Language Theory. ACM Transactions of Internet Technology.2005, 5(4):660–704
75徐德智,吴敏. XML自动机的构造及实用化研究.计算机学报. 2003,26(4):471–476
76 B. Bouchou, M. H. F. Alves, D. Laurent, et al. Extending Tree Automata toModel XML Validation under Element and Attribute Constraints. ICEIS 2003:Proceedings of the 5th International Conference on Enterprise Information Sys-tems, April 22-26, 2003, Angers, France. 2003:184–190
77 A. Balmin, Y. Papakonstantinou, V. Vianu. Incremental Validation of XMLDocuments. ACM Transactions on Database Systems (TODS). 2004,29(4):710–751
78 D. Barbosa, A. O. Mendelzon, L. Libkin, et al. Efficient Incremental Valida-tion of XML Documents. ICDE’04: Proceedings of the 20th InternationalConference on Data Engineering, Boston, USA. Washington, DC, USA: IEEEComputer Society, 2004:671–682
79 L. Segoufin, V. Vianu. Validating Streaming XML Documents. PODS’02:Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposiumon Principles of database systems, Madison, Wisconsin, USA. New York, NY,USA: ACM Press, 2002:53–64
80 C. Chitic, D. Rosu. On Validation of XML Streams Using Finite State Ma-chines. WebDB’04: Proceedings of the 7th International Workshop on theWeb and Databases, Paris, France. New York, NY, USA: ACM, 2004:85–90
81 N. Alon, T. Milo, F. Neven, et al. Typechecking XML Views of RelationalDatabases. ACM Transactions on Computational Logic. 2003, 4(3):315–354
82 N. Alon, T. Milo, F. Neven, et al. XML with Data Values: Typechecking Revis-ited. Journal of Computer and System Sciences. 2003, 66(4):688–727
83 D. Suciu. Typechecking for Semistructured Data. DBPL’01: Revised Papersfrom the 8th International Workshop on Database Programming Languages,Potsdam, Germany. London, UK: Springer-Verlag, 2002:1–20
84 D. Suciu. The XML Typechecking Problem. ACM SIGMOD Record. 2002,31(1):89–96
85 T. Milo, D. Suciu, V. Vianu. Typechecking for XML Transformers. Journal ofComputer and System Sciences. 2003, 66(1):66–97
86 W. Martens, F. Neven. Typechecking Top-down Uniform Unranked Tree Trans-ducers. ICDT’03: Proceedings of the 9th International Conference on DatabaseTheory, Siena, Italy. London, UK: Springer-Verlag, 2002:64–78
87 W. Martens, F. Neven. Frontiers of Tractability for Typechecking Simple XMLTransformations. PODS’04: Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. New York,NY, USA: ACM, 2004:23–34
88 H. Comon, M. Dauchet, R. Gilleron, et al. Tree Automata Techniques andApplications. Available on: http://www.grappa.univ-lille3.fr/tata, 2007. Release October, 12th 2007
89 V. Vianu. A Web Odyssey: From Codd to XML. PODS’01: Proceedingsof the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principlesof database systems, Santa Barbara, California, USA. New York, NY, USA:ACM, 2001:1–15
90 F. Neven. Automata Theory for XML Researchers. ACM SIGMOD Record.2002, 31(3):39–46
91 F. Neven. Automata, Logic, and XML. Computer Science Logic, 16th Inter-national Workshop, CSL 2002, 11th Annual Conference of the EACSL, Ed-inburgh, Scotland, UK, September 22-25, 2002, Proceedings. Springer, 2002,2471:2–26
92 T. Schwentick. Trees, Automata and XML. PODS’04: Proceedings of thetwenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles ofdatabase systems, Paris, France. New York, NY, USA: ACM, 2004:222–222
93 A. Bruggemann-Klein, M. Murata, D. Wood. Regular Tree and Regular HedgeLanguages Over Unranked Alphabets. Tech. rep., HKUST-TCSC-2001-0, TheHong Kong University of Science and Technology, 2001
94 H. Hosoya, B. C. Pierce. Regular Expression Pattern Matching for XML. Jour-nal of Functional Programming. 2003, 13(6):961–1004
95 F. Neven, T. Schwentick. Query Automata. PODS’99: Proceedings ofthe eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principlesof database systems, Philadelphia, Pennsylvania, USA. New York, NY, USA:ACM, 1999:205–214
96 F. Neven, T. Schwentick. XPath Containment in the Presence of Disjunction,DTDs, and Variables. ICDT’03: Proceedings of the 9th International Confer-ence on Database Theory, Siena, Italy. Springer, 2003, 2572:315–329
97 G. Miklau, D. Suciu. Containment and Equivalence for a Fragment of XPath.Journal of ACM(JACM). 2004, 51(1):2–45
98高军,杨冬青,唐世谓,等.一种基于DTD的XPath逻辑优化方法.软件学报. 2004, 15(12):1860–1868
99高军,杨冬青,唐世谓,等.基于树自动机的XPath在XML数据流上的高效执行.软件学报. 2005, 16(2):223–232
100 T. Bray, J. Paoli, C. M. Sperberg-McQueen, et al. The Extensible MarkupLanguage(XML) 1.0 (4nd Edition). 2006. http://www.w3.org/TR/REC-xml
101 I. O. for Standardization. Iso 8879:1986 Information Processing– Text andOffice Systems– Standard Generalized Markup Language (SGML). Geneva,Switzerland: International Organization for Standardization, 1986
102 The Hypertext Markup Language. http://www.w3.org/TR/html
103 S. Cluet, C. Delobel, J. Sime′on, et al. Your Mediators Need Data Conversion!ACM SIGMOD Record. 1998, 27(2):177–188
104 H. Hosoya, B. C. Pierce. XDuce: A Statically Typed XML Processing Lan-guage. ACM Transactions on Internet Technology. 2003, 3(2):117–148
105 RELAX (regular Language Description for XML). http://www.xml.gr.jp/relax
106 The XML Schema Specification. http://www.w3.org/TR/XML/Schema
107 XML Path Language(XPath) Version 1.0. http://www.w3c.org/TR/xpath
108 XQuery 1.0: An XML Query Language. http://www.w3c.org/TR/xquery
109 XSL Transformations (XSLT) Version 1.0. http://www.w3c.org/TR/xslt
110 M. Benedikt, W. Fan, G. Kuper. Structural Properties of XPath Fragments.Theoretical Computer Science. 2005, 336(1):3–31
111 S. Amer-Yahia, S. Cho, L. V. S. Lakshmanan, et al. Tree Pattern Query Mini-mization. The VLDB Journal. 2002, 11(4):315–331
112 Universal Description, Discovery and Integration of Business for theWeb(UDDI). http://uddi.xml.org/uddi-org
113 A. Bru¨ggemann-Klein, D. Wood. One-unambiguous Regular Languages. In-formation and Computation. 1998, 142(2):182–206
114 W. Martens. Static Analysis of XML Transformation and Schema Languages.University of Limburg, Ph.D. thesis. 2006
115 T. J. Green, A. Gupta, G. Miklau, et al. Processing XML Streams with Deter-ministic Automata and Stream Indexes. ACM Transactions on Database Sys-tems. 2004, 29(4):752–788
116高军,杨冬青,唐世谓,等.一种XML数据流之上持续查询执行器的增量维护方法.计算机研究与发展. 2005, 42(5):771–776
117 Y. Papakonstantinou, V. Vianu. DTD Inference for Views of XML Data. PODS’00: Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART sympo-sium on Principles of database systems, Dallas, Texas, USA. New York, NY,USA: ACM Press, 2000:35–46
118 J. E. Hopcroft, R. Motwani, J. D. Ullman. Introduction to Automata Theory,Languages, and Computation. second edn. Beijing: Tsinghua University Press,2002, 46–66
119 A. Tozawa, M. Hagiya. XML Schema Containment Checking Based on Semi-implicit Techniques. Implementation and Application of Automata, 8th Inter-national Conference, Santa Barbara, CA, USA. 2003:213–225
120 H. Seidl. Deciding Equivalence of Finite Tree Automata. SIAM Journal ofComputing. 1990, 19(3):424–437
121 H. Seidl. Haskell Overloading is DEXPTIME-complete. Information Process-ing Letters. 1994, 52(2):57–60
122 L. J. Stockmeyer, A. R. Meyer. Word Problems Requiring ExponentialTime(preliminary Report). STOC’73: Proceedings of the fifth annual ACMsymposium on Theory of computing, Austin, Texas, USA. New York, NY,USA: ACM, 1973:1–9
123 W. Fan, L. Libkin. On XML Integrity Constraints in the Presence of DTDs.Journal of the ACM. 2002, 49(3):368–406
124 T. Milo, D. Suciu. Type Inference for Queries on Semistructured Data. PODS’99: Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART sympo-sium on Principles of database systems. New York, NY, USA: ACM, 1999:215–226125 D. Barbosa, A. O. Mendelzon, J. Keenleyside, et al. Toxgene: An ExtensibleTemplate-based Data Generator for XML. WebDB2002: Fifth InternationalWorkshop on the Web and Databases, Madison, Wisconsin. New York, NY,USA: ACM Press, 2002:49–54
126 Apache Org. http://xml.apache.org/xalan-j
127 M. Arenas, L. Libkin. A Normal Form for XML Documents. ACM Transactionson Database Systems. 2004, 29(1):195–232
128 SAX 2.0.2: The Simple API for XML. http://www.saxproject.org/
129 Document Object Model (DOM) Level 3 Validation Specification. http://www.w3.org/TR/2004/REC-DOM-Level-3-Val-20040127/