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.00010178006
Overall Rank: 1,897 | 86.81%
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
882	DTD Inference for Views of XML Data	2000	PODS	0.00015657456
2,150	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS	9.4255252e-05
2,594	On XML Integrity Constraints in the Presence of DTDs	2001	PODS	8.474176e-05
2,727	Semantic Query Optimization in the Presence of Types	2010	PODS	8.2216778e-05
3,427	XML with Data Values: Typechecking Revisited	2001	PODS	7.1033924e-05
5,139	Lazy Query Evaluation for Active XML	2004	SIGMOD	5.6686638e-05
5,761	Capturing both Types and Constraints in Data Integration	2003	SIGMOD	5.3377412e-05
7,727	Semantic Query Optimization for XQuery over XML Streams	2005	VLDB	4.6663256e-05
7,961	Schema-Based Independence Analysis for XML Updates	2009	VLDB	4.613363e-05
8,563	Active Views for Electronic Commerce	1999	VLDB	4.4937074e-05
12,382	Type Inference and Type Checking for Queries on Execution Traces	2008	VLDB	4.1945683e-05
12,417	Querying Web-Based Applications Under Models of Uncertainty	2008	VLDB	4.1945683e-05
12,430	Expressiveness and Complexity of XML Publishing Transducers	2007	PODS	4.1945683e-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.00064329285
114	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00046339735
274	Regular Path Queries with Constraints	1997	PODS	0.00029390022
294	Using Schema Matching to Simplify Heterogeneous Data Translation	1998	VLDB	0.00028669519
491	Your Mediators Need Data Conversion!	1998	SIGMOD	0.00022011503
844	Object Fusion in Mediator Systems	1996	VLDB	0.00016004956
1,081	Catching the Boat with Strudel: Experiences with a Web-Site Management System	1998	SIGMOD	0.00014216794

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,848	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	0.00010330772
3,681	Queries with Incomplete Answers over Semistructured Data	1999	PODS	6.8492288e-05
2,727	Semantic Query Optimization in the Presence of Types	2010	PODS	8.2216778e-05
1,163	Extracting Schema from Semistructured Data	1998	SIGMOD	0.00013577466
12,157	Type-Based Detection of XML Query-Update Independence	2012	VLDB	4.1945683e-05
2,150	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS	9.4255252e-05
9,668	Interaction between Path and Type Constraints	1999	PODS	4.3074872e-05
3,863	Type Systems for Querying Class Hierarchies with Non-strict Inheritance.	1989	PODS	6.6873684e-05
3,427	XML with Data Values: Typechecking Revisited	2001	PODS	7.1033924e-05
12,382	Type Inference and Type Checking for Queries on Execution Traces	2008	VLDB	4.1945683e-05