Efficiently supporting order in XML query processing

XML is an ordered data model and XQuery expressions return results that have a well-defined order. However, little work on how order is supported in XML query processing has been done to date. In this paper we study the issues related to handling order in the XML context, namely challenges imposed by the XML data model, the variety of order requirements of the XQuery language, and the need to maintain order in the presence of updates to the XML data. We propose an efficient solution that addresses all these issues. Our solution is based on a key encoding for XML nodes that serves as node identity and at the same time encodes order. We design rules for encoding order of processed XML nodes based on the XML algebraic query execution model and the node key encoding. These rules do not require any actual sorting for intermediate results during execution. Our approach enables efficient order-sensitive incremental view maintenance as it makes most XML algebra operators distributive with respect to bag union. We prove the correctness of our order encoding approach. Our approach is implemented and integrated with Rainbow, an XML data management system developed at WPI. We have tested the efficiency of our approach using queries that have different order requirements. We have also measured the relative cost of different components related to our order solution in different types of queries. In general the overhead of maintaining order in our approach is very small relative to the query processing time.     

The XML Tree Model – toward an XML conceptual schema reversed from XML Schema Definition

XML Schema Definition (XSD) is the logical schemas of an XML model, but there is no standard format for the conceptual schema of an XML model. Therefore, we propose an XML Tree Model (XTM) as an XML conceptual schema for representing data semantics in a diagram, and also as an XML data model validator for confirming the data semantics required by users. An XTM consists of hierarchical nodes representing all the elements, and the data relationships among elements within the XSD. A rule-based algorithm and an information capacity with pre- and post-conditions are developed as the methodology for reverse engineering. The proposed algorithm consists of two rules: General Information Transformation and Data Semantic Recovering to construct an XTM. Users can draw an XTM with data relationships among elements as a result of the reverse engineering.     

Rule-based XML

