Storing and querying ordered XML using a relational database system

Igor TatarinovStratis D. ViglasKevin BeyerJayavel ShanmugasundaramEugene ShekitaChun Zhang

article2002SIGMOD1,915 citations

Develops three order-encoding techniques—Global, Local, and Dewey Order—alongside translation algorithms that enable standard relational databases to efficiently store, query, and update ordered XML documents.

Listen

As XML emerged as the primary standard for Internet data exchange, content management systems increasingly required ways to store, query, and reconstruct documents while preserving their inherent hierarchical and sequential order. Prior approaches focused on decomposing XML documents into unordered relational databases, leaving a critical gap in understanding how to efficiently support ordered XML data models without purpose-built sequence engines. The article set out to evaluate whether relational database systems can efficiently support ordered XML data and to demonstrate effective order-encoding methods and query translation algorithms for standard database workloads.

To address this challenge, the authors introduced three lossless numbering schemes to encode order as explicit data values: Global Order (absolute document positions), Local Order (relative sibling positions), and Dewey Order (hierarchical path vectors). They developed algorithms to translate ordered XPath navigation, predicates, and updates into SQL across both schema-less (Edge) and schema-aware (Inlining) database configurations. The researchers evaluated these approaches by running query, reconstruction, and insertion workloads on an IBM DB2 relational database system using scaled versions of the Shakespeare XML dataset, sizing up to 100 megabytes, and comparing performance against a dedicated main-memory XML processor.

The findings show that standard relational database management systems can process complex ordered XML queries efficiently, executing queries on a 100-megabyte dataset in roughly 2 to 3 seconds. Global Order delivers the fastest query execution times across most ordered access patterns, though it experiences significant renumbering overhead during updates. Dewey Order offers the best overall trade-off, showing query speeds only slightly slower than Global Order while reducing insertion and renumbering times during data updates by roughly half compared to Global Order under conflict conditions. In contrast, Local Order performs best on updates but struggles severely with queries on schema-less tables due to its reliance on expensive SQL recursion, though knowing the document schema significantly mitigates this performance penalty.

These results demonstrate that enterprises do not need to abandon mature, scalable relational database infrastructures to manage ordered XML content. Relational engines can remain highly competitive and even outpace main-memory XML processors by avoiding repetitive document parsing and leveraging relational path indexes. However, the study uncovered that standard relational query optimizers frequently misestimate hierarchical containment predicates, occasionally selecting execution plans that run orders of magnitude slower than optimal plans unless manually tuned.

Organizations handling XML data within relational databases should adopt Global Order for read-dominated environments and Dewey Order when systems require frequent updates. System architects should also utilize schema-aware storage designs whenever possible to avoid recursive SQL evaluation. To sustain these performance benefits systematically, database vendors and engineering teams must enhance relational query optimizers with native awareness of hierarchical data structures and containment costing. While the reported benchmarks reliably reflect workloads fitting in-memory database buffers, teams should anticipate a two- to five-fold increase in reconstruction runtimes when data outgrows the relational buffer pool.

Cornell University IBM University of Washington University of Wisconsin Madison data exchange data management hierarchical structures XML query processing relational database system XML document tree

Tatarinov et al (2002).pdf

Paper: Access path selection in a relational database management system, P. Selinger et al. (1979). This foundational paper establishes the cost-based relational optimization and access path selection principles that govern how translated SQL queries over shredded hierarchical data are evaluated.

Paper: Dremel: Interactive Analysis of Web-Scale Datasets, S. Melnik et al. (2010). This work advances techniques for storing and querying nested, structured data by introducing columnar encoding and distributed SQL-like execution for large-scale hierarchical records.

Cover for Storing and querying ordered XML using a relational database system

Abstract

