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: 1466
Venue: PODS
Year: 2008
Pagerank: 6.1961339e-05
Overall Rank: 5,502 | 62.26%
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
806	Provenance for Aggregate Queries	2011	PODS	0.00013890398
1,060	Curated Databases	2008	PODS	0.00012371807
1,786	Putting Lipstick on Pig: Enabling Database-style Workflow Provenance	2012	VLDB	9.7690421e-05
1,912	Querying Data Provenance	2010	SIGMOD	9.4946756e-05
1,952	Caravan: Provisioning for What-If Analysis	2013	CIDR	9.4233049e-05
2,503	The Semiring Framework for Database Provenance	2017	PODS	8.4964654e-05
5,511	A Quest for Beauty and Wealth (or, Business Processes for Database Researchers)	2011	PODS	6.1915384e-05
6,301	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS	5.9213518e-05
7,748	To Not Miss the Forest for the Trees - A Holistic Approach for Explaining Missing Answers over Nested Data	2021	SIGMOD	5.5528084e-05
8,509	Hypothetical Reasoning via Provenance Abstraction	2019	SIGMOD	5.4120069e-05
9,193	Query-Guided Resolution in Uncertain Databases	2023	SIGMOD	5.3058708e-05
12,212	A Provenance Framework for Data-Dependent Process Analysis	2014	VLDB	5.093636e-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.00059843817
137	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB	0.00029877792
1,060	Curated Databases	2008	PODS	0.00012371807
1,599	Update Exchange with Mappings and Provenance	2007	VLDB	0.00010241307
2,569	ProTDB: Probabilistic Data in XML	2002	VLDB	8.4090027e-05
3,318	On the Complexity of Managing Probabilistic XML Data	2007	PODS	7.5247776e-05
4,495	Queries with Incomplete Answers over Semistructured Data	1999	PODS	6.6623097e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	17	Provenance Semirings	2007	PODS
2	2,757	Secure XML Querying with Security Views	2004	SIGMOD
3	5,936	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD
4	12,684	Structural Characterizations of the Semantics of XPath as Navigation Tool on a Document	2006	PODS
5	8,279	Schema-Based Independence Analysis for XML Updates	2009	VLDB
6	496	Schema-Free XQuery	2004	VLDB
7	806	Provenance for Aggregate Queries	2011	PODS
8	1,243	Querying XML Views of Relational Data	2001	VLDB
9	12,555	Relational-Style XML Query	2008	SIGMOD
10	12,410	Certain Answers for XML Queries	2010	PODS