Annotated XML: Queries and Provenance

Summary: Formal provenance framework for XQuery: annotate unordered XML with commutative semirings to capture provenance for a large positive fragment and to represent repetitions, incomplete/probabilistic XML and access-control metadata. Technically, generalize the Nested Relational Calculus to semiring-annotated complex values, add recursive types and structural recursion for trees, and define XQuery semantics via translation into this calculus. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h728790df5f5d0aaa
Venue: PODS
Year: 2008
Pagerank: 6.0684862e-05
Overall Rank: 5,611 | 62.28%
DOI: 10.1145/1376916.1376954

Incoming Non-self Citations Over Time

Authors

1. J. Nathan Foster (University of Pennsylvania)
2. Todd J. Green (University of Pennsylvania)
3. Val Tannen (University of Pennsylvania)

BibTeX Citation

@inproceedings{foster_pods08,
        address = {New York, NY, USA},
        series = {{PODS} '08},
        title = {{Annotated XML: Queries and Provenance}},
        url = {https://dl.acm.org/doi/10.1145/1376916.1376954},
        doi = {10.1145/1376916.1376954},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Foster, J. Nathan and Green, Todd J. and Tannen, Val},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
819	Provenance for Aggregate Queries	2011	PODS	0.00013666629
1,076	Curated Databases	2008	PODS	0.00012159025
1,765	Putting Lipstick on Pig: Enabling Database-style Workflow Provenance	2012	VLDB	9.6955585e-05
1,827	Querying Data Provenance	2010	SIGMOD	9.5545888e-05
1,944	Caravan: Provisioning for What-If Analysis	2013	CIDR	9.3281326e-05
2,418	The Semiring Framework for Database Provenance	2017	PODS	8.4928222e-05
5,644	A Quest for Beauty and Wealth (or, Business Processes for Database Researchers)	2011	PODS	6.0533802e-05
6,429	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS	5.7884926e-05
7,234	Hypothetical Reasoning via Provenance Abstraction	2019	SIGMOD	5.5792063e-05
7,879	To Not Miss the Forest for the Trees - A Holistic Approach for Explaining Missing Answers over Nested Data	2021	SIGMOD	5.4341576e-05
9,373	Query-Guided Resolution in Uncertain Databases	2023	SIGMOD	5.1868213e-05
12,503	A Provenance Framework for Data-Dependent Process Analysis	2014	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
17	Provenance Semirings	2007	PODS	0.00059752575
141	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB	0.00029294114
1,076	Curated Databases	2008	PODS	0.00012159025
1,555	Update Exchange with Mappings and Provenance	2007	VLDB	0.00010269848
2,617	ProTDB: Probabilistic Data in XML	2002	VLDB	8.2219007e-05
3,378	On the Complexity of Managing Probabilistic XML Data	2007	PODS	7.3569859e-05
4,592	Queries with Incomplete Answers over Semistructured Data	1999	PODS	6.513694e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	17	Provenance Semirings	2007	PODS
2	2,816	Secure XML Querying with Security Views	2004	SIGMOD
3	6,059	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD
4	12,974	Structural Characterizations of the Semantics of XPath as Navigation Tool on a Document	2006	PODS
5	8,447	Schema-Based Independence Analysis for XML Updates	2009	VLDB
6	505	Schema-Free XQuery	2004	VLDB
7	819	Provenance for Aggregate Queries	2011	PODS
8	1,267	Querying XML Views of Relational Data	2001	VLDB
9	12,845	Relational-Style XML Query	2008	SIGMOD
10	12,701	Certain Answers for XML Queries	2010	PODS