Formal specification, expressiveness and complexity analysis for JSON schema

dc.contributor.advisorReutter de la Maza, Juan
dc.contributor.authorSuárez Barría, Fernando
dc.contributor.otherPontificia Universidad Católica de Chile. Escuela de Ingeniería
dc.date.accessioned2016-12-15T13:07:13Z
dc.date.available2016-12-15T13:07:13Z
dc.date.issued2016
dc.descriptionTesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2016
dc.description.abstractJSON 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.
dc.format.extentxi, 104 hojas
dc.identifier.doi10.7764/tesisUC/ING/16908
dc.identifier.urihttps://doi.org/10.7764/tesisUC/ING/16908
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/16908
dc.language.isoen
dc.nota.accesoTexto completo
dc.rightsacceso abierto
dc.subject.ddc620
dc.subject.deweyIngenieríaes_ES
dc.subject.otherJSON (Lenguaje de marcación de documentos).es_ES
dc.subject.otherLenguajes de marcación de documentos.es_ES
dc.titleFormal specification, expressiveness and complexity analysis for JSON schemaes_ES
dc.typetesis de maestría
sipa.codpersvinculados126898
sipa.codpersvinculados194028
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
000676530.pdf
Size:
633.55 KB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
730 B
Format:
Item-specific license agreed upon to submission
Description: