The Active XML project: an overview

This paper provides an overview of the Active XML project developed at INRIA over the past five years. Active XML (AXML, for short), is a declarative framework that harnesses Web services for distributed data management, and is put to work in a peer-to-peer architecture. The model is based on AXML documents, which are XML documents that may contain embedded calls to Web services, and on AXML services, which are Web services capable of exchanging AXML documents. An AXML peer is a repository of AXML documents that acts both as a client by invoking the embedded service calls, and as a server by providing AXML services, which are generally defined as queries or updates over the persistent AXML documents. The approach gracefully combines stored information with data defined in an intensional manner as well as dynamic information. This simple, rather classical idea leads to a number of technically challenging problems, both theoretical and practical. In this paper, we describe and motivate the AXML model and language, overview the research results obtained in the course of the project, and show how all the pieces come together in our implementation. The first and third authors were partially funded by the European Project Edos. Work done when the second and third authors were at INRIA. Work done when the second and third authors were at INRIA.     

Active XML文档有效性检验

文档有效性检验是XML领域的一个基本问题.Active XML(AXML)文档在XML文档中引入Web服务,传统用于解决XML文档有效性的检验方法并不适用于AXML文档,为文档有效性检验提出了新的挑战.研究了AXML文档有效性检验问题,在原始树自动机的基础上,定义了AXML模式树自动机-ASTA机,该树自动机能够有效地描述满足AXML模式约束的文档集合.基于ASTA机,提出了一种多项式时间的AXML文档有效性检验算法.实验数据表明,基于提出的算法能够有效的完成对AXML文档的有效性检验.     

On the improvement of active XML (AXML) representation and query evaluation

Active XML (AXML) as intensional data aims to exploit potential computing powers of XML, Web services and P2P architecture. It is considered a powerful extension of XML to deal with dynamic XML data from autonomous and heterogeneous data sources on a very large scale via Web services. However, AXML is still at an immature stage and various issues need to be investigated before it can be accepted widely. This paper will focus on two issues facing the current AXML system, namely the representation and the query process. We propose superior representation and improved query evaluation for AXML. For justification purposes, we compare our proposed algorithms with the existing algorithms.     

利用关系表构建XML文档解析的树模型

在对XML文档的数据解析和查询操作研究中,发现树能较好地反映XML文档的层次结构,但其查询效率较低,而关系表是一种适合存储大量数据且有较好查询效率与操作功能的数据结构。给出了一个把树和关系表相结合构建一种存储XML文档的数据模型;在这个模型的解析过程中,采用回调事件式的分段解析方法以减少解析时间和存储空间。这样既能较好保存XML文档的结构特点,又能提高其查询的效率和操作的便利性。通过对大数据量XML文档的解析和操作实验,实验结果证明这种数据模型在处理大型XML文档中具有明显优势。     

Query optimization in XML structured-document databases

While the information published in the form of XML-compliant documents keeps fast mounting up, efficient and effective query processing and optimization for XML have now become more important than ever. This article reports our recent advances in XML structured-document query optimization. In this article, we elaborate on a novel approach and the techniques developed for XML query optimization. Our approach performs heuristic-based algebraic transformations on XPath queries, represented as PAT algebraic expressions, to achieve query optimization. This article first presents a comprehensive set of general equivalences with regard to XML documents and XML queries. Based on these equivalences, we developed a large set of deterministic algebraic transformation rules for XML query optimization. Our approach is unique, in that it performs exclusively deterministic transformations on queries for fast optimization. The deterministic nature of the proposed approach straightforwardly renders high optimization efficiency and simplicity in implementation. Our approach is a logical-level one, which is independent of any particular storage model. Therefore, the optimizers developed based on our approach can be easily adapted to a broad range of XML data/information servers to achieve fast query optimization. Experimental study confirms the validity and effectiveness of the proposed approach.     

Active XML文档安全重写判定算法

研究了AXML文档安全重写判定问题,即判定给定AXML文档通过触发其包含的服务调用生成的文档集合是否能够全部重写为符合目标模式的文档实例.基于树自动机理论,定义了用于抽象AXML文档的树自动机--ATA机(AXML treeautomata),ATA机等价于给定AXML文档通过触发其包含的服务调用所能生成的文档集合.基于ATA机,提出一个AXML文档安全重写判定算法,表明了该算法的正确性及有效性.     

Native XML数据库XSQS查询处理系统的设计与实现

XML已经成为互联网中数据表示和数据交换事实上的标准.实现专门对于XML数据的有效存储和查询变得十分重要.报告了当前NativeXML数据库在国内外的发展情况,讨论了一种NativeXML数据库管理系统原型XSQS的功能及概要设计.系统采用了基于压缩表的存储方式和索引结构,采用了基于结果集的查询处理方法.重点讨论了系统查询处理部分的设计及实现.实践结果表明,这种存储索引结构和查询方式相结合,使系统在查询效率上有了显著的提高.     

Active XML文档物化终止性检验算法

Active XML（简记为AXML）文档在XML文档中引入嵌入式Web服务,通过调用这些服务,来获取相应的内涵信息,为AXML文档物化过程。研究了AXML文档物化的终止性检验问题,提出了多项式时间的检验算法,该算法通过构造AXML模式依赖图,检验其无环性来判定AXML文档物化终止性问题,证明了算法的正确性和有效性。     

一种Active XML模式重写算法

基于树自动机理论,研究了Active xML(简记为AXML)模式重写问题,提出了一种多项式时间的AXML模式重写判定算法,并对算法进行了实现.实验结果证明了所提算法用于判定AXML模式重写的优越性.     

基于XML数据的通用路径表达式的查询

查询重写是数据库研究的一个基本问题,它和查询优化、数据仓库、数据集成、语义缓存等数据库问题密切相关。同时,查询重写也是在关系数据库中存储和查询XML数据的关键问题。由于XML数据是元素嵌套和元素引用的,嵌套层数可以任意,并且模式和数据混合,因此XML的查询会涉及到广义路径表达式(GPE)。文中着重研究了如何解决XML数据的查询重写的方案,把含有广义路径表达式的XML查询语句重写为含有简单路径表达式(SPE)的XML查询语句,再转化为基于关系数据库的SQL语句。     

ELCA evaluation for keyword search on probabilistic XML data

As probabilistic data management is becoming one of the main research focuses and keyword search is turning into a more popular query means, it is natural to think how to support keyword queries on probabilistic XML data. With regards to keyword query on deterministic XML documents, ELCA (Exclusive Lowest Common Ancestor) semantics allows more relevant fragments rooted at the ELCAs to appear as results and is more popular compared with other keyword query result semantics (such as SLCAs). In this paper, we investigate how to evaluate ELCA results for keyword queries on probabilistic XML documents. After defining probabilistic ELCA semantics in terms of possible world semantics, we propose an approach to compute ELCA probabilities without generating possible worlds. Then we develop an efficient stack-based algorithm that can find all probabilistic ELCA results and their ELCA probabilities for a given keyword query on a probabilistic XML document. Finally, we experimentally evaluate the proposed ELCA algorithm and compare it with its SLCA counterpart in aspects of result probability, time and space efficiency, and scalability.     

IXMDB：RDBMS中XML数据的一种全新存储模式

在RDBMS中存储XML数据有两种模式：Schema-conscious和Schema-oblivious。Schema-conscious模式不支持复杂的X-Path查询,Schema-oblivious模式在类型描述和访问过程中缺少灵活性。本文为MPEG-7文档提出了一个全新的存储方法：IXMDB。IXMDB吸取了Schema-conscious和Schema-oblivious的优点。同时避免了它们的主要缺点。IXMDB还为特殊数据类型提供了专门的存储机制。     

基于形式语言理论的Active XML重写算法

主动XML（AXML）是指一部分数据直接给出,另一部分数据以Web Services调用方式隐含给出XML文档。研究AXML重写问题,给出AXML重写系统的形式化定义,提出一个基于树自动机理论的AXML文档重写算法,并证明该算法的正确性及有效性。实验数据表明,基于树自动机的AXML文档交换方法具有良好的执行效率。     

RDBMS中层次查询结果的XML文档生成

数据库应用系统中相当多的数据都呈现出相应的层次特征,对这类数据,常常需要生成元素间保持层次特征的XML文档,用一般的查询机制来解决这个问题比较繁琐,以Oracle9i数据库第2版为例,应用层次查询,并结合OracleXML DB,对层次查询结果相对应的保持层次特征的XML文档的生成机制进行了研究,并将其应用于税务信息综合查询系统之中.结果表明,该方法简单、效率高、应用效果良好.     

基于编码的XML关系数据库存储

