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: hfbef73c0080dbfbe
Venue: PODS
Year: 1998
Pagerank: 7.3728818e-05
Overall Rank: 3,365 | 77.38%
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,041	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.1421879e-05
2,565	On XML Integrity Constraints in the Presence of DTDs	2001	PODS	8.2910005e-05
4,248	Integrity Constraints for XML	2000	PODS	6.704016e-05
4,266	A Web Odyssey: from Codd to XML	2001	PODS	6.6972871e-05
4,582	Reasoning about Nested Functional Dependencies	1999	PODS	6.5191203e-05
4,592	Queries with Incomplete Answers over Semistructured Data	1999	PODS	6.513694e-05
5,226	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS	6.2207517e-05
6,016	OLAP Dimension Constraints	2002	PODS	5.9134174e-05
8,043	Extended Path Expressions for XML	2001	PODS	5.4011538e-05
9,980	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	5.1013913e-05
10,067	Interaction between Path and Type Constraints	1999	PODS	5.0873692e-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
130	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030320165
356	Regular Path Queries with Constraints	1997	PODS	0.00020103855

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,923	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS
2	13,164	Reachability and Connectivity Queries in Constraint Databases	2000	PODS
3	13,319	Incomplete Path Expressions and their Disambiguation	1994	SIGMOD
4	4,459	Semantic Query Optimization in the Presence of Types	2010	PODS
5	11,834	Data Path Queries over Embedded Graph Databases	2022	PODS
6	10,115	Semantic Acyclicity Under Constraints	2016	PODS
7	5,226	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS
8	4,592	Queries with Incomplete Answers over Semistructured Data	1999	PODS
9	356	Regular Path Queries with Constraints	1997	PODS
10	10,067	Interaction between Path and Type Constraints	1999	PODS