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.1905499e-05
Overall Rank: 11,645 | 19.07%
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.00021654356
1,328	Numerical Document Queries	2003	PODS	0.00012565501

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,285	Foundations of Semantic Web Databases	2004	PODS	7.2738104e-05
8,442	Static Analysis of Graph Database Transformations	2023	PODS	4.5043421e-05
2,517	Dependencies for Graphs	2017	PODS	8.6058545e-05
11,073	Efficient Validation of SHACL Shapes with Reasoning	2024	VLDB	4.1905499e-05
9,889	The (Almost) Complete Guide to Tree Pattern Containment	2015	PODS	4.2576366e-05
3,926	Magic Shapes for SHACL Validation	2022	VLDB	6.6210393e-05
7,435	Schema Mappings for Data Graphs	2017	PODS	4.7265981e-05
8,977	A Principled Approach to Bridging the Gap between Graph Data and their Schemas	2014	VLDB	4.4145674e-05
1,489	On the Decidability of Query Containment under Constraints	1998	PODS	0.00011687823
6,899	Containment of Graph Queries Modulo Schema	2024	PODS	4.8878659e-05