在XML的发展过程中,如何有效地利用关系数据库技术存储和查询XML数据已经成为一个研究热点．提出了一种基于前、后序编码的XML关系数据库存储方法,该方法采用的模式映射方法能够使基于不同DTD（或schema）的XML文档保存在同一个关系表中,支持快速的XML路径查询,且具有较高的XML文档重组效率．对该方法中递归模式的处理技术也进行了讨论．实验表明,与XRel,Florescu和Kossman等人提出的XML关系数据库存储方法相比,该方法能够缩短复杂XML路径查询（如带条件谓词约束的路径查询）的响应时间．     

XN-Store:一种原生XML数据库的存储方案

随着XML相关标准的推广与应用,Web上出现了大量的XML文档,为了进行有效的管理,有必要将XML文档存储到数据库中,存储方案已成为XML数据管理领域研究的一个重要课题,将XML文档映射为关系表,存储到传统的RDBMS中,会破坏XML数据的树形结构,造成查询效率的下降,提出了一种新的用于原生XML数据库的存储方案--XN-Store,该方案基于索引结构将XML节点作为记录直接存储到分页文件中,建立起持久化文档对象模型,从而保持了XML数据原有的树形结构.XN-Store不仅降低了XML文档的存储空间开销,而且实现了XML节点的快速串行化输出和访问操作.作为通用的原生XML存储方案,XN-Store支持各种二级索引的创建,以提高XML查询处理的效率,采用多种数据集,分别在XN-Store和先前的XML存储系统上进行实验,比较存储空间、存储时间、串行化时间和节点访问时间.实验结果表明,XN-Store是一种高性能的原生XML数据库存储方案.     

Efficiently Querying Large XML Data Repositories: A Survey

Extensible markup language (XML) is emerging as a de facto standard for information exchange among various applications on the World Wide Web. There has been a growing need for developing high-performance techniques to query large XML data repositories efficiently. One important problem in XML query processing is twig pattern matching, that is, finding in an XML data tree D all matches that satisfy a specified twig (or path) query pattern Q. In this survey, we review, classify, and compare major techniques for twig pattern matching. Specifically, we consider two classes of major XML query processing techniques: the relational approach and the native approach. The relational approach directly utilizes existing relational database systems to store and query XML data, which enables the use of all important techniques that have been developed for relational databases, whereas in the native approach, specialized storage and query processing systems tailored for XML data are developed from scratch to further improve XML query performance. As implied by existing work, XML data querying and management are developing in the direction of integrating the relational approach with the native approach, which could result in higher query processing performance and also significantly reduce system reengineering costs.     

Principles of Holism for sequential twig pattern matching

Modern applications face the challenge of dealing with structured and semi-structured data. They have to deal with complex objects, most of them presenting some kind of internal structure, which often forms a hierarchy. Though XML documents are the most known, chemical compounds, CAD drawings, web-sites and many other applications have to deal with similar problems. In such environments, ordered and unordered tree pattern matching are the fundamental search operations. One of the main thrusts of research activities for tree pattern matching is the class of holistic approaches. Their ultimate goal is to evaluate a query twig as a whole by relying on sequential access patterns and non trivial auxiliary storage structures, typically stored in main memory. Based on the pre/post-order ranks of individual tree nodes, we establish strong theoretical bases as a foundation for correct and efficient holistic pattern matching algorithms. In particular, we define and prove sufficient and necessary conditions to minimize the amount of data retained in memory, thus introducing a correct and complete framework on which different holistic solutions can be compared. We also show how these rules can be applied for building algorithms for ordered and unordered tree-pattern matching. Thanks to the above theoretical achievements, each holistic algorithm gains in efficiency as it is directly implemented on the adopted numbering scheme, avoids expensive matching refinements and keeps memory requirements stable. An experimental analysis and comparison with previous approaches confirms the superiority of our approach tested on synthetic as well as real-life data sets.     

用XML对数据库查询的方法

本文讨论了用ＸＭＬ查询数据库的具体实现方法。首先,提出了用ＤＴＤ描述关系数据模式和利用ＡＳＰ技术转化数据库的数据成ＸＭＬ文档方法;然后,用ＸＭＬ的查询语言ＸＭＬ－ＱＬ完成Ｗｅｂ数据库上查询和数据集成等操作。     

XML数据的B树存储实现及更新

XML正逐渐成为 WWW数据表示和交换的标准 ,如何有效实现对于 XML数据的存储、查询及更新等操作是 XML 相关技术研究中的一个重要领域。本文首先简要介绍了我们的基于模式匹配的 XML 数据库系统 (DISXDBS)组成 ;然后研究了如何实现用 B树存储 XML 文档以及对其进行查询、更新等操作 ;最后与目前存在的几种 XML 文档的存储策略进行比较。