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: h39928cb53423c3a9
Venue: SIGMOD
Year: 1998
Pagerank: 0.00011306716
Overall Rank: 1,258 | 91.55%
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
23	Spark SQL: Relational Data Processing in Spark	2015	SIGMOD	0.00055406774
326	Storing Semistructured Data with STORED	1999	SIGMOD	0.00020963333
1,118	XTRACT: A System for Extracting Document Type Descriptors from XML Documents	2000	SIGMOD	0.00011951924
1,315	DTD Inference for Views of XML Data	2000	PODS	0.00011058412
2,797	Inferring XML Schema Definitions from XML Data	2007	VLDB	7.9969811e-05
3,242	Inference of Concise DTDs from XML Data	2006	VLDB	7.4991762e-05
3,723	Schema Management for Document Stores	2015	VLDB	7.0706017e-05
4,592	Queries with Incomplete Answers over Semistructured Data	1999	PODS	6.513694e-05
7,461	Reducing Ambiguity in Json Schema Discovery	2021	SIGMOD	5.5213638e-05
9,042	Measuring the Structural Similarity of Semistructured Documents Using Entropy	2007	VLDB	5.2318346e-05
13,146	Querying Websites Using Compact Skeletons	2001	PODS	4.9793485e-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
50	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00043130126
130	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030320165
2,147	Query Decomposition and View Maintenance for Query Languages for Unstructured Data	1996	VLDB	8.9576491e-05
4,461	An Object Data Model with Roles	1993	VLDB	6.5884518e-05

Semantically Similar Papers

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