1,721,051 research outputs found
Validation of Modern JSON Schema: Formalization and Complexity
No full text<p>Artifact evaluation package for the POPL'24 contribution <strong>"Validation of Modern JSON Schema: Formalization and Complexity"</strong> by Lyes Attouche, Mohamed-Amine Baazizi, Dario Colazzo, Giorgio Ghelli, Carlo Sartiani, and Stefanie Scherzinger.</p><p>All artifacts (source code, data, scripts) are packaged in a virtual machine running Ubuntu Linux, which can be run using VirtualBox. The README.md file contains the instructions. </p>
Validation of Modern JSON Schema: Formalization and Complexity
No full text<p>Artifact evaluation package for the POPL'24 submission <strong>"Validation of Modern JSON Schema: Formalization and Complexity"</strong> by Lyes Attouche, Mohamed-Amine Baazizi, Dario Colazzo, Giorgio Ghelli, Carlo Sartiani, and Stefanie Scherzinger.</p>
<p>All artifacts (source code, data, scripts) are packaged in a virtual machine running Ubuntu Linux, which can be run using VirtualBox. The README.md file contains the instructions. </p>
Types for Path Correctness of XML Queries
Full text linkIf a subexpression in a query will never contribute data to the query answer, this should be regarded as an error. This principle has been recently accepted into mainstream XML query languages, but was still waiting for a complete treatment. We provide here a precise definition for this class of errors, and define a type system that is sound and complete, in its search for such errors, for a core language, under mild restrictions on the use of recursion in type definitions. In the process, we describe a dichotomy among existential and universal type systems, which is useful to understand some unusual features of our type system.This is the pre-print of the article: Dario Colazzo, Giorgio Ghelli, Paolo Manghi, and Carlo Sartiani. 2004. Types for path correctness of XML queries. In Proceedings of the ninth ACM SIGPLAN international conference on Functional programming (ICFP '04). Association for Computing Machinery, New York, NY, USA, 126–137. https://doi.org/10.1145/1016850.101686
Efficient Inclusion of Conflict-free XML Types with Interleaving and Counting
No full textInclusion between XML types is important but expensive, and is much more expensive when unordered types are considered. We prove here that inclusion for XML types with interleaving and counting can be decided in polynomial time in presence of two important restrictions: no element appears twice in the same content model, and Kleene star is only applied to disjunctions of single elements
Linear Time Membership in a Class of Regular Expressions with Interleaving and Counting
Full text linkThe extension of Regular Expressions (REs) with an interleaving (shuffle) operator has been proposed in many occasions, since it would be crucial to deal with unordered data. However, interleaving badly affects the complexity of basic operations, and, expecially, makes membership NPhard [13], which is unacceptable for most uses of REs. REs form the basis of most XML type languages, such as DTDs and XML Schema types, and XDuce types [16, 11]. In this context, the interleaving operator would be a natural addition to the language of REs, as witnessed by the presence of limited forms of interleaving in XSD (the all group), Relax-NG, and SGML, provided that the NPhardness of membership could be avoided. We present here a restricted class of REs with interleaving and counting which admits a linear membership algorithm, and which is expressive enough to cover the vast majority of real-world XML types. We first present an algorithm for membership of a list of words into a RE with interleaving and counting, based on the translation of the RE into a set of constraints. We generalize the approach in order to check membership of XML trees into a class of EDTDs with interleaving and counting, which models the crucial aspects of DTDs and XSD schemas
The Query Language TQL Demo Presentation
No full textThis work presents the query language TQL, a query language for semistructured data, that can be used to query XML files. TQL substitutes the standard path-based patternmatching mechanism with a logic-based mechanism, where the programmer specifies the properties of the pieces of data he is trying to extract. As a result, TQL queries are more ‘declarative’, or less ‘operational’, than queries in comparable languages. This feature makes some queries easier to express, and should allow the adoption of better optimization techniques. Through a set of examples, which will presented at the SEBD demo, we show that the range of queries that can be declaratively expressed in TQL is quite wide.
- …
