Formal specification, expressiveness and complexity analysis for JSON schema

Formal specification, expressiveness and complexity analysis for JSON schema

620

Ingeniería

JSON (Lenguaje de marcación de documentos).

Lenguajes de marcación de documentos.

Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2016

JSON es hoy en día el formato más popular para el traspaso de datos en la web. Sin embargo, todavía carece de un esquema estandarizado que permita a desarrolladores especificar la estructura estos documentos. JSON Schema es una propuesta para definir metadata a través de esquemas para documentos JSON. Sin embargo, todavía está en una etapa de madurez muy temprana, y no existe una especificación formal que capture al lenguaje en su totalidad. En esta tesis se lleva a cabo el primer análisis formal de documentos JSON Schema. En primer lugar, se propone una definición formal tanto de la sintaxis como de la semántica para la validación de estos documentos. Luego, en base a esta definición, se procede a capturar el poder expresivo del lenguaje. Por un lado, se demuestra que JSON Schema puede simular autómatas de árbol, con el sólo uso de un subconjunto muy restringido de la especificación. Por otro lado, se muestra que JSON Schema puede ser capturado por lógica monádica de segundo orden sobre árboles.Finalmente, se analiza la complejidad computacional de los principales problemas de decisión presentes en el contexto esquemas para lenguajes formales, el problema de validación y el problema de satisfacibilidad para documentos JSON Schema. Estos problemas resultan de gran importancia en el desarrollo de algoritmos eficientes para el traspaso de datos en la web. Por un lado, se muestra que el problema de validación puede ser resuelto de manera eficiente para esquemas fijos. Sin embargo, en términos de complejidad combinada el problema resulta ser inherentemente secuencial. Por otro lado, se propone un algoritmo exponencial para resolver el problema de satisfacibilidad. Además, se demuestra que este problema no puede ser computado con una mejor cota que la obtenida.

Suárez Barría, Fernando

2016-12-15T13:07:13Z

2016-12-15T13:07:13Z

2016

Reutter de la Maza, Juan

Pontificia Universidad Católica de Chile. Escuela de Ingeniería

acceso abierto

xi, 104 hojas

application/pdf

en

tesis de maestría

10.7764/tesisUC/ING/16908

https://doi.org/10.7764/tesisUC/ING/16908

https://repositorio.uc.cl/handle/11534/16908