XML is quickly becoming the de facto standard for data exchange over the Internet. This is creating a new set of data management requirements involving XML, such as the need to store and query XML documents. Researchers have proposed using relational database systems to satisfy these requirements by devising ways to “shred” XML documents into relations, and translate XML queries into SQL queries over these relations. However, a key issue with such an approach, which has largely been ignored in the research literature, is how (and whether) the ordered XML data model can be efficiently supported by the unordered relational data model. This paper shows that XML’s ordered data model can indeed be efficiently supported by a relational database system. This is accomplished by encoding order as a data value. We propose three order encoding methods that can be used to represent XML order in the relational data model, and also propose algorithms for translating ordered XPath expressions into SQL using these encoding methods. Finally, we report the results of an experimental study that investigates the performance of the proposed order encoding methods on a workload of ordered XML queries and updates.

Shakespeare’s plays are marked up and stored as XML, the ordering of the acts within a play is relevant, and queries can exploit this order by asking for the second act in a play.

In this paper, we show that XML’s ordered data model can indeed be efficiently supported by a relational DBMS. We propose three order encoding methods that can be used to represent XML order in the relational data model. These encoding methods are essentially numbering schemes that capture enough information to reconstruct an ordered XML document; that is, they ensure that the mapping from ordered XML to relations is “lossless”.

Each encoding method we propose is based on a different approach for achieving a lossless mapping from ordered XML to relations. With the Global Order encoding method, the absolute position of each XML element is stored as a data value. With the Local Order encoding method, the position of an element relative to its siblings is stored. Finally, the Dewey Order encoding method stands as a hybrid of the preceding two methods. These order encoding methods are general and can be used with different approaches for shredding XML documents into relations.

Given these three order encoding methods, the question we would like to answer is: when and why does one encoding method work better than the other? As we shall show, the choice of the order encoding method has a dramatic effect on the performance of ordered XML queries and updates. To answer the above question in a systematic manner, we characterize ordered XML queries (specified in XPath) along three dimensions, and show that each dimension can be supported independently. We then present algorithms for translating XPath queries into SQL using the proposed order encoding methods. Finally, we present an experimental study of the three encoding methods using a workload of ordered XML queries and updates.

Our results show that a relational database system can efficiently support most ordered XPath queries. The best performance is achieved with Global Order for query-mostly workloads, and with Dewey Order for a mix of queries and updates. Our results also show that in some cases machine-translated XPath queries can perform very poorly, requiring manual tuning for optimal performance. However, poor performance in those cases is not due to a flaw in the translation algorithm. Rather, it can be attributed to the fact that the relational database system does not understand the hierarchical structure of XML and the semantics of XPath queries. We discuss these limitations and outline possible solutions.

In summary, this paper presents the first comprehensive study of how XML’s ordered data model can be supported using a relational database system.

1. Introduction
2. Related Work
3. Ordered XML: Data Model, Query Languages and Query Dimensions
3.1 The XML Data Model
3.2 Order in XML Query Languages
3.2.1 Order-based Functionality in XPath
3.2.2 Order-based Functionality in XQuery
3.3 Evaluation Modes for XML Queries
3.4 The Three Dimensions of XML Order
3.4.2 Result Set Ordering (Inter-Element Order)
3.4.3 Ordered Element Reconstruction (Intra-Element Order)
4. XML Order Encoding Methods
4.1 Global Order Encoding
4.2 Local (Sibling) Order Encoding
4.3 Dewey Order Encoding
4.4 Same-Sibling (Partial) Order Encoding
5. Shredding Ordered XML into Relations
5.1 The Schema-less Case
5.1.1 Storing Order Information
5.2 The Schema-aware Case
6. Translating Ordered XML Queries and Updates into SQL
6.1 Query Translation for Global Order
6.1.1 Translation of following
6.1.2 Translation of following-sibling
6.1.3 Translation of Position-based Predicates
6.1.4 Translation of XQuery Operators
6.1.5 Enforcing Inter- and Intra-Element Order
6.1.6 Translating XML Updates
6.2 Query Translation for Dewey Order
6.2.1 Enforcing Global Order using Dewey Paths
6.2.2 Inferring parent_id in Dewey
6.3 Query Translation for Local Order
6.4 Query Translation in Inlining
7. Experimental Results
7.1 Storage Requirements
7.2 Test Queries
7.3 Unordered Selection
7.4 Ordered Selection
7.5 Reconstruction
7.6 Insert Performance
7.7 Reducing the Buffer Size
7.8 Comparison with a Main-Memory XPath Processor
8. Conclusion
References

