Análisis de nuevos atributos en el sistema de Query Prefetching de un Endpoint SPARQL

Abstract

Los repositorios de datos abiertos enlazados (LOD Linked Open Data) almacenan relaciones semánticas entre recursos globalmente identificables a través de los denominados URI (Uniform Resource Identificator). Las relaciones se codifican mediante tripletas RDF (Resource Description Framework) y permiten constituir grafos de información semántica dentro de dichos repositorios. Los repositorios LOD se pueden manejar y consultar mediante el el denominado lenguaje SPARQL (acrónimo recursivo de SPARQL Protocol and RDF Query Language). A través de sencillas consultas (’SPARQL queries), diferentes agentes extraen información semántica a través de un proceso de emparejamiento entre el grafo del repositorio y el sub-grafo que representa cada consulta a resolver. La ejecución de una consulta SPARQL muestra una arquitectura cliente/servidor distinguiéndose entre el agente (’cliente’) que solicita la resolución de una consulta y procesa su resultado, y el endpoint (’servidor SPARQL’) que se encarga de ejecutar el proceso de emparejamiento indicado anteriormente. Existen múltiples tipologías de agente, distinguiéndose a nivel del programa utilizado (navegador Web, aplicación API, herramienta,etc) y el patrón de uso (agente ’orgánico’: humano vs. agente ’robótico’: máquina). En aras de conseguir la máxima eficiencia y agilidad en el proceso de resolución de consultas, el endpoint SPARQL dispone de conocidos mecanismos de optimización basados en ’Caching’ (almacenamiento en memoria principal de resultados de consultas ya resueltas), ’Prefetching’ (recuperación proactiva de consultas anticipadas, aun no solicitadas desde el agente) y ’Query Augmentation’ (relajación de alguna condición o grado de libertad en la consulta con objeto de recuperar una respuesta mayor que permita ser utilizada ante consultas ’similares’). Existen un gran número de publicaciones científicas sobre el proceso de análisis de las consultas recibidas por los endpoints SPARQL, persiguiendo aumentar y mejorar dichos objetivos de eficiencia y agilidad y planteando estrategias diferentes. En este TFM se plantea analizar nuevos atributos que permitan ser incluidos en la estrategia de Prefetching que se detalla Rico, Touma, Queralt Calafat y col. [1] y que se resume en los siguientes pilares: Descomposición de las consultas SPARQL entre la estructura de la misma (que marca el tipo de consulta) y su superficie (que marca los recursos o individuos concretos que se solicitan en la consulta). Utilizando una representación en árbol, la estructura correspondería con la serialización de los nodos internos, mientras que la superficie correspondería con la de los nodos hoja. Tanto a nivel de tipo de consulta como de superficie, composición de series de las consultas previas consecutivas a una determinada pertenecientes a una misma sesión (desde un único agente) y utilización de árboles de decisión para la inferencia del tipo y superficie de la siguiente consulta en la serie mediante clasificación supervisada construyendo una consulta aumentada a recuperar proactivamente. Adicionalmente a estos dos puntos, planteamos extender dicha estrategia con objeto de incluir el agrupamiento de las series a partir de atributos que compacten ciertas características de complejidad y diversidad de cada consulta de la serie. Mediante este agrupamiento, perseguimos la detección de patrones entre series, utilizando clustering determinista sobre centroides, proponiéndose como línea futura el estudio comparativo del agrupamiento alrededor de medoides o agrupamiento probabilista. Esta estrategia se ha validado mediante la experimentación en 7 escenarios diferentes en donde se han observado las diferentes métricas de evaluación a nivel de clasificación J48 en uno de los datasets utilizados en el estudio (Rico, Touma, Queralt Calafat y col. [1]). A ese nivel, se han recogido porcentajes de aciertos, precisión, recall y la medida-f1 de una de las clases de observaciones. Asimismo, en cuatro escenarios diferentes se ha recogido el número de clusters computado por el algoritmo ’CascadeSimpleKMeans’ según el denominado Criterio de Calinski-Harabasz (Calinski y Harabasz [2]) :Maximización del Ratio de la dispersión inter-clusters dividido por la dispersión intra-clusters. Se constata que en uno de los escenarios propuestos, la métrica recall de evaluación de clasificación J48 muestra mayores valores en todos los puntos de observación comparativamente contra la línea base de experimentación expuesta en la publicación anteriormente indicada (Rico, Touma, Queralt Calafat y col. [1]).---ABSTRACT---The LOD Linked Open Data repositories store semantic relationships between globally identifiable resources through the so-called Uniform Resource Identifiers (URI). The relationships are encoded by means of RDF (Resource Description Framework) triplets and allow the creation of graphs of semantic information within these repositories. LOD repositories can be managed and queried using the so-called SPARQL language (recursive acronym for SPARQL Protocol and RDF Query Language). Through simple queries (‘SPARQL queries’), different agents extract semantic information through a pairing process between the repository graph and the sub-graph that represents each query to solve. The execution of a SPARQL query shows a client / server architecture distinguishing between the agent (’client’) that requests the resolution of a query and processes its result, and the endpoint (’SPARQL server’) that is in charge of executing the process of pairing indicated above. There are multiple types of agent, distinguishing at the level of the program used (Web browser, API application, tool, etc.) and the pattern of use (’organic’ agent: human vs. ’robotic’ agent: machine). In order to achieve maximum efficiency and agility in the query resolution process, the SPARQL endpoint has well-known optimization mechanisms based on ‘Caching’ (main memory storage of results of queries already resolved), ‘Prefetching’ (proactive recovery of advanced queries, not yet requested from the agent) and ‘Query Augmentation’ (relaxation of some condition or degree of freedom in the query in order to retrieve a more general response and allow the response to similar queries to be retrieved from the repository). There are a large number of scientific publications on the process of analyzing the queries received by SPARQL endpoints, seeking to increase and improve these efficiency and agility objectives and proposing different strategies. The one proposed in this TFM is summarized in the following pillars: As detailed in (Rico, Touma, Queralt Calafat y col. [1]): Decomposition of the SPARQL queries between its structure (that marks the type of query) and its surface (that marks the resources or specific individuals that are requested in the query). Using a tree representation, the structure would correspond to the serialization of the internal nodes, while the surface would correspond to that of the leaf nodes. Both at the type and surface query level, composition of series of queries prior to a specific one belonging to the same session (from a single agent) and use of decision trees for inference of the type and surface of the next query in the serie using supervised classification by building an augmented query to proactively retrieve. In addition to these two points, we plan to extend this strategy in order to include the grouping of the series based on attributes that compact certain characteristics of complexity and diversity of each query in the series. Through this grouping, we pursue the detection of patterns between series, using deterministic clustering on centroids, proposing as a future line the comparative study of the grouping around medoids or probabilistic grouping. This strategy has been validated by experimenting in 7 different scenarios where the different evaluation metrics at the J48 classification level have been observed in one of the datasets used in the study (Rico, Touma, Queralt Calafat y col. [1]). At this level, percentages of correct answers, precision, recall and the f1-score of one of the classes of observations have been collected. Likewise, in four different scenarios the number of clusters computed by the ’CascadeSimpleKMeans’ algorithm (according to the so-called Calinski-Harabasz Criterion (Calinski y Harabasz [2]): Maximization of the Ratio between the inter-cluster dispersion divided by the intra-cluster dispersion) were gathered. It is verified that in one of the proposed scenarios, the J48 classification evaluation recall metric shows higher values than in all the observation points comparatively against the experimentation baseline exposed in the previously indicated publication (Rico, Touma, Queralt Calafat y col. [1] ).