Extracting Schema from Semistructured Data

Summary: Models semistructured data as labeled directed graphs; types them via greatest fixpoint semantics of monadic Datalog. Approximate typing algorithm; optimal typing NP-hard; clustering-based heuristics yield near-optimal results; preliminary experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3084
Venue: SIGMOD
Year: 1998
Pagerank: 0.00011475793
Overall Rank: 1,253 | 91.41%
DOI: 10.1145/276304.276331

Incoming Non-self Citations Over Time

Authors

1. Svetlozar Nestorov (Stanford University)
2. Serge Abiteboul (INRIA)
3. Rajeev Motwani (Stanford University)

BibTeX Citation

@inproceedings{nestorov_sigmod98,
        title = {{Extracting Schema from Semistructured Data}},
        author = {Nestorov, Svetlozar and Abiteboul, Serge and Motwani, Rajeev},
        series = {{SIGMOD} '98},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/276304.276331},
        url = {https://dl.acm.org/doi/10.1145/276304.276331},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
24	Spark SQL: Relational Data Processing in Spark	2015	SIGMOD	0.00054865648
318	Storing Semistructured Data with STORED	1999	SIGMOD	0.00021380325
1,142	XTRACT: A System for Extracting Document Type Descriptors from XML Documents	2000	SIGMOD	0.00012002609
1,290	DTD Inference for Views of XML Data	2000	PODS	0.00011312135
2,795	Inferring XML Schema Definitions from XML Data	2007	VLDB	8.115421e-05
3,185	Inference of Concise DTDs from XML Data	2006	VLDB	7.6567423e-05
3,655	Schema Management for Document Stores	2015	VLDB	7.2226714e-05
4,495	Queries with Incomplete Answers over Semistructured Data	1999	PODS	6.6623097e-05
7,327	Reducing Ambiguity in Json Schema Discovery	2021	SIGMOD	5.6435519e-05
8,882	Measuring the Structural Similarity of Semistructured Documents Using Entropy	2007	VLDB	5.3516704e-05
12,856	Querying Websites Using Compact Skeletons	2001	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
48	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00044033592
124	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030950263
2,118	Query Decomposition and View Maintenance for Query Languages for Unstructured Data	1996	VLDB	9.1419103e-05
4,385	An Object Data Model with Roles	1993	VLDB	6.7321354e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,308	Path Constraints on Semistructured and Structured Data	1998	PODS
2	3,341	Designing and Refining Schema Mappings via Data Examples	2011	SIGMOD
3	2,600	Convergence of Datalog over (Pre-) Semirings	2022	PODS
4	9,811	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD
5	9,126	A Principled Approach to Bridging the Gap between Graph Data and their Schemas	2014	VLDB
6	12,575	Type Inference and Type Checking for Queries on Execution Traces	2008	VLDB
7	6,301	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS
8	2,261	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS
9	4,495	Queries with Incomplete Answers over Semistructured Data	1999	PODS
10	1,233	Semistructured Data	1997	PODS