Carlo Sartiani
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Carlo Sartiani has a total of 21 co-authors. Here are the top co-authors by number of shared publications:
- Giorgio Ghelli
University of Pisa
18 shared publications Dario Colazzo
Université Paris Dauphine
17 shared publications- Dario Colazzo
Université Paris Dauphine
6 shared publications - Mohamed-Amine Baazizi
Sorbonne University
5 shared publications - Paolo Manghi
National Research Council Institute of Information Science and Technologies Alessandro Faedo, Pisa, Italy
5 shared publications - Stefanie Scherzinger
Universität Passau
5 shared publications
Latest Publications
- Open Access
- 22 October 2026
- Published by Association for Computing Machinery (ACM) in ACM Computing Surveys
Classical and Modern JSON Schema: A Tutorial
The last few years have seen the ubiquitous diffusion of JSON as one of the most widely used formats for publishing and interchanging data, as it combines the flexibility of semistructured data models with well-known data structures such as objects and arrays. While various schema languages for describing JSON data have been proposed in the past (e.g., JSound and Joi), JSON Schema established itself as de-facto standard schema language for JSON data. The main aim of this tutorial is to provide the reader with the basic notions about JSON Schema. This tutorial focuses on four main aspects: (1) we first describe Classical JSON Schema and introduce the features that are shared with the latest versions of the specification; (2) we introduce, then, Modern JSON Schema, explain why it differs from Classical JSON Schema, and discuss its novel evaluation model; (3) we analyze tools that support or exploit JSON Schema, like, for example, validators and data generators; and (4) we highlight open research challenges and opportunities related to JSON Schema.
- 22 October 2026
- Published by Association for Computing Machinery (ACM) in ACM Computing Surveys
Open AccessClassical and Modern JSON Schema: A Tutorial
The last few years have seen the ubiquitous diffusion of JSON as one of the most widely used formats for publishing and interchanging data, as it combines the flexibility of semistructured data models with well-known data structures such as objects and arrays. While various schema languages for describing JSON data have been proposed in the past (e.g., JSound and Joi), JSON Schema established itself as de-facto standard schema language for JSON data. The main aim of this tutorial is to provide the reader with the basic notions about JSON Schema. This tutorial focuses on four main aspects: (1) we first describe Classical JSON Schema and introduce the features that are shared with the latest versions of the specification; (2) we introduce, then, Modern JSON Schema, explain why it differs from Classical JSON Schema, and discuss its novel evaluation model; (3) we analyze tools that support or exploit JSON Schema, like, for example, validators and data generators; and (4) we highlight open research challenges and opportunities related to JSON Schema.
- Open Access
- 17 June 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 51 (4) , 1-45
Witness Generation for Classical JSON Schema
JSON Schema is an important, evolving standard schema language for families of JSON documents. It is based on a complex combination of structural and Boolean operators, including negation, as well as mutually recursive variables. The static analysis of JSON Schema documents comprises practically relevant problems, including schema satisfiability, inclusion, and equivalence. These three can be reduced to witness generation: given a schema, generate an element of the schema — if it exists — otherwise report unsatisfiability. Schema satisfiability, inclusion, and equivalence have been shown to be decidable, by reduction to reachability in alternating tree automata. However, no witness generation algorithm has yet been formally described. We contribute a first, direct algorithm for JSON Schema witness generation. We study its effectiveness and efficiency, in experiments over several schema collections, including thousands of real-world schemas. Our focus is on the completeness of the language (where we only exclude the "uniqueItems" operator), on the ability of the algorithm to run in reasonable time on a large set of real-world examples, despite the exponential complexity of the problem, and on proving its correctness and completeness.
- 17 June 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 51 (4) , 1-45
Open AccessWitness Generation for Classical JSON Schema
JSON Schema is an important, evolving standard schema language for families of JSON documents. It is based on a complex combination of structural and Boolean operators, including negation, as well as mutually recursive variables. The static analysis of JSON Schema documents comprises practically relevant problems, including schema satisfiability, inclusion, and equivalence. These three can be reduced to witness generation: given a schema, generate an element of the schema — if it exists — otherwise report unsatisfiability. Schema satisfiability, inclusion, and equivalence have been shown to be decidable, by reduction to reachability in alternating tree automata. However, no witness generation algorithm has yet been formally described. We contribute a first, direct algorithm for JSON Schema witness generation. We study its effectiveness and efficiency, in experiments over several schema collections, including thousands of real-world schemas. Our focus is on the completeness of the language (where we only exclude the "uniqueItems" operator), on the ability of the algorithm to run in reasonable time on a large set of real-world examples, despite the exponential complexity of the problem, and on proving its correctness and completeness.
- Open Access
- 28 November 2025
- Published by Elsevier in Theoretical Computer Science
- Vol. 1063
Elimination of annotation dependencies in validation for Modern JSON Schema
- 28 November 2025
- Published by Elsevier in Theoretical Computer Science
- Vol. 1063
Open AccessElimination of annotation dependencies in validation for Modern JSON Schema
- Open Access
- 22 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 1-6
JTutor: JSON Schema Validation Explained
- 22 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 1-6
Open AccessJTutor: JSON Schema Validation Explained
- Open Access
- 2 January 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 8 (POPL) , 1451-1481
Validation of Modern JSON Schema: Formalization and Complexity
JSON Schema is the de-facto standard schema language for JSON data. The language went through many minor revisions, but the most recent versions of the language, starting from Draft 2019-09, added two novel features, dynamic references and annotation-dependent validation , that change the evaluation model. Modern JSON Schema is the name used to indicate all versions from Draft 2019-09, which are characterized by these new features, while Classical JSON Schema is used to indicate the previous versions. These new “modern” features make the schema language quite difficult to understand and have generated many discussions about the correct interpretation of their official specifications; for this reason, we undertook the task of their formalization. During this process, we also analyzed the complexity of data validation in Modern JSON Schema, with the idea of confirming the polynomial complexity of Classical JSON Schema validation, and we were surprised to discover a completely different truth: data validation, which is expected to be an extremely efficient process, acquires, with Modern JSON Schema features, a PSPACE complexity. In this paper, we give the first formal description of Modern JSON Schema, which we have discussed with the community of JSON Schema tool developers, and which we consider a central contribution of this work. We then prove that its data validation problem is PSPACE-complete. We prove that the origin of the problem lies in the Draft 2020-12 version of dynamic references, and not in annotation-dependent validation. We study the schema and data complexities, showing that the problem is PSPACE-complete with respect to the schema size even with a fixed instance but is in P when the schema is fixed and only the instance size is allowed to vary. Finally, we run experiments that show that there are families of schemas where the difference in asymptotic complexity between dynamic and static references is extremely visible, even with small schemas.
- 2 January 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 8 (POPL) , 1451-1481
Open AccessValidation of Modern JSON Schema: Formalization and Complexity
JSON Schema is the de-facto standard schema language for JSON data. The language went through many minor revisions, but the most recent versions of the language, starting from Draft 2019-09, added two novel features, dynamic references and annotation-dependent validation , that change the evaluation model. Modern JSON Schema is the name used to indicate all versions from Draft 2019-09, which are characterized by these new features, while Classical JSON Schema is used to indicate the previous versions. These new “modern” features make the schema language quite difficult to understand and have generated many discussions about the correct interpretation of their official specifications; for this reason, we undertook the task of their formalization. During this process, we also analyzed the complexity of data validation in Modern JSON Schema, with the idea of confirming the polynomial complexity of Classical JSON Schema validation, and we were surprised to discover a completely different truth: data validation, which is expected to be an extremely efficient process, acquires, with Modern JSON Schema features, a PSPACE complexity. In this paper, we give the first formal description of Modern JSON Schema, which we have discussed with the community of JSON Schema tool developers, and which we consider a central contribution of this work. We then prove that its data validation problem is PSPACE-complete. We prove that the origin of the problem lies in the Draft 2020-12 version of dynamic references, and not in annotation-dependent validation. We study the schema and data complexities, showing that the problem is PSPACE-complete with respect to the schema size even with a fixed instance but is in P when the schema is fixed and only the instance size is allowed to vary. Finally, we run experiments that show that there are families of schemas where the difference in asymptotic complexity between dynamic and static references is extremely visible, even with small schemas.
- 22 March 2017
- Published by Springer Nature in Information Systems Frontiers
- Vol. 20 (1) , 63-90
Evaluating Queries and Updates on Big XML Documents
- 22 March 2017
- Published by Springer Nature in Information Systems Frontiers
- Vol. 20 (1) , 63-90
Evaluating Queries and Updates on Big XML Documents
- 28 August 2015
- Published by Springer Nature
- p. 218-228
Andromeda: A System for Processing Queries and Updates on Big XML Documents
- 28 August 2015
- Published by Springer Nature
- p. 218-228
Andromeda: A System for Processing Queries and Updates on Big XML Documents
- 1 March 2014
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 28-31
Typing query languages for data graphs
Graph query languages are essentially untyped. The lack of type information greatly limits the optimization opportunities for query engines and makes application development more complex. In this paper we discuss a simple, yet expressive, schema language for edge-labelled data graphs. This schema language is, then, used to define a query type inference approach with good precision properties.
- 1 March 2014
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 28-31
Typing query languages for data graphs
Graph query languages are essentially untyped. The lack of type information greatly limits the optimization opportunities for query engines and makes application development more complex. In this paper we discuss a simple, yet expressive, schema language for edge-labelled data graphs. This schema language is, then, used to define a query type inference approach with good precision properties.
- Open Access
- 1 August 2013
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 38 (3) , 1-45
Almost-linear inclusion for XML regular expression types
Type inclusion is a fundamental operation in every type-checking compiler, but it is quite expensive for XML manipulation languages. A polynomial inclusion checking algorithm for an expressive family of XML type languages is known, but it runs in quadratic time both in the best and in the worst cases. We present here an algorithm that has a linear-time backbone, and resorts to the quadratic approach for some specific parts of the compared types. Our experiments show that the new algorithm is much faster than the quadratic one, and that it typically runs in linear time, hence it can be used as a building block for a practical type-checking compiler.
- 1 August 2013
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 38 (3) , 1-45
Open AccessAlmost-linear inclusion for XML regular expression types
Type inclusion is a fundamental operation in every type-checking compiler, but it is quite expensive for XML manipulation languages. A polynomial inclusion checking algorithm for an expressive family of XML type languages is known, but it runs in quadratic time both in the best and in the worst cases. We present here an algorithm that has a linear-time backbone, and resorts to the quadratic approach for some specific parts of the compared types. Our experiments show that the new algorithm is much faster than the quadratic one, and that it typically runs in linear time, hence it can be used as a building block for a practical type-checking compiler.
- 9 May 2013
- Published by Elsevier in Theoretical Computer Science
- Vol. 492, 88-116
Efficient asymmetric inclusion of regular expressions with interleaving and counting for XML type-checking
- 9 May 2013
- Published by Elsevier in Theoretical Computer Science
- Vol. 492, 88-116
Efficient asymmetric inclusion of regular expressions with interleaving and counting for XML type-checking