Legal contracts and litigation documents common to the American legal system were encoded in the eXtensible Markup Language (XML). XML also represents rules about the contracts and litigation procedure. In addition to an expert system tool that allows one to make inferences with that engine, a Graphical User Interface (GUI) generates the XML representing the rules. A rulebase is developed by marking up examples of the XML to be interpreted and the XML to be generated, analogously to Query By Example. This article provides a broader context of the synergy between XML and artificial intelligence by including discussions of: (1) the role of Artificial Intelligence in handling routine litigation; (2) how the use of XML enables legal expert systems to get their `input' without the user having to enter the same information again for the expert system;(3) the advantages of XML markup over other forms of markup for documents; (4) the relationship between XML and ontologies; (5) other projects using XML with rules or legal affairs.     

Distributed Reactive XML

XML-centric models of computation have been proposed as an answer to the demand for interoperability, heterogeneity and openness in coordination models. We present a prototype implementation of an open XML-centric coordination middleware called Distributed Reactive XML. The middleware has as theoretical foundation a general distributed extensible process calculus inspired by the theory of Bigraphical Reactive Systems. The calculus is extensible just as XML is extensible, in that its signature and reaction rules are not fixed. It is distributed by allowing both the state of processes as well as the set of reaction rules to be distributed (or partly shared) between different clients. The calculus is implemented by representing process terms as XML documents stored in a value-oriented, peer-to-peer XML Store and reaction rules as XML transformations performed by the clients. The formalism does not require that only process terms are stored—inside process terms one may store application specific data as well. XML Store provides transparent sharing of process terms between all participating peers. Conflicts between concurrent reaction rules are handled by an optimistic concurrency control. The implementation thus provides an open XML-based coordination middleware with a formal foundation that encompasses both the shared data, processes and reaction rules.     

Studying the XML Web: Gathering Statistics from an XML Sample

XML has emerged as the language for exchanging data on the web and has attracted considerable interest both in industry and in academia. Nevertheless, to date, little is known about the XML documents published on the web. This paper presents a comprehensive analysis of a sample of about 200,000 XML documents on the web, and is the first study of its kind. We study the distribution of XML documents across the web in several ways; moreover, we provided a detailed characterization of the structure of real XML documents. Our results provide valuable input to the design of algorithms, tools and systems that use XML in one form or another. An erratum to this article is available at .     

基于XML数据的关联规则挖掘研究

XML凭借其诸多优点,在短短的时间内迅速成为表示和交换信息的标准。大量XML数据的涌现给数据挖掘提出了新的挑战。传统关联规则挖掘是基于关系数据库的,因此现有许多XML数据关联规则挖掘的方法都或多或少地利用关系数据库-即把XML数据文档映射成关系数据库来完成的。在仔细研究了XML数据的访问接口后,给出了一个基于Apriori算法可直接从XML文档挖掘关联规则的类接口,并且在．NET平台下用C#语言实现了。     

Integrating E-Business XML Business Forms and Rule-Based Agent Technologies

This study investigates the role of extensible mark-up language (XML) business forms and agent-based computing to support negotiation, management and implementation of inter-organization business processes. We explore recently proposed standards for representing artificial agent exchanges through rule-based inference. An XML representational syntax for standard business forms is developed and applied to augment rule-based agents. A prototype investigates ways to combine knowledge-based agents and business forms to assist business and customers in Web-based conference registration. The implementation helps guide customer decisions and the combination of business forms and rules promotes understandability, testability and adaptability of the registration system.     

Interfacing environmental simulation models and databases using XML

Typically in environmental management tasks one needs to examine and explore data from several sources, use simulation models, develop scenarios, assess impacts, and provide support for decision makers. Here we consider the eXtensible Markup Language (XML) standard in developing information transfer techniques between databases and simulation models. Suitability of XML as the agreed data transfer format is studied in a sample application, where two snow models of different complexity are linked with input data extracted from a relational database. The simple case study demonstrated that with free and easily accessible tools it was relatively straightforward to develop an XML interface between a meteorological data set and simulation models. Based on the case study, a structure for a more comprehensive system comprising model and data resources, and a broker application that acts as an intermediate between the user and those resources, is presented. We believe that such an XML-based structure is worth exploring on the track towards an open modelling framework. Such a framework would allow models developed by various expert groups to connect easily to a common information system.     

基于XML的软件安全静态检测方法研究

安全关键软件设计使用的C/C++语言含有大量未定义行为,使用不当可能产生重大安全隐患。软件静态检测是从软件代码和结构中找出安全缺陷的重要手段。从安全规则的角度,提出了基于XML（eXtensible Markup Language）中间模型的静态检测方法。该方法将C/C++源代码解释为XML中间模型,将安全规则转化为缺陷模式,利用Xquery查询表达式对软件安全缺陷进行定位。基于该方法的原型系统检验结果表明：该方法能够有效地检测出违反安全规则的软件缺陷,并具有安全规则可定制的特点。     

Constructing ontologies by mining deep semantics from XML Schemas and XML instance documents

With the development of the Semantic Web and Artificial Intelligence techniques, ontology has become a very powerful way of representing not only knowledge but also their semantics. Therefore, how to construct ontologies from existing data sources has become an important research topic. In this paper, an approach for constructing ontologies by mining deep semantics from eXtensible Markup Language (XML) Schemas (including XML Schema 1.0 and XML Schema 1.1) and XML instance documents is proposed. Given an XML Schema and its corresponding XML instance document, 34 rules are first defined to mine deep semantics from the XML Schema. The mined semantics is formally stored in an intermediate conceptual model and then is used to generate an ontology at the conceptual level. Further, an ontology population approach at the instance level based on the XML instance document is proposed. Now, a complete ontology is formed. Also, some corresponding core algorithms are provided. Finally, a prototype system is implemented, which can automatically generate ontologies from XML Schemas and populate ontologies from XML instance documents. The paper also classifies and summarizes the existing work and makes a detailed comparison. Case studies on real XML data sets verify the effectiveness of the approach.     

Active rules for XML: A new paradigm for E-services

XML is rapidly becoming one of the most widely adopted technologies for information exchange and representation. As the use of XML becomes more widespread, we foresee the development of active XML rules, i.e., rules explicitly designed for the management of XML information. In particular, we argue that active rules for XML offer a natural paradigm for the rapid development of innovative e-services. In the paper, we show how active rules can be specified in the context of XSLT, a pattern-based language for publishing XML documents (promoted by the W3C) which is receiving strong commercial support, and Lorel, a query language for XML documents that is quite popular in the research world. We demonstrate, through simple examples of active rules for XSLT and Lorel, that active rules can be effective for the implementation of e-commerce services. We also discuss the various issues that need to be considered in adapting the notion of relational triggers to the XML context. Received: 30 October 2000 / Accepted: 19 December 2000 Published online: 27 April 2001     

A multi-ranker model for adaptive XML searching

The evolution of computing technology suggests that it has become more feasible to offer access to Web information in a ubiquitous way, through various kinds of interaction devices such as PCs, laptops, palmtops, and so on. As XML has become a de-facto standard for exchanging Web data, an interesting and practical research problem is the development of models and techniques to satisfy various needs and preferences in searching XML data. In this paper, we employ a list of simple XML tagged keywords as a vehicle for searching XML fragments in a collection of XML documents. In order to deal with the diversified nature of XML documents as well as user preferences, we propose a novel multi-ranker model (MRM), which is able to abstract a spectrum of important XML properties and adapt the features to different XML search needs. The MRM is composed of three ranking levels. The lowest level consists of two categories of similarity and granularity features. At the intermediate level, we define four tailored XML rankers (XRs), which consist of different lower level features and have different strengths in searching XML fragments. The XRs are trained via a learning mechanism called the Ranking Support Vector Machine in a voting Spy Naïve Bayes framework (RSSF). The RSSF takes as input a set of labeled fragments and feature vectors and generates as output Adaptive Rankers (ARs) in the learning process. The ARs are defined over the XRs and generated at the top level of the MRM. We show empirically that the RSSF is able to improve the MRM significantly in the learning process that needs only a small set of training XML fragments. We demonstrate that the trained MRM is able to bring out the strengths of the XRs in order to adapt different preferences and queries.     

基于XML数据的FP-growth算法挖掘研究

XML是跨平台的数据表示、交换技术,由于其本身在自描述性、开放性等方面的优势,在短短的时间内迅速成为行业标准。大量XML数据的涌现给数据挖掘提出了新的挑战。传统关联规则挖掘是基于关系数据库的,即把XML数据文档映射成关系数据库来完成。给出一个使用FP-growth算法直接从XML文档挖掘关联规则的类接口,并且在J2EE平台下用Java语言实现。     

XML文档中时态信息存储方法的研究与比较

XML作为Web上新的数据发布语言,将成为web下一代"数据表达"和"数据交换"的统一标准.然而XML文档很少是静止的,它经常会被修改.引入"时态表达"后,时态XML文档能够记录一系列的修改痕迹以及数据的变化过程.本文提出了将双时态XML数据模型映射到双时态XML文档的四种映射方法,最后通过实验对比了这些映射方法及其适用场合.     

Static analysis of XML transformations in Java

XML documents generated dynamically by programs are typically represented as text strings or DOM trees. This is a low-level approach for several reasons: 1) traversing and modifying such structures can be tedious and error prone, 2) although schema languages, e.g., DTD, allow classes of XML documents to be defined, there are generally no automatic mechanisms for statically checking that a program transforms from one class to another as intended. We introduce XACT, a high-level approach for Java using XML templates as a first-class data type with operations for manipulating XML values based on XPath. In addition to an efficient runtime representation, the data type permits static type checking using DTD schemas as types. By specifying schemes for the input and output of a program, our analysis algorithm will statically verify that valid input data is always transformed into valid output data and that the operations are used consistently.     

基于RDBMS的XML数据管理技术研究

XML是一种专门为Internet所设计的标记语言,但是它已逐渐成为Internet上数据表示以及数据交换的标准,是一种发展势头良好的新兴数据管理手段.关系数据库管理系统(RDBMS)是一种技术成熟、应用十分广泛的系统.在数据管理上,XML技术和数据库技术各有优势和不足,XML和数据库结合技术成为学术界的研究热点.在对XML和数据库结合技术进行了研究的基础上一个基于RDBMS的XML数据管理的实现框架(XRM)被提出,该框架依据不同的映射策略,解析Schema文件或DTD,生成对应的关系模式,利用RDBMS存储中间件,使用户能透明地通过RDBMS来管理XML数据.该框架充分考虑了结构的灵活性和扩展性.     

基于语义对象的XML Schema数据建模

语义对象模型是把语义看作基本出发点,用来文档化用户需求并建立数据模型的。利用语义对象模型来获得XML Schema,或将语义对象模型作为关系数据模型向XML Schema转换的中介,有利于尽可能多地保留数据的语义信息。文章提出了利用语义对象的XML Schema数据建模的一些基本规则和方法。     

支持XML查询代数和树模式查询的XQuery系统框架

XQuery语言的高性能实现需要利用XML查询代数提供的查询优化方法,也需要采取高效的树模式整体匹配算法。为了将这两种XML查询处理技术有效地结合在XQuery语言处理系统中,提出了一种通用系统框架来支持XQuery语言的高性能实现。在这个框架内,提供开放式XML数据源连接,并且通过作为中间语言的一种函数式查询计划描述语言FXQL来支持各种查询代数算子和树查询模式的表示,既允许采用各种XML查询代数,又允许采用各种树模式查询算法;进而,通过这种中间层的程序变换可以实现基于各种查询代数的查询重写,并从查询计划中分离出独立的树模式查询计算,使两种查询处理技术适当地统一在同一系统框架中,有效地支持了多种环境下XQuery语言的实现。