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.3455463e-05
Overall Rank: 3,377 | 77.37%
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,043	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.1266211e-05
2,571	On XML Integrity Constraints in the Presence of DTDs	2001	PODS	8.2596816e-05
4,267	Integrity Constraints for XML	2000	PODS	6.6786936e-05
4,281	A Web Odyssey: from Codd to XML	2001	PODS	6.6721591e-05
4,602	Reasoning about Nested Functional Dependencies	1999	PODS	6.4944895e-05
4,609	Queries with Incomplete Answers over Semistructured Data	1999	PODS	6.4891057e-05
5,249	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS	6.1979445e-05
6,030	OLAP Dimension Constraints	2002	PODS	5.8911268e-05
8,069	Extended Path Expressions for XML	2001	PODS	5.3807682e-05
10,024	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	5.082116e-05
10,106	Interaction between Path and Type Constraints	1999	PODS	5.0681497e-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
131	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.000302173
358	Regular Path Queries with Constraints	1997	PODS	0.00020030407

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,937	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS
2	13,211	Reachability and Connectivity Queries in Constraint Databases	2000	PODS
3	13,366	Incomplete Path Expressions and their Disambiguation	1994	SIGMOD
4	4,482	Semantic Query Optimization in the Presence of Types	2010	PODS
5	11,884	Data Path Queries over Embedded Graph Databases	2022	PODS
6	10,156	Semantic Acyclicity Under Constraints	2016	PODS
7	5,249	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS
8	4,609	Queries with Incomplete Answers over Semistructured Data	1999	PODS
9	358	Regular Path Queries with Constraints	1997	PODS
10	10,106	Interaction between Path and Type Constraints	1999	PODS