Dissemination of heterogeneous xml data

Yuan Ni, Chee Yong ChanWWW 2008 · OpenReview

Abstract

A lot of recent research has focused on the content-based dissemination of XML data. However, due to the heterogeneous data schemas used by different data publishers even for data in the same domain, an important challenge is how to efficiently and effectively disseminate relevant data to subscribers whose subscriptions might be specified based on schemas that are different from those used by the data publishers. This paper examines the options to resolve this schema heterogeneity problem in XML data dissemination, and proposes a novel paradigm that is based on data rewriting. Our experimental results demonstrate the effectiveness of the data rewriting paradigm and identifies the tradeoffs of the various approaches.

Introduction

In content-based publish/subscribe (pub/sub) systems, users express their interests through subscriptions—often represented as XPath queries—and receive XML documents that match those interests. While traditional systems assume a homogeneous environment where all participants share a single schema, real-world applications are characterized by schema heterogeneity. For example, in an e-commerce domain, one publisher might use <price> while another uses <cost>, and their nesting structures may differ significantly.

The standard approach to this problem is "Query Rewriting," where a single user subscription is translated into multiple versions to match every possible publisher's schema. However, in large-scale systems with millions of subscribers and numerous publishers, this leads to a "scalability explosion" at network routers. This paper proposes a shift in perspective: instead of rewriting millions of queries, we should rewrite the data itself to match a common global schema.

The Data Rewriting Approach (DRA)

The Data Rewriting Approach (DRA) introduces a Mediator Agent that manages mappings between local schemas and a single global schema ($S_g$). By transforming incoming data into the global format, the system allows subscribers to remain agnostic of the technical details of individual publishers. They simply subscribe to the "standard" version, and the infrastructure handles the translation.

This paradigm leverages the "single-data-multiple-queries" nature of dissemination. Since one piece of data is typically matched against thousands or millions of queries, the computational cost of rewriting that data once is significantly lower than the cumulative cost of managing rewritten queries for every possible schema variation.

Implementation Strategies

The authors explore three primary implementation strategies for data rewriting:

  1. Static Data Rewriting (SDR): Data is rewritten once by a central agent before dissemination. The network then carries both the original data and the rewritten version to ensure compatibility. While simple, this approach doubles the data volume, leading to bandwidth bottlenecks.
  2. Dynamic Data Rewriting (DDR): Routers perform rewriting on-the-fly as data passes through the network. This is further categorized into:
  3. Non-intrusive (NDDR): A data rewriter component sits between the XML parser and the matching engine. It intercepts data events and translates them into the global schema format before they reach the engine. This maintains a clean separation of concerns.
  4. Intrusive (IDDR): The matching engine itself is modified to handle translation internally. While theoretically more integrated, this increases the complexity of the core matching algorithm and can degrade performance.

Experimental Evaluation and Results

The effectiveness of these strategies was tested by measuring memory overhead and processing performance. The results highlight several key findings:

  • Performance Winner: The Non-intrusive Dynamic Data Rewriting (NDDR) approach proved to be the most efficient. By decoupling the rewriting logic from the matching engine, it avoided the performance penalties associated with the intrusive method.
  • Memory Efficiency: NDDR demonstrated surprisingly low memory overhead. For most documents, the overhead was approximately 5% of the document size, peaking at 32% only in the most complex scenarios. This suggests that the cost of caching events for translation is manageable.
  • Bandwidth and Scalability: SDR was found to be the least scalable due to the increased bandwidth requirements of sending multiple versions of the same data. In contrast, the DRA method (specifically NDDR) maintains constant space overhead at the routers regardless of the number of subscriptions, making it highly suitable for large-scale dissemination.

Conclusion

Resolving schema heterogeneity is critical for the practical deployment of XML dissemination systems. The Data Rewriting Paradigm offers a scalable alternative to traditional query rewriting. By focusing on transforming data at the router level—specifically through non-intrusive dynamic rewriting—systems can achieve high performance and low memory overhead while shielding subscribers from the complexities of diverse data sources. Future work may further optimize the rewriter components to minimize memory peaks in highly complex XML structures.

Summary updated

Abstract

A lot of recent research has focused on the content-based dissemination of XML data. However, due to the heterogeneous data schemas used by different data publishers even for data in the same domain, an important challenge is how to efficiently and effectively disseminate relevant data to subscribers whose subscriptions might be specified based on schemas that are different from those used by the data publishers. This paper examines the options to resolve this schema heterogeneity problem in XML data dissemination, and proposes a novel paradigm that is based on data rewriting. Our experimental results demonstrate the effectiveness of the data rewriting paradigm and identifies the tradeoffs of the various approaches
BibTeX
@inproceedings{ni2008dissemination,
  author = {Yuan Ni and Chee Yong Chan},
  title = {{Dissemination of heterogeneous xml data}},
  booktitle = {The Web Conference},
  year = {2008},
  url = {https://openreview.net/forum?id=BJ-8GzZuWr},
}
Figure