Containment of Shape Expression Schemas for RDF

Summary: Identify a ShEx subclass with 'shape graphs' and a natural RDF→shape-graph embedding; embedding suffices for containment and is iff for deterministic shape graphs, yielding tractable containment. General shape-graph containment is EXP-complete; arbitrary ShEx decidable. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1749
Venue: PODS
Year: 2019
Pagerank: 4.1945683e-05
Overall Rank: 11,641 | 19.02%
DOI: 10.1145/3294052.3319687

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Sławek Staworko
2. Piotr Wieczorek

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
499	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.000216753
1,324	Numerical Document Queries	2003	PODS	0.00012581674

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,282	Foundations of Semantic Web Databases	2004	PODS	7.2808673e-05
8,450	Static Analysis of Graph Database Transformations	2023	PODS	4.5086643e-05
2,527	Dependencies for Graphs	2017	PODS	8.5954406e-05
11,070	Efficient Validation of SHACL Shapes with Reasoning	2024	VLDB	4.1945683e-05
9,890	The (Almost) Complete Guide to Tree Pattern Containment	2015	PODS	4.2617199e-05
3,923	Magic Shapes for SHACL Validation	2022	VLDB	6.6274198e-05
7,436	Schema Mappings for Data Graphs	2017	PODS	4.7311358e-05
8,971	A Principled Approach to Bridging the Gap between Graph Data and their Schemas	2014	VLDB	4.4187977e-05
1,490	On the Decidability of Query Containment under Constraints	1998	PODS	0.00011699154
6,896	Containment of Graph Queries Modulo Schema	2024	PODS	4.8925595e-05