Knowls

Knowl 1 — Three Dimensions of XML Order in Query Processing
definition
Support for the ordered XML data model in database systems comprises three distinct dimensions:
1. Evaluation of Order-Based Axes and Functions: Evaluation of navigation axes and predicates that explicitly depend on document order. These include directional axes such as following (all nodes after the context node, excluding descendants), preceding (all nodes before the context node, excluding ancestors), following-sibling, preceding-sibling, and indexing functions such as position() = n or range selections ([m TO n]).
2. Result Set Ordering (Inter-Element Order): Enforcing document order among the distinct nodes or element identifiers returned by an XML query in both selection mode (returning ordered node identifiers) and reconstruction mode (returning complete XML element fragments).
3. Ordered Element Reconstruction (Intra-Element Order): Preserving the relative document order of all internal subelements, text nodes, and descendant structures when reconstructing complete XML trees from underlying relational storage.
Knowl 2 — XML Order Encoding Schemes: Global, Local, and Dewey Order
model/method
To represent the ordered XML data model within unordered relational tables losslessly, three primary node order numbering schemes can be used:
- Global Order: Each node is assigned a single numerical identifier representing its absolute document order position (e.g., start byte offset or sequential integer rank). In addition, an end-of-subtree marker $\text{end\_desc\_id}$ (the identifier of its last descendant) is stored. Global axes and structural containment translate directly into numeric range comparisons ( $ext{id} \le \text{descendant\_id} \le \text{end\_desc\_id}$ ). In the worst-case insertion scenario, inserting a new node requires renumbering all following nodes in the entire document.
- Local (Sibling) Order: Each node is assigned an integer $\text{sIndex}$ reflecting its relative position among immediate siblings under the same parent node. While local sibling navigation is straightforward, global document order requires dynamically reconstructing ancestor paths. In the worst-case insertion scenario, only the subsequent siblings of the inserted node require renumbering.
- Dewey Order: Each node is assigned a vector representing the path of sibling indices from the root to that node (e.g., $1.2.1$ ). This vector uniquely and losslessly determines both global document position and ancestor-descendant relationships. In the worst-case insertion scenario, only the subsequent siblings and their descendants require renumbering.
Knowl 3 — Ordered Relational Shredding for Schema-less and Schema-Aware XML
model/method
When decomposing (shredding) XML trees into relational tables, the representation of order depends on whether an XML schema or DTD is known:

Schema-less Shredding (Edge Approach)

All elements across documents are stored in an Edge table whose schema is specialized per order encoding:
- Global Order: $\text{Edge}(\text{id}, \text{parent\_id}, \text{end\_desc\_id}, \text{path\_id}, \text{value})$ , where $\text{id}$ reflects document order and $\text{end\_desc\_id}$ defines the descendant boundary.
- Local Order: $\text{Edge}(\text{id}, \text{parent\_id}, \text{sIndex}, \text{path\_id}, \text{value})$ , where $\text{id}$ is an arbitrary identifier and $\text{sIndex}$ stores sibling rank.
- Dewey Order: $\text{Edge}(\text{dewey}, \text{path\_id}, \text{value})$ , where $\text{dewey}$ is a variable-length byte string encoding the full root-to-node path; explicit $\text{id}$ and $\text{parent\_id}$ columns are omitted because they can be derived directly from the Dewey path.
Schema-Aware Shredding (Inlining Approach)

