Interaction between Path and Type Constraints

Summary: Characterizes implication problems for path constraints (inclusions/inverses) over semistructured XML with and without schema/type systems, targeting semantics and query-optimization applications. Proves that types can both lower complexity (undecidable→cubic-time and finitely axiomatizable) and raise it (PTIME→undecidable) for different implication problems. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hddbdfec149c7a4ba
Venue: PODS
Year: 1999
Pagerank: 5.0849609e-05
Overall Rank: 10,072 | 32.31%
DOI: 10.1145/303976.303982

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_pods99,
        address = {New York, NY, USA},
        series = {{PODS} '99},
        title = {{Interaction between Path and Type Constraints}},
        url = {https://dl.acm.org/doi/10.1145/303976.303982},
        doi = {10.1145/303976.303982},
        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 = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,565	On XML Integrity Constraints in the Presence of DTDs	2001	PODS	8.2870757e-05
4,249	Integrity Constraints for XML	2000	PODS	6.7008425e-05
4,266	A Web Odyssey: from Codd to XML	2001	PODS	6.6941178e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
356	Regular Path Queries with Constraints	1997	PODS	0.0002009439
366	Object Identity As A Query Language Primitive	1989	SIGMOD	0.00019914615
1,099	A General Framework for the Optimization of Object-Oriented Queries	1992	SIGMOD	0.000120317
1,254	Semistructured Data	1997	PODS	0.00011331788
3,367	Path Constraints on Semistructured and Structured Data	1998	PODS	7.3693945e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,413	On Verifying Consistency of XML Specifications	2002	PODS
2	2,565	On XML Integrity Constraints in the Presence of DTDs	2001	PODS
3	3,343	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS
4	356	Regular Path Queries with Constraints	1997	PODS
5	2,935	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS
6	3,759	XML with Data Values: Typechecking Revisited	2001	PODS
7	2,319	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS
8	12,924	Reasoning about XML Update Constraints	2007	PODS
9	4,249	Integrity Constraints for XML	2000	PODS
10	3,367	Path Constraints on Semistructured and Structured Data	1998	PODS