Type Inference for Queries on Semistructured Data (Extended Abstract)

Summary: Introduces a novel "traces" technique for type checking and inference over semistructured data, showing the general problem is NP-complete but PTIME for many practical cases (notably XML queries). Traces enable practical query formulation, optimization, and verification. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1176
Venue: PODS
Year: 1999
Pagerank: 0.00010168127
Overall Rank: 1,900 | 86.80%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Tova Milo
2. Dan Suciu

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
880	DTD Inference for Views of XML Data	2000	PODS	0.00015642282
2,155	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS	9.4164126e-05
2,598	On XML Integrity Constraints in the Presence of DTDs	2001	PODS	8.4660607e-05
2,732	Semantic Query Optimization in the Presence of Types	2010	PODS	8.2137395e-05
3,434	XML with Data Values: Typechecking Revisited	2001	PODS	7.0965116e-05
5,140	Lazy Query Evaluation for Active XML	2004	SIGMOD	5.6632963e-05
5,770	Capturing both Types and Constraints in Data Integration	2003	SIGMOD	5.3325833e-05
7,726	Semantic Query Optimization for XQuery over XML Streams	2005	VLDB	4.6618495e-05
7,964	Schema-Based Independence Analysis for XML Updates	2009	VLDB	4.6089395e-05
8,560	Active Views for Electronic Commerce	1999	VLDB	4.4893996e-05
12,390	Type Inference and Type Checking for Queries on Execution Traces	2008	VLDB	4.1905499e-05
12,426	Querying Web-Based Applications Under Models of Uncertainty	2008	VLDB	4.1905499e-05
12,439	Expressiveness and Complexity of XML Publishing Transducers	2007	PODS	4.1905499e-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
61	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00064281097
115	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00046301137
276	Regular Path Queries with Constraints	1997	PODS	0.00029365217
295	Using Schema Matching to Simplify Heterogeneous Data Translation	1998	VLDB	0.00028645757
489	Your Mediators Need Data Conversion!	1998	SIGMOD	0.00021989648
840	Object Fusion in Mediator Systems	1996	VLDB	0.000159889
1,080	Catching the Boat with Strudel: Experiences with a Web-Site Management System	1998	SIGMOD	0.00014204122

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,854	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	0.00010320817
2,732	Semantic Query Optimization in the Presence of Types	2010	PODS	8.2137395e-05
3,683	Queries with Incomplete Answers over Semistructured Data	1999	PODS	6.84255e-05
1,163	Extracting Schema from Semistructured Data	1998	SIGMOD	0.00013572993
12,165	Type-Based Detection of XML Query-Update Independence	2012	VLDB	4.1905499e-05
2,155	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS	9.4164126e-05
9,668	Interaction between Path and Type Constraints	1999	PODS	4.3033855e-05
3,865	Type Systems for Querying Class Hierarchies with Non-strict Inheritance.	1989	PODS	6.6809234e-05
3,434	XML with Data Values: Typechecking Revisited	2001	PODS	7.0965116e-05
12,390	Type Inference and Type Checking for Queries on Execution Traces	2008	VLDB	4.1905499e-05