Path Constraints on Semistructured and Structured Data

Summary: Defines a class of path constraints for structured and semistructured data and shows implication is undecidable (r.e.-complete) and finite implication co-r.e.-complete for the full language. Identifies expressive decidable fragments that capture inverse relationships and local OO constraints, and proves decidability results for two typed object‑oriented models. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1137
Venue: PODS
Year: 1998
Pagerank: 7.5381026e-05
Overall Rank: 3,308 | 77.31%
DOI: 10.1145/275487.275502

Incoming Non-self Citations Over Time

Authors

1. Peter Buneman (University of Pennsylvania)
2. Wenfei Fan (University of Pennsylvania)
3. Scott Weinstein (University of Pennsylvania)

BibTeX Citation

@inproceedings{buneman_pods98,
        address = {New York, NY, USA},
        series = {{PODS} '98},
        title = {{Path Constraints on Semistructured and Structured Data}},
        url = {https://dl.acm.org/doi/10.1145/275487.275502},
        doi = {10.1145/275487.275502},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Buneman, Peter and Fan, Wenfei and Weinstein, Scott},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,066	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.2348082e-05
2,515	On XML Integrity Constraints in the Presence of DTDs	2001	PODS	8.4811795e-05
4,167	Integrity Constraints for XML	2000	PODS	6.8578387e-05
4,178	A Web Odyssey: from Codd to XML	2001	PODS	6.849218e-05
4,487	Reasoning about Nested Functional Dependencies	1999	PODS	6.6686357e-05
4,495	Queries with Incomplete Answers over Semistructured Data	1999	PODS	6.6623097e-05
5,146	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS	6.3470184e-05
5,892	OLAP Dimension Constraints	2002	PODS	6.0488431e-05
7,876	Extended Path Expressions for XML	2001	PODS	5.5249028e-05
9,811	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	5.214913e-05
9,877	Interaction between Path and Type Constraints	1999	PODS	5.2041072e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
124	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030950263
348	Regular Path Queries with Constraints	1997	PODS	0.00020518814

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,883	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS
2	12,874	Reachability and Connectivity Queries in Constraint Databases	2000	PODS
3	13,029	Incomplete Path Expressions and their Disambiguation	1994	SIGMOD
4	4,369	Semantic Query Optimization in the Presence of Types	2010	PODS
5	11,525	Data Path Queries over Embedded Graph Databases	2022	PODS
6	9,933	Semantic Acyclicity Under Constraints	2016	PODS
7	5,146	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS
8	4,495	Queries with Incomplete Answers over Semistructured Data	1999	PODS
9	348	Regular Path Queries with Constraints	1997	PODS
10	9,877	Interaction between Path and Type Constraints	1999	PODS