Foundations of Fast Communication via XML

Communication with XML often involves pre-agreed document types. In this paper, we propose an offline parser generation approach to enhance online processing performance for documents conforming to a given DTD. Our examination of DTDs and the languages they define demonstrates the existence of ambiguities. We present an algorithm that maps DTDs to deterministic context-free grammars defining the same languages. We prove the grammars to be LL(1) and LALR(1), making them suitable for standard parser generators. Our experiments show the superior performance of generated optimized parsers. Our results generalize from DTDs to XML schema specifications with certain restrictions, most notably the absence of namespaces, which exceed the scope of context-free grammars.     

SGML支持系统及DTD编辑器的设计模型

标准通用费标语言是用来标记文件逻辑结构的语言。ＳＧＧＭＬ支持系统是帮助用户编辑符合ＳＧＭＬ语法规范的ＳＧＭＬ文件，它包括了ＤＴＤ编辑器和语法制惆的ＳＧＭＬ文件编辑器。     

Clustering DTDs: An Interactive Two-Level Approach

XML（eXtensible Markup Language)is a standard which is widely applied in data representation and data exchange,However,as an important concept of XML,DTD(Document Type Definition)is not taken full advantage in current applications.In this paper,a new method for clustering DTDs is presented.and it can be used in XML document clustering.The two-level method clusters the elements in DTDs and clusters DTDs separately.Element clustering forms the first level and provides element clusters,which are the generalization of relevant elements.DTD clustering utilizes the generalized information and forms the second level in the whole clustering process.The two-level method has the following advantages:1) It takes into consideration both the content and the structure within DTDs;2) The generalized information about elements is more useful than the separated words in the vector model;3) The two-level method facilitates the searching of outliers.The experiments show that this method is able to categorize the relevant DTDs effectively.     

Typechecking for XML transformers

We study the typechecking problem for XML (eXtensible Markup Language) transformers: given an XML transformation program and a DTD for the input XML documents, check whether every result of the program conforms to a specified output DTD. We model XML transformers using a novel device called a k-pebble transducer, that can express most queries without data-value joins in XML-QL, XSLT, and other XML query languages. Types are modeled by regular tree languages, a robust extension of DTDs. The main result of the paper is that typechecking for k-pebble transducers is decidable. Consequently, typechecking can be performed for a broad range of XML transformation languages, including XML-QL and a fragment of XSLT.     

一个DTD 比较工具及实例分析

提出了一种找出不同XML语法间差别的方法，基于此方法开发了一种叫做DTD—Comparer的原型工具。应用实例表明，通过此工具可以有效得到XML语言的语法之间的差别，以减少不同XML应用系统间信息交换过程中的数据丢失。     

XML弱函数依赖及其推理规则

XML函数依赖问题是进行XML数据库后续研究的基础。首先基于M.Arenas等人给定的XML中DTD和XML树的定义,提出空值、不完全树元组、数据值偏序、最小扩展树等概念,在此基础上,给出弱函数依赖及其满足性的定义;其次研究了XML弱函数依赖的逻辑蕴含问题,提出一组适合XML空值模型的函数依赖推理规则集;最后给出推理规则集的正确性和完备性证明。     

Mapping DTDs to relational schemas with semantic constraints

XML is becoming a prevalent format and standard for data exchange in many applications. With the increase of XML data, there is an urgent need to research some efficient methods to store and manage XML data. As relational databases are the primary choices for this purpose considering their data management power, it is necessary to research the problem of mapping XML schemas to relational schemas. The semantics of XML schemas are crucial to design, query, and store XML documents and functional dependencies are very important representations of semantic information of XML schemas. As DTDs are one of the most frequently used schemas for XML documents in these days, we will use DTDs as schemas of XML documents here. This paper proposes the concept and the formal definition of XML functional dependencies over DTDs. A method to map XML DTDs to relational schemas with constraints such as functional dependencies, domain constraints, choice constraints, reference constraints, and cardinality constraints over DTDs is given, which can preserve the structures of DTDs as well as the semantics implied by the above constraints over DTDs. The concepts and method of mapping DTDs to relational schemas presented in the paper can be extended to the field of XML Schema just with some modifications in related formal definitions.     

一种DTD到关系模式的映射方法

现有的XML到关系数据的映射算法没有充分考虑DTD中所蕴涵的语义，如果DTD中蕴含函数依赖，在映射到关系数据库时应考虑DTD中的函数依赖，基于Inlining算法，考虑DTD中蕴含的函数依赖，提出了一种既能保持XML文档的内容和结构，又能保持函数依赖的从XML到关系数据模型的映射方法。     

基于XML的数据交换与存取技术研究

可扩展置标语言XML(eXtensibleMarkupLanguage)是由W3C(WorldWideWebConsortium)组织于1998年2月制定的一种面向Internet应用的置标语言。作为对SGML(标准通用置标语言)的一种改良,XML具有良好的扩展性和自描述性、形式与内容分离、遵循严格的语法要求以及提供对多语种的支持等特点,使其成为Internet网上发布与数据交换的一门新兴技术,并有望在跨平台跨地域异构应用间的协同工作、基于语义的智能数据搜索等领域发挥重要作用。所有这些应用都又和XML的数据存取机制分不开的。基于上述种种原因,近年来,基于XML的数据交换与存取技术成为数据交换和存取领域的一项重要课题,并引起广泛关注。文章将此技术展开分析,详细探讨了XML数据存取机制,并结合关系型数据库和面向对象数据库,重点分析了XML在数据库中的存储模式和应用模式,最后对XML数据存取技术的发展趋势进行了展望。     

XML在电子商务中的应用

介绍可扩展标记语言XML,并与标准通用标记语言SGML及超文本标记语言HTML进行了比较,说明XML的优势,阐述XML在电子商务中的应用.     

Structural and semantic aspects of similarity of Document Type Definitions and XML schemas

The natural optimization strategy for XML-to-relational mapping methods is exploitation of similarity of XML data. However, none of the current similarity evaluation approaches is suitable for this purpose. While the key emphasis is currently put on semantic similarity of XML data, the main aspect of XML-to-relational mapping methods is analysis of their structure.In this paper we propose an approach that utilizes a verified strategy for structural similarity evaluation - tree edit distance - to DTD constructs. This approach is able to cope with the fact that DTDs involve several types of nodes and can form general graphs. In addition, it is optimized for the specific features of XML data and, if required, it enables one to exploit the semantics of element/attribute names. Using a set of experiments we show the impact of these extensions on similarity evaluation. And, finally, we discuss how this approach can be extended for XSDs, which involve plenty of “syntactic sugar”, i.e. constructs that are structurally or semantically equivalent.     

格值树自动机与格值上下文无关树文法的等价性

本文将模糊树自动机和模糊上下文无关树文法的概念推广到格半群上。证明了在接受语言和生成语言的意义下,树自动机和上下文无关树文法是等价的。同时给出了构造正规形式的等价文法的方法。     

基于上下文的异构文档类型定义匹配

XML文档的模式匹配是许多应用中的重要步骤．提出一种匹配算法来发现不同DTD中对应的元素和属性，通过转化规则将DTD转化成一个有向图模型，先给出了两个DTD树之间的匹配算法，然后将其推广一般的DTD图匹配的情形．匹配算法中在考察DTD节点的相似性时，除考虑标签语义和基数约束之外，研究了上下文语义对节点相似性的影响．     

A practical approach to extracting DTD-conforming XML documents from heterogeneous data sources

XML documents are becoming popular for business process integration. To achieve interoperability between applications, XML documents must also conform to various commonly used data type definitions (DTDs). However, most business data are not maintained as XML documents. They are stored in various native formats, such as database tables or LDAP directories. Hence, a middleware is needed to dynamically generate XML documents conforming to predefined DTDs from various data sources. As industrial consortia and large corporations have created various DTDs, it is both challenging and time-consuming to design the necessary middleware to conform to so many different DTDs. This problem is particularly acute for a small- or medium-sized enterprise because it lacks the IT skills to quickly develop such a middleware. In this paper, we present XLE, an XML Lightweight Extractor, as a practical approach to dynamically extracting DTD-conforming XML documents from heterogeneous data sources. XLE is based on a framework called DTD source annotation (DTDSA). It treats a DTD as the control structure of a program. The annotations become the program statements, such as functions and assignments. DTD-conforming XML documents are generated by parsing annotated DTDs. Basically, DTD annotations describe declaratively the mappings between target XML documents and the source data. The XLE engine implements a few basic annotations, providing a practical solution for many small- and medium-sized enterprises. However, XLE is designed to be versatile. It allows sophisticated users to plug in their own implementations to access new types of data or to achieve better performance. Heterogeneous data sources can be simply specified in the annotations. A GUI tool is provided to highlight the places where annotations are needed.     

Representing and Reasoning About XML with Ontologies

The eXtensible Markup Language (XML) has reached a wide acceptance as the relevant standardization for representing and exchanging data on the Web. Unfortunately, XML covers the syntactic level but lacks semantics, and thus cannot be directly used for the Semantic Web. Currently, finding a way to utilize XML data for the Semantic Web is challenging research. As we have known that ontology can formally represent shared domain knowledge and enable semantics interoperability. Therefore, in this paper, we investigate how to represent and reason about XML with ontologies. Firstly, we give formalized representations of XML data sources, including Document Type Definitions (DTDs), XML Schemas, and XML documents. On this basis, we propose formal approaches for transforming the XML data sources into ontologies, and we also discuss the correctness of the transformations and provide several transformation examples. Furthermore, following the proposed approaches, we implement a prototype tool that can automatically transform XML into ontologies. Finally, we apply the transformed ontologies for reasoning about XML, so that some reasoning problems of XML may be checked by the existing ontology reasoners.     

Formal properties of XML grammars and languages

We consider XML documents described by a document type definition (DTD). An XML-grammar is a formal grammar that captures the syntactic features of a DTD. We investigate properties of this family of grammars. We show that every XML-language basically has a unique XML-grammar. We give two characterizations of languages generated by XML-grammars, one is set-theoretic, the other is by a kind of saturation property. We investigate decidability problems and prove that some properties that are undecidable for general context-free languages become decidable for XML-languages. We also characterize those XML-grammars that generate regular XML-languages.

---

Résumé. Nous considérons des documents XML décrits par une définition de type de document (DTD). Une grammaire XML est une grammaire formelle qui retient les aspects syntaxiques d'une DTD. Nous étudions les propriétés de cette famille de grammaires. Nous montrons qu'un langage XML a essentiellement une seule grammaire XML. Nous donnons deux caractérisations des langages engendrés par les grammaires XML, la première est ensembliste, la deuxième est par une propriété de saturation. Nous examinons des problèmes de décision et nous prouvons que certaines propriétés qui sont indécidables pour les langages context-free généraux deviennent décidables pour les langages XML. Nous caractérisons également les grammaires XML qui engendrent des langages rationnels.

---

---

Received: 16 March 2001 / 19 March 2002     

Grammar semantics, analysis and parsing by abstract interpretation

We study abstract interpretations of a fixpoint protoderivation semantics defining the maximal derivations of a transitional semantics of context-free grammars akin to pushdown automata. The result is a hierarchy of bottom-up or top-down semantics refining the classical equational and derivational language semantics and including Knuth grammar problems, classical grammar flow analysis algorithms and parsing algorithms.     

Double Greibach operator grammars

Every context-free grammar can be transformed into one in double Greibach operator form, that satisfies both double Greibach form and operator form. Examination of the expressive power of various well-known subclasses of context-free grammars in double Greibach and/or operator form yields an extended hierarchy of language classes. Basic decision properties such as equivalence can be stated in stronger forms via new classes of languages in this hierarchy.