The word problem for visibly pushdown languages described by grammars

Visibly pushdown languages are an interesting subclass of deterministic context-free languages that can model nonregular properties of interest in program analysis. Such class properly contains typical classes of parenthesized languages such as “parenthesis”, “bracketed”, “balanced” and “input-driven” languages. It is closed under boolean operations and has decidable decision problems such as emptiness, inclusion and universality. We study the membership problem for visibly pushdown languages, and show that it can be solved in time linear in both the size of the input grammar and the length of the input word. The algorithm relies on a reduction to the reachability problem for game graphs. We also discuss the time complexity of the membership problem for the class of balanced languages which is the largest among those cited above. Besides the intrinsic theoretical interest, we further motivate our main result showing an application to the validation of XML documents against Schema and Document Type Definitions (DTDs). Work partially supported by funds for the research from MIUR 2006, grant “Metodi Formali per la verifica di sistemi chiusi ed aperti”, Università di Salerno. A preliminary version of this paper was published in the Proceedings of the 4th International Symposium Automated Technology for Verification and Analysis (ATVA 2006), Lecture Notes in Computer Science 4218, pp. 96–109, 2006.     

Efficient determinization of visibly and height-deterministic pushdown automata

New algorithms for the determinization of nondeterministic visibly and nondeterministic real-time height-deterministic pushdown automata are presented. The algorithms improve the results of existing algorithms. They construct only accessible states and necessary pushdown symbols of the resulting deterministic pushdown automata.     

Evolving schemas for streaming XML

In this paper we model schema evolution for XML by defining formal language operators on Visibly Pushdown Languages (VPLs). Our goal is to provide a framework for efficient validation of streaming XML in the realistic setting where the schemas of the exchanging parties evolve and thus diverge from one another. We show that Visibly Pushdown Languages are closed under the defined language operators and this enables us to expand the schemas (for XML) in order to account for flexible or constrained evolution.     

P-hardness of the emptiness problem for visibly pushdown languages

Visibly pushdown languages form a subclass of the context-free languages which is appealing because of its nice algorithmic and closure properties. Here we show that the emptiness problem for this class is not any easier than the emptiness problem for context-free languages, namely hard for deterministic polynomial time. The proof consists of a reduction from the alternating graph reachability problem.     

Converting XML DTDs to UML diagrams for conceptual data integration

Extensible Markup Language (XML) is fast becoming the new standard for data representation and exchange on the World Wide Web, e.g., in B2B e-commerce. Modern enterprises need to combine data from many sources in order to answer important business questions, creating a need for integration of web-based XML data. Previous web-based data integration efforts have focused almost exclusively on the logical level of data models, creating a need for techniques that focus on the conceptual level in order to communicate the structure and properties of the available data to users at a higher level of abstraction. The most widely used conceptual model at the moment is the Unified Modeling Language (UML).

This paper presents algorithms for automatically constructing UML diagrams from XML DTDs, enabling fast and easy graphical browsing of XML data sources on the web. The algorithms capture important semantic properties of the XML data such as precise cardinalities and aggregation (containment) relationships between the data elements. As a motivating application, it is shown how the generated diagrams can be used for the conceptual design of data warehouses based on web data, and an integration architecture is presented. The choice of data warehouses and On-Line Analytical Processing as the motivating application is another distinguishing feature of the presented approach.     

基于下推自动机的XML数据流递归查询研究

针对具有子孙轴(//)和谓词([])结构特征的XPath对具有不同递归深度的XML数据流进行递归查询处理问题,提出了基于下推自动机技术的处理方法,通过将XPath各类置步转化成相对应的处理模块,由算法将各类处理模块组合起来,建立了自上而下的树状查询模型.由于查询过程中将会发生多重匹配,从而会产生大量的匹配模式,该模型通过有效的匹配策略和缓存操作,对匹配模式进行保存及检验,成功地实现XML数据流递归查询.实验结果表明,该算法在性能上要优于传统方法.     

一种基于XML的Web数据集成方案

介绍了Web环境下异构数据集成技术产生的背景和研究目的以及相关的概念、技术和方法,针对XML作为合适的数据交换格式的特点介绍了基于XML的信息集成的关键因素,提出了一种基于XML的Web数据集成操作模型,并讨论了该模型在Web数据集成时数据交换和共享过程,给出了集成构架的结构及组成。     

基于XML的电子病历信息集成的研究

通过分析电子病历数据来源,针对数据来源的多样性,利用XML可以对不同应用甚至是差异很大的应用间的数据进行描述的优点,设计出基于XML的电子病历集成框架,将来源于不同应用系统的病历数据转换为XML文档以实现数据的共享与交换。     

基于XML的电子病历信息集成的研究

通过分析电子病历数据来源，针对数据来源的多样性，利用XML可以对不同应用甚至是差异很大的应用间的数据进行描述的优点．设计出基于XML的电子病历集成框架，将来源于不同应用系统的病历数据转换为XML文档以实现数据的共享与交换。     

基于XML技术的数据集成解决方案的研究与应用

企业为了提高相互之间的合作程度以及自身的竞争力,常常需要将企业内部或者企业之间的应用系统进行集成,数据集成作为系统集成的基础,它的成功与否直接影响到系统集成的成败,文章首先提出了一种基于XML技术的数据集成解决方案,研究了XML技术在数据整合与交换方面的原理与实现,然后结合它在“银保”合作中的应用,说明了基于XML技术的数据集成解决方案在实际应用中的可行性和优势。     

一种改进的基于约束关系的XML查询重写算法研究

查询重写是解决数据集成、查询优化和物理层数据独立性等问题的关键技术.以往工作主要集中在关系数据模型方面.最近Michigan大学Timber研究小组提出一种全新的基于约束的XML查询重写算法.然而,该算法未考虑存在内定谓词情况下的重写问题,应用范围受到一定限制.在原算法的重写思想基础上,提出了一种基于约束的XML查询重写的改进算法.通过引入映射规则中的约束条件,消除阻碍重写的Skolem函数,从而解决内定谓词问题,增大原算法的应用范围.证明了改进算法的正确性.性能分析和测试结果表明,改进算法并不增加实质性的性能代价.     

Double-layered schema integration of heterogeneous XML sources

Schema integration aims to create a mediated schema as a unified representation of existing heterogeneous sources sharing a common application domain. These sources have been increasingly written in XML due to its versatility and expressive power. Unfortunately, these sources often use different elements and structures to express the same concepts and relations, thus causing substantial semantic and structural conflicts. Such a challenge impedes the creation of high-quality mediated schemas and has not been adequately addressed by existing integration methods. In this paper, we propose a novel method, named XINTOR, for automating the integration of heterogeneous schemas. Given a set of XML sources and a set of correspondences between the source schemas, our method aims to create a complete and minimal mediated schema: it completely captures all of the concepts and relations in the sources without duplication, provided that the concepts do not overlap. Our contributions are fourfold. First, we resolve structural conflicts inherent in the source schemas. Second, we introduce a new statistics-based measure, called path cohesion, for selecting concepts and relations to be a part of the mediated schema. The path cohesion is statistically computed based on multiple path quality dimensions such as average path length and path frequency. Third, we resolve semantic conflicts by augmenting the semantics of similar concepts with context-dependent information. Finally, we propose a novel double-layered mediated schema to retain a wider range of concepts and relations than existing mediated schemas, which are at best either complete or minimal, but not both. Performed on both real and synthetic datasets, our experimental results show that XINTOR outperforms existing methods with respect to (i) the mediated-schema quality using precision, recall, F-measure, and schema minimality; and (ii) the execution performance based on execution time and scale-up performance.     

Integrating and querying distributed XML data via XLink

XML instances are not necessarily self-contained but may have connections to remote XML data residing on other servers. In this paper, we show that—in spite of its minor support and use in the XML world—the XLink language provides a powerful mechanism for expressing such links both from the modeling point of view and for actually querying interlinked XML data: in our dbxlink approach, the links are not seen as explicit links (where the users must be aware of the links and traverse them explicitly in their queries), but define views that combine into a logical, transparent XML model which serves as an external schema and can be queried by XPath/XQuery. We motivate the underlying modeling and give a concise and declarative specification as an XML-to-XML mapping. We also describe the implementation of the model as an extension of the eXist [eXist: an Open Source Native XML Database, http://exist-db.org/] XML database system. The approach can be applied both for distribution of data and for integration of data from autonomous sources.     

利用JMS和XML实现系统集成

说明系统集成是信息化的必然趋势,提出用JMS－XML构建系统集成体系,具体阐述了JMS和XML的体系和实现,最后,运用JMS－XML体系来构建一个实例。     

Dual syntax for XML languages

XML is successful as a machine processable data interchange format, but it is often too verbose for human use. For this reason, many XML languages permit an alternative more legible non-XML syntax. XSLT stylesheets are often used to convert from the XML syntax to the alternative syntax; however, such transformations are not reversible since no general tool exists to automatically parse the alternative syntax back into XML.

We present XSugar, which makes it possible to manage dual syntax for XML languages. An XSugar specification is built around a context-free grammar that unifies the two syntaxes of a language. Given such a specification, the XSugar tool can translate from alternative syntax to XML and vice versa. Moreover, the tool statically checks that the transformations are reversible and that all XML documents generated from the alternative syntax are valid according to a given XML schema.     

基于XML的数据集成模型研究

随着企业信息化的逐步深入，企业内部及企业之间存在着大量的异构数据，数据集成问题是企业信息化建设所面临的问题之一。应用XML技术，提出了基于XML技术的企业数据集成模型的框架结构，对该框架的各个组成部分给出了说明以及所涉及的关键技术进行了研究。     

基于XML的数据集成模型研究

随着企业信息化的逐步深入,企业内部及企业之间存在着大量的异构数据,数据集成问题是企业信息化建设所面临的问题之一。应用XML技术,提出了基于XML技术的企业数据集成模型的框架结构,对该框架的各个组成部分给出了说明以及所涉及的关键技术进行了研究。     

基于XML的Web数据集成技术的研究

本文首先介绍了Web环境下异构数据集成技术产生的背景和研究目的以及相关的概念、技术和方法,然后针对XML作为合适的数据交换格式的特点介绍了基于XML的信息集成的关键因素,基于此,提出了一种基于XML的Web数据集成操作模型,并讨论了该模型在Web数据集成时数据交换和共享过程。最后,给出了集成构架的结构及组成。