Schemas for Graphs and Other Forms of Semi-Structured Data

Juan L. ReutterAMW 2019 · OpenReview

Introduction

For years, the primary selling point of semi-structured data formats like JSON and RDF was their "schema-less" nature. This flexibility allowed web developers and data scientists to iterate rapidly without the rigid constraints of traditional relational databases. However, as these systems have scaled, the industry has encountered a significant hurdle: the lack of formal structure often leads to data quality issues, integration nightmares, and high maintenance costs.

This paper explores the evolution of schema languages designed to bring order to this flexibility. By analyzing the leading proposals—SHACL and ShEx for RDF graphs, and JSON Schema for hierarchical trees—it demonstrates that these seemingly disparate tools share a common theoretical foundation and face a unified set of computational challenges.

The Problem: The High Cost of Flexibility

While the ability to store data without a predefined schema is convenient, it creates a "wild west" environment for data integrity. In a large-scale system, it becomes difficult to guarantee that a "user" object consistently contains an "email" field or that a "friend" relationship in a graph is reciprocal. Without these guarantees, downstream applications must include complex error-handling logic to account for missing or malformed data.

To address this, two distinct communities have developed their own validation standards:

  1. The Semantic Web Community: Developed SHACL (Shapes Constraint Language) and ShEx (Shape Expressions) to validate RDF (Resource Description Framework) data, which is structured as directed, labeled graphs.
  2. The Web Development Community: Developed JSON Schema to validate JSON data, which is primarily hierarchical or tree-structured.

Historically, these communities have operated in silos. However, as the paper argues, they are essentially attempting to solve the same logical problems using different syntaxes.

Theoretical Convergence: The "Shape" Paradigm

By looking past surface-level syntax and examining the underlying logic and automata theory, a clear convergence emerges. The paper suggests that the "graph world" and the "document world" are moving toward a shared structural requirement: the Shape.

Shapes are declarative constraints that describe what a specific node or object should look like. Whether the data is a node in a complex RDF graph or a nested object in a JSON file, the logic used to validate its "shape" is fundamentally similar. This realization is significant because it implies that research progress in graph validation complexity can be directly applied to JSON validation, and vice versa. The industry is moving away from completely unstructured data toward a model where metadata—describing both content and structure—is a necessity for modern database vendors.

Computational Challenges and Limitations

Despite the adoption of these schema languages, several "interesting open problems" remain. These challenges typically arise from the tension between developer demands and computational feasibility:

  • Expressiveness vs. Complexity: Users frequently request powerful features such as cross-field validation or complex recursive constraints. However, adding these features often pushes the validation logic into the realm of NP-hard or even undecidable problems.
  • The Performance Gap: Validating schemas on massive, web-scale datasets requires high efficiency. There is a lingering challenge in maintaining the expressiveness developers need without sacrificing the performance required for real-time data processing.
  • Query Language Integration: There are still unresolved questions regarding how these schemas should interact with traditional query languages, such as SPARQL for RDF or SQL-based approaches for JSON.

Conclusion

The divide between graph-based and tree-based data validation is narrowing. SHACL, ShEx, and JSON Schema represent two sides of the same coin, unified by the "Shape" paradigm. As the industry continues to prioritize data quality, the focus must shift toward solving the shared theoretical and performance challenges that currently limit these schema languages. Bridging the gap between these communities will be essential for creating a more robust and integrated data ecosystem.

Summary updated

BibTeX
@inproceedings{reutter2019schemas,
  author = {Juan L. Reutter},
  title = {{Schemas for Graphs and Other Forms of Semi-Structured Data}},
  booktitle = {AMW},
  year = {2019},
  url = {https://openreview.net/forum?id=5Yjm_VSUBgP},
}
Figure