When a DTD or XML Schema is present, child elements with multiplicity of at most 1 are inlined as attributes within their parent relation. Separate tables are generated only for elements that occur multiple times. Each generated relation contains an order column (Global, Local, or Dewey) corresponding to the entity. Inlined child elements require no separate order column because their position relative to the parent is statically determined by the schema.
Knowl 4 — XPath-to-SQL Translation Algorithm for Global Order
algorithm
The algorithm translates an ordered XPath expression over a schema-less Edge table into a sequence of SQL Common Table Expressions (WITH inlined views), preserving document order and evaluating navigational axes through global identifier comparisons.
Input: An XPath expression $P = /Step_1/Step_2/\dots/Step_N$
Output: An executable SQL query preserving document order
q = 1
sql = "WITH Q_1 (id, parent_id, end_desc_id) AS (
       SELECT id, parent_id, end_desc_id FROM Edge WHERE parent_id = -1);"
for i = 1 to length(P) do
    step = P[i]
    sql = sql + translateStep(step, q)
    q = q + 1
end for
// Reconstruction and intra-element ordering
sql = sql + "SELECT E.* FROM Edge E, Q_" + q + " AS Q
             WHERE E.id >= Q.id AND E.id <= Q.end_desc_id
             ORDER BY Q.id, E.id;"
return sql
Within translateStep, navigation axes are translated into WITH Q_{q+1} subqueries querying Edge E joined with Q_q AS Q:
- child: WHERE E.parent_id = Q.id
- following: WHERE E.id > Q.end_desc_id
- following-sibling: WHERE E.id > Q.id AND E.parent_id = Q.parent_id
- preceding: WHERE E.id < Q.id AND E.end_desc_id < Q.id
Intra-element reconstruction sorts tuples on (Q.id, E.id) to guarantee that descendants of overlapping context nodes are not interleaved.
Knowl 5 — Position-Based XPath Predicate Translation via SQL:1999 Window Ranking
algorithm
Evaluating XPath positional index predicates of the form [n] or [position()=n] without correlated subqueries is accomplished using the SQL:1999 RANK() window function. Sparse order keys within the context node set are mapped into dense sequential sibling ranks.

For a context view $Q_q$ , the predicate step is translated into the following SQL query fragment:
```
WITH Q_{q+1} (id, parent_id, end_desc_id) AS (
  SELECT T.id, T.parent_id, T.end_desc_id
  FROM (
    SELECT Q.id, Q.parent_id, Q.end_desc_id,
           RANK() OVER (PARTITION BY Q.parent_id ORDER BY Q.id) AS pos
    FROM Q_q AS Q
  ) AS T
  WHERE T.pos = n
)
```
PARTITION BY Q.parent_id groups context nodes belonging to the same parent, and ORDER BY Q.id assigns consecutive dense integers ( $1, 2, \dots$ ) to sibling nodes. Sibling nodes matching the target rank $n$ (or range $m \le \text{pos} \le n$ ) are selected.
Knowl 6 — Dewey Order Path Encoding and Structural Derivation via UTF-8
model/method
To allow relational database systems to evaluate Dewey order comparisons via standard byte-string sorting without fixed-width space bloat, each integer component of a Dewey vector is encoded using UTF-8 variable-length byte representations and concatenated.

Because UTF-8 preserves integer sorting order in byte-by-byte lexicographical comparison, any two Dewey vectors $dp_1, dp_2$ can be compared using standard SQL operators ( $<, \le, =, >, \ge$ ).

