Banca de DEFESA: CIRO MORAIS MEDEIROS

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE : CIRO MORAIS MEDEIROS
DATA : 23/02/2018
HORA: 14:30
LOCAL: Auditorio I DIMAp
TÍTULO:

Avaliação Top-Down de Consultas de Caminhos Livres-de-Contexto em Grafos


PALAVRAS-CHAVES:

rdf; consultas em grafos; gramáticas LL.


PÁGINAS: 89
RESUMO:

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.
Daí surgiu 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 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 através 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.

Apresentamos 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. Mostramos 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.


MEMBROS DA BANCA:
Presidente - 1221251 - MARTIN ALEJANDRO MUSICANTE
Interno - 1639701 - MARCEL VINICIUS MEDEIROS OLIVEIRA
Interno - 1495704 - UMBERTO SOUZA DA COSTA
Externo ao Programa - 1845280 - SERGIO QUEIROZ DE MEDEIROS
Externo à Instituição - MARIZA ANDRADE DA SILVA BIGONHA - UFMG
Notícia cadastrada em: 25/01/2018 10:16
SIGAA | Superintendência de Informática - (84) 3215-3148 | Copyright © 2006-2019 - UFRN - sigaa07-producao.info.ufrn.br.sigaa07-producao