Storing and Querying Ordered XML Using a Relational Database System

Summary: Demonstrates that ordered XML can be efficiently stored and queried in a relational DB by encoding XML order as data values. Proposes three order-encoding schemes and translation algorithms from ordered XPath to SQL, with experimental performance comparisons for ordered XML workloads. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3412
Venue: SIGMOD
Year: 2002
Pagerank: 0.00020125068
Overall Rank: 362 | 97.52%
DOI: 10.1145/564691.564715

Incoming Non-self Citations Over Time

Authors

1. Igor Tatarinov (University of Washington)
2. Kevin Beyer (IBM)
3. Jayavel Shanmugasundaram (Cornell University)
4. Stratis D. Viglas (University of Wisconsin)
5. Eugene Shekita (IBM)
6. Chun Zhang (University of Wisconsin)

BibTeX Citation

@inproceedings{tatarinov_sigmod02,
        title = {{Storing and Querying Ordered XML Using a Relational Database System}},
        author = {Tatarinov, Igor and Beyer, Kevin and Shanmugasundaram, Jayavel and Viglas, Stratis D. and Shekita, Eugene and Zhang, Chun},
        series = {{SIGMOD} '02},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/564691.564715},
        url = {https://dl.acm.org/doi/10.1145/564691.564715},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 50 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
77	XRANK: Ranked Keyword Search over XML Documents	2003	SIGMOD	0.00037048607
719	ORDPATHs: Insert-Friendly XML Node Labels	2004	SIGMOD	0.00014637695
795	Efficient Keyword Search for Smallest LCAs in XML Databases	2005	SIGMOD	0.00013939786
1,204	A Comprehensive XQuery to SQL Translation using Dynamic Interval Encoding	2003	SIGMOD	0.00011664562
1,460	MonetDB/XQuery: A Fast XQuery Processor Powered by a Relational Engine	2006	SIGMOD	0.00010710674
1,744	System RX: One Part Relational, One Part XML	2005	SIGMOD	9.868841e-05
2,031	Indexing XML Data Stored in a Relational Database	2004	VLDB	9.2839251e-05
2,694	Holistic Twig Joins on Indexed XML Documents	2003	VLDB	8.2469414e-05
3,167	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB	7.6749991e-05
3,727	Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps	2003	VLDB	7.1689738e-05
3,917	Tree Logical Classes for Efficient Evaluation of XQuery	2004	SIGMOD	7.0182992e-05
4,265	XQuery Implementation in a Relational Database System	2005	VLDB	6.7936855e-05
4,294	From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching	2005	VLDB	6.7780241e-05
4,537	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.6417534e-05
4,576	Efficient Evaluation of XQuery over Streaming Data	2005	VLDB	6.6216442e-05
4,813	Horton+: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs	2013	VLDB	6.4974292e-05
4,822	Colorful XML: One Hierarchy Isn't Enough	2004	SIGMOD	6.4919484e-05
5,199	Efficiently Evaluating Complex Boolean Expressions	2010	SIGMOD	6.3216824e-05
5,209	Prefix Based Numbering Schemes for XML: Techniques, Applications and Performances	2008	VLDB	6.3163287e-05
5,547	Beyond Relations: A Case for Elevating to the Entity-Relationship Abstraction	2025	CIDR	6.1790655e-05
5,750	DDE: From Dewey to a Fully Dynamic XML Labeling Scheme	2009	SIGMOD	6.100444e-05
5,772	Pattern tree algebras: sets or sequences?	2005	VLDB	6.0930389e-05
5,918	Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue	2024	PODS	6.0427671e-05
6,438	Incorporating XSL Processing Into Database Engines	2002	VLDB	5.8789927e-05
7,037	Designing Information-Preserving Mapping Schemes for XML	2005	VLDB	5.7209033e-05
7,180	Nearest Keyword Search in XML Documents	2011	SIGMOD	5.6798251e-05
7,267	Structured Materialized Views for XML Queries	2007	VLDB	5.6597556e-05
7,405	Storing and Querying Tree-Structured Records in Dremel	2014	VLDB	5.624456e-05
7,486	Why Off-the-Shelf RDBMSs are Better at XPath Than You Might Expect	2007	SIGMOD	5.6073128e-05
7,596	XPRESS: A Queriable Compression for XML Data	2003	SIGMOD	5.5882603e-05
7,607	XQuery Reloaded	2009	VLDB	5.5845947e-05
7,931	MESSIAH: Missing Element-Conscious SLCA Nodes Search in XML Data	2013	SIGMOD	5.5181056e-05
8,021	CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation	2005	VLDB	5.5055705e-05
8,033	TI: An Efficient Indexing Mechanism for Real-Time Search on Tweets	2011	SIGMOD	5.5039566e-05
8,109	Relational Support for Flexible Schema Scenarios	2008	VLDB	5.4843869e-05
8,217	Automated Migration of Hierarchical Data to Relational Tables using Programming-by-Example	2018	VLDB	5.4644927e-05
8,577	A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions	2021	SIGMOD	5.409313e-05
8,757	Search Driven Analysis of Heterogeneous XML Data	2009	CIDR	5.3766157e-05
8,870	Lazy XML Updates: Laziness as a Virtue of Update and Structural Join Efficiency	2005	SIGMOD	5.3543292e-05
9,352	Querying Virtual Hierarchies using Virtual Prefix-Based Numbers	2014	SIGMOD	5.2831061e-05
9,576	Indexing Highly Dynamic Hierarchical Data	2015	VLDB	5.2528121e-05
10,976	TreeCat: Standalone Catalog Engine for Large Data Systems	2025	VLDB	5.093636e-05
12,428	Pay-As-You-Go - An Adaptive Approach to Provide Full Context-Aware Text Search over Document Content	2010	SIGMOD	5.093636e-05
12,554	Efficient Storage Scheme and Query Processing for Supply Chain Management using RFID	2008	SIGMOD	5.093636e-05
12,559	Grouping and Optimization of XPath Expressions in DB2 pureXML	2008	SIGMOD	5.093636e-05
12,583	Towards a Physical XML independent XQuery/SQL/XML Engine	2008	VLDB	5.093636e-05
12,586	SEDA: A System for Search, Exploration, Discovery, and Analysis of XML Data	2008	VLDB	5.093636e-05
12,689	Locking-Aware Structural Join Operators for XML Query Processing	2006	SIGMOD	5.093636e-05
12,824	XISS/R: XML Indexing and Storage System Using RDBMS	2003	VLDB	5.093636e-05
13,825	Quark: An Efficient XQuery Full-Text Implementation	2006	SIGMOD	-

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
137	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB	0.00029877792
163	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027839792
318	Storing Semistructured Data with STORED	1999	SIGMOD	0.00021380325
335	A Taxonomy of Time in Databases	1985	SIGMOD	0.00020869676
430	A Fast Index for Semistructured Data	2001	VLDB	0.00018600166
502	XQuery: A Query Language for XML	2003	SIGMOD	0.00017320395
535	Efficiently Publishing Relational Data as XML Documents	2000	VLDB	0.00017003136
687	Sequence Query Processing	1994	SIGMOD	0.00014948592
1,208	Efficient Evaluation of XML Middle-ware Queries	2001	SIGMOD	0.00011659601
2,772	Updating XML	2001	SIGMOD	8.1398108e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,696	Efficient XSLT Processing in Relational Database System	2006	VLDB
2	4,710	XML Schemas in Oracle XML DB	2003	VLDB
3	8,600	Query Rewrite for XML in Oracle XML DB	2004	VLDB
4	4,265	XQuery Implementation in a Relational Database System	2005	VLDB
5	2,772	Updating XML	2001	SIGMOD
6	535	Efficiently Publishing Relational Data as XML Documents	2000	VLDB
7	12,555	Relational-Style XML Query	2008	SIGMOD
8	2,031	Indexing XML Data Stored in a Relational Database	2004	VLDB
9	1,243	Querying XML Views of Relational Data	2001	VLDB
10	137	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB