Avaliação top-down de consultas de caminhos livres-decontexto em grafos

• Ano de defesa: 2018
• Autor(a) principal: Medeiros, Ciro Morais
• Orientador(a): Musicante, Martin Alejandro
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Programa de Pós-Graduação: PROGRAMA DE PÓS-GRADUAÇÃO EM SISTEMAS E COMPUTAÇÃO
• País: Brasil
• Palavras-chave em Português: Rdf; Consultas em grafos; Gramáticas LL
• Área do conhecimento CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO
• Link de acesso: https://repositorio.ufrn.br/jspui/handle/123456789/24969

A internet possibilitou a criação de um imenso espaço de dados global, que pode ser acessado na forma de páginas web. Entretanto, páginas web são ideais para apresentar conteúdo para seres humanos, mas não para serem interpretadas por máquinas. Além disso, se torna difícil relacionar as informações armazenadas nos bancos de dados por trás dessas páginas. Para contornar esses problemas foi desenvolvido o Linked Data, um conjunto de boas práticas para relacionamento e publicação de dados. O formato padrão recomendado pelo Linked Data para armazenamento e publicação de dados relacionados é o Resource Description Framework (RDF). Este formato utiliza triplas na forma (sujeito, predicado, objeto) para estabelecer relacionamentos entre os dados. Um banco de dados de triplas pode ser facilmente visualizado como um grafo, de maneira que as consultas são feitas por meio da definição de caminhos no grafo. SPARQL, a linguagem padrão para consultas em grafos RDF, possibilita a definição de caminhos utilizando expressões regulares. Entretanto, expressões regulares têm expressividade reduzida, insuficiente para algumas consultas desejáveis. Para contornar este problema, alguns trabalhos propuseram a utilização de gramáticas livres-de-contexto para definir os caminhos. Desenvolvemos um algoritmo para avaliação de consultas de caminhos livres-de-contexto em grafos inspirado em técnicas de parsing top-down. Dado um grafo e uma consulta definida com base em uma gramática livre-de-contexto, nosso algoritmo identifica pares de vértices ligados por caminhos que formam palavras pertencentes à linguagem gerada pela gramática. Argumentamos que nosso algoritmo é correto e demonstramos outras propriedades importantes. O algoritmo apresenta complexidade cúbica de tempo de execução no pior caso em termos do número de vértices no grafo. Implementamos o algoritmo proposto e avaliamos seu desempenho com bancos de dados RDF e com grafos sintéticos para confirmar sua eficiência.