Structural properties are derived directly from the Dewey byte string $dp$ :
- Parent Identifier: Extracted via a user-defined prefix function: $\text{parent\_id}(dp) = \text{prefix}(dp)$ which strips the final component of $dp$ .
- Descendant Boundary: Derived by appending an all-ones byte $\mathtt{0xFF}$ (which is invalid in UTF-8 and higher than any valid component byte): $\text{end\_descendant\_id}(dp) = dp \mathbin{\Vert} \mathtt{0xFF}$
A node $E$ is a descendant of context node $Q$ if and only if: $Q.dewey \le E.dewey < Q.dewey \mathbin{\Vert} \mathtt{0xFF}$
Knowl 7 — Local Order Query Evaluation via SQL Recursion
model/method
In the absence of global order information or schema metadata (the schema-less Edge model with Local Order), global axes and document order reconstruction require recursive SQL queries using least fix-point WITH clauses:
- Evaluating Global Axes (following, preceding): For a context node $u$ $u$ :
  1. Recursively traverse foreign keys from child to parent to compute the set of all ancestors $\text{anc}(u)$ .
  2. For every ancestor node in $\text{anc}(u)$ , retrieve its following siblings using $\text{sIndex}$ comparisons to form $\text{anc\_sib}$ .
  3. Recursively compute all descendants of every node in $\text{anc\_sib}$ .
- Inter-Element and Intra-Element Sorting: Because sibling indices alone cannot determine relative order across branches, recursive CTEs must traverse from the root to each result node, concatenating $\text{sIndex}$ values along the path to materialize a Dewey-like vector on the fly, which is then used in an ORDER BY clause.
When schema-aware Inlining is used, the fixed depth of elements defined in the DTD allows regular joins to replace recursive queries, eliminating the performance penalty of Local Order.
Knowl 8 — Relational Query Optimizer Failure on XML Containment Predicates
limitation
Standard relational cost-based optimizers (e.g., IBM DB2) fail to generate efficient execution plans for hierarchical XML containment queries because they lack knowledge of tree containment semantics.

When evaluating range predicates of the form: $E.id \ge Q.id \land E.id \le Q.end\_desc\_id$ the relational optimizer routinely overestimates intermediate result cardinality. To avoid an apparently massive sort over the estimated rows, the optimizer chooses an un-indexed scan over the entire document table, checking containment tuple by tuple, rather than performing an index nested-loop join followed by a sort on $(Q.id, E.id)$ . On a Shakespeare dataset, this caused the initial un-tuned plan for query $Q_3$ (/play/act/scene/speech) to run 400 times slower than query $Q_2$ (/play/act//speech), taking 35 minutes versus several seconds.

Query Tuning Workarounds
1. Forcing the optimizer to sort after joining by adding the context identifier to the ORDER BY clause (e.g., ORDER BY Q.speech_id, E.id), which eliminates the full-table scan plan.
2. Modifying the containment boundary with an arithmetic expression (e.g., $E.end\_desc\_id \le Q.end\_desc\_id + 0$ ), forcing the optimizer to use its expression-based estimator, which produces smaller cardinality estimates and selects the optimal index join plan.

Knowl 9 — Insertion Performance Comparison Across Order Schemes and Strategies

data/table

Insertion performance was evaluated under the schema-less Edge approach using both a conservative strategy (executing a check query prior to insertion to detect sparse-gap collisions) and an optimistic strategy (relying on uniqueness constraints, catching collision errors, and falling back to renumbering). Tests inserted an element after the second act of Hamlet within the 5x Shakespeare dataset.

	Conservative		Optimistic
Order Scheme	No Conflict	Conflict	No Conflict	Conflict
Global	116.2 ms	2511.9 ms	22.9 ms	2720.2 ms
Local	103.8 ms	176.3 ms	23.0 ms	115.9 ms
Dewey	137.0 ms	1303.6 ms	32.4 ms	1331.1 ms

The measurements demonstrate:

The optimistic insertion method is substantially faster when no renumbering conflict occurs (approx. $23\text{--}32\text{ ms}$ vs. $103\text{--}137\text{ ms}$ ) because it avoids pre-insertion conflict-checking queries.
In conflict scenarios requiring node renumbering, Local Order incurs the lowest latency ( $115.9\text{--}176.3\text{ ms}$ ) because renumbering is restricted to following siblings.
Dewey Order ( $1303.6\text{--}1331.1\text{ ms}$ ) outperforms Global Order ( $2511.9\text{--}2720.2\text{ ms}$ ) during conflicts because only following siblings and their descendants are renumbered, rather than all subsequent nodes in the entire document.

Knowl 10 — Storage Overhead of XML Order Schemes Across Shredding Methods

data/table

Storage requirements for the Global, Local, and Dewey order encoding schemes were measured on the 5x scaled Shakespeare dataset (~898,445 Edge tuples and ~888,900 Inlining tuples):

	Edge		Inlining
Order Scheme	Table Size	Index Size	Table Size	Index Size
Global	52.1 MB	57.9 MB	44.1 MB	28.9 MB
Local	52.1 MB	87.9 MB	47.7 MB	36.8 MB
Dewey	48.9 MB	38.7 MB	44.5 MB	15.8 MB

The data shows:

Inlining vs. Edge: Inlining consistently reduces table and index footprints compared to Edge shredding due to relational partitioning and the elimination of order columns for inlined subelements.
Dewey Efficiency: Dewey Order achieves the smallest combined table and index footprint in both configurations (87.6 MB for Edge, 60.3 MB for Inlining) because UTF-8 encoding is compact and Dewey vectors eliminate explicit parent_id and end_descendant_id columns.
Local Order Overhead: Local Order requires the largest index storage in the Edge configuration (87.9 MB) to support the parent-child navigation required during recursive path generation.

Coverage note — All substantial contributions—including the three XML order encoding schemes, shredding strategies, XPath-to-SQL translation algorithms, optimizer containment limitations, and empirical query/storage/update benchmark evaluations—are fully covered in the extracted knowls.

References

1.P. Bohannon, J. Freire,P. Roy, J. Simeon. From XML Schema to Relations: A Cost-based Approach to XML Storage. ICDE 2002.
2.M. Carey et al., XPERANTO: Publishing Object-Relational Data as XML. In Workshop on Web and Databases (WebDB), 2000.
3.B. Cooper et al., A Fast Index for Semistructured Data. In Proc. of VLDB Conference, 2001.
4.A. Deutsch, M. Fernandez, D. Suciu. Storing Semistructured Data with STORED. In Proc. of SIGMOD Conference, 1999.
5.M. F. Fernandez, A. Morishima, D. Suciu. Efficient Evaluation of XML Middle-ware Queries. In SIGMOD, 2001.
6.M. F. Fernandez, et al. Publishing Relational Data as XML: The SilkRoute Approach. IEEE Data Engineering Bulletin 24(2), 2001.
7.D. Florescu, D. Kossmann, Storing and Querying XML Data using an RDBMS. IEEE Data Engineering Bulletin 22(3), 1999.
8.D. D. Kha, M. Yoshikawa, S. Uemura. An XML Indexing Structure with Relative Region Coordinate. In ICDE 2001.
9.Online Computer Library Center. Introduction to the Dewey Decimal Classification. http://www.oclc.org/oclc/fp/about/about_the_ddc.htm.
10.P. Seshadri, M. Livny, R. Ramakrishnan. Sequence Query Processing. In Prof. SIGMOD Conference, 1994.
11.J. Shanmugasundaram et al. Relational Databases for Querying XML Documents: Limitations and Opportunities. VLDB 1999.
12.J. Shanmugasundaram et al. Efficiently Publishing Relational Data as XML Documents. In VLDB 2000.
13.J. Shanmugasundaram et al. A General Technique for Querying XML Documents using a Relational Database System. SIGMOD Record, September 2001.
14.T. Shimura, M. Yoshikawa, S. Uemura. Storage and Retrieval of XML Documents Using Object-Relational Databases. In Proc. of DEXA Conference, 1999.
15.R. Snodgrass, I. Ahn, A Taxonomy of Time in Databases. In Proc. of SIGMOD Conference, 1985.
16.I. Tatarinov, Z. G. Ives, A. Y. Halevy, D. S. Weld. Updating XML. In Proc. of SIGMOD Conference, 2001.
17.I. Tatarinov, et al. Storing and Querying Ordered XML using a Relational DBMS. Tech Report, Univ. of Washington, 2002.
18.The Plays of Shakespeare in XML. http://www.oasis-open.org/cover/bosakShakespeare200.html.
19.World Wide Web Consortium. Document Object Model (DOM) Level 3 Core Specification. W3C Recommendation Sept. 2001.
20.World Wide Web Consortium, Extensible Markup Language (XML). W3C Recommendation, February 1998.
21.World Wide Web Consortium. XML Path Language (XPath), Version 1.0, W3C Recommendation, November 1999.
22.World Wide Web Consortium. XQuery: A Query Language for XML. W3C Working Draft, June 2001.
23.F. Yergeau, UTF-8, A Transformation Format of ISO 10646. Request for Comments 2279, January 1998.
24.C. Zhang et al., On Supporting Containment Queries in Relational Database Management Systems. In. SIGMOD 2001.
25.M. Yoshikawa et al., XREL: A Path-Based Approach to Storage and Retrieval of XML documents using Relational Databases. In ACM Transactions on Internet Technology, August 2001.

Citation

MLA

Tatarinov, I., et al. “Storing and Querying Ordered XML Using a Relational Database System”. Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, 2002, pp. 204–15, https://doi.org/10.1145/564691.564715.

APA

Tatarinov, I., Viglas, S. D., Beyer, K., Shanmugasundaram, J., Shekita, E., & Zhang, C. (2002). Storing and querying ordered XML using a relational database system. Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, 204–215. https://doi.org/10.1145/564691.564715

Chicago

Tatarinov, I., S. D. Viglas, K. Beyer, J. Shanmugasundaram, E. Shekita, and C. Zhang. 2002. “Storing and Querying Ordered XML Using a Relational Database System”. Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, 204–15. https://doi.org/10.1145/564691.564715.

Harvard

Tatarinov, I. et al. (2002) “Storing and querying ordered XML using a relational database system”, Proceedings of the 2002 ACM SIGMOD international conference on Management of data. ACM, pp. 204–215. Available at: https://doi.org/10.1145/564691.564715.

Vancouver

1. Tatarinov I, Viglas SD, Beyer K, Shanmugasundaram J, Shekita E, Zhang C (2002) Storing and querying ordered XML using a relational database system. In: Proceedings of the 2002 ACM SIGMOD international conference on Management of data. ACM, pp 204–215

BibTeX

@inproceedings{Tatarinov_2002, series={SIGMOD/PODS02}, title={Storing and querying ordered XML using a relational database system}, url={http://dx.doi.org/10.1145/564691.564715}, DOI={10.1145/564691.564715}, booktitle={Proceedings of the 2002 ACM SIGMOD international conference on Management of data}, publisher={ACM}, author={Tatarinov, Igor and Viglas, Stratis D. and Beyer, Kevin and Shanmugasundaram, Jayavel and Shekita, Eugene and Zhang, Chun}, year={2002}, month=June, pages={204–215}, collection={SIGMOD/PODS02} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Storing and querying ordered XML using a relational database system

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Three Dimensions of XML Order in Query Processing

Knowl 2 — XML Order Encoding Schemes: Global, Local, and Dewey Order

Knowl 3 — Ordered Relational Shredding for Schema-less and Schema-Aware XML

Schema-less Shredding (Edge Approach)

Schema-Aware Shredding (Inlining Approach)

Knowl 4 — XPath-to-SQL Translation Algorithm for Global Order

Knowl 5 — Position-Based XPath Predicate Translation via SQL:1999 Window Ranking

Knowl 6 — Dewey Order Path Encoding and Structural Derivation via UTF-8

Knowl 7 — Local Order Query Evaluation via SQL Recursion

Knowl 8 — Relational Query Optimizer Failure on XML Containment Predicates