A última atividade presencial que fiz na PUC-Rio foi assistir a defesa de tese da Grettel Monteagudo Garcia , em 13/03/2020 (uma sexta-feira 13 !!!!).
O título da tese é “A Keyword-based Query Processing Method for Datasets with Schemas” e me interessou por causa do projeto do NIMA.
A proposta parte do cenário onde usuários possam consultar dados, armazenados em bancos de dados relacionais e TripleStores, de maneira semelhante ao Google, ou seja, digitando palavras-chave, e deixando para o sistema recuperar os dados que melhor correspondem ao conjunto de palavras-chave.
Na tese estão descritos um algoritmo e um framework projetados para processar consultas baseadas em palavras-chave para bases de dados com esquema, especificamente bancos relacionais e bases de dados em RDF.
A primeira etapa do algoritmo é a conversão do conjunto de palavras chaves em uma consulta abstrata explorando um esquema abstrato. Nesta etapa o principal desafio é achar onde a informação está (os matches das palavras) e entender a intenção do usuário (quais matches são relevantes) para escolher as respostas certas.
Não foi usada uma ontologia para enriquecer a lista de palavras chaves mas foi feito o uso de auto complete para sugerir palavras/expressões que existem na base de dados assim como uma word cloud com as palavras mais buscadas.
Para gerar uma resposta, é preciso utilizar o esquema do banco de dados de modo a relacionar as informações através relacionamentos (junções). Uma vez que a solução exata para o algoritmo de busca é NP-Completo (computacionalmente lento), foram propostas na tese três heurísticas para encontrar, selecionar e relacionar as informações de maneira eficiente.
1) Match Heuristic: descarta alguns matches por não considerá-los com probabilidade de serem relevantes para a busca do usuário. Para realizar os descartes, é levado em conta a similaridade do texto com os termos digitados pelo usuário e a ordem das palavras digitadas.
2) Nucleuses Heuristic: corresponde a um algoritmo guloso (greedy), no qual os matches são agrupados em núcleos, onde cada núcleo tem um pontuação que avalia o quão relevante é o núcleo para a pesquisa feita pelo usuário. Em seguida, o algoritmo guloso seleciona o menor conjunto de núcleos com a maior pontuação, que cobre todas as palavras digitadas pelo usuário.
3) Connection Heuristic, encontra o mínimo Steiner Tree entre os núcleos selecionados pelo algoritmo guloso. Se baseia no índice de caminho mínimo calculado usando uma variação do algoritmo do Floyd-Warshall
A segunda etapa do algoritmo (passo 6) é a conversão dessa consulta abstrata em uma consulta SPARQL ou SQL e sua execução no respectivo banco de dados.
Através de um mecanismo de feedback é possível refinar o resultado gerando novas respostas.
O framework foi criado com base no algoritmo e suas heurísticas além de permite a extensão para qualquer RDBMS ou baseado em RDF. As implementações das heurísticas foram feitas de forma flexível e têm como parâmetros várias funções para conseguir que um mesmo algoritmo funcione em diferentes bancos de dados.
Ao realizar a extensão para um banco de dados é necessário não só adaptar ao SGBD como também alimentar as informações do esquema abstrato a partir dos metadados do banco de dados.
Uma etapa de pré-processamento se fez necessária para a construção do índice de shortest-path, ou seja, encontrar os caminhos entre um par de nós do grafo.
A ferramenta se chama DANKE,
O trabalho compara os resultados e o desempenho obtidos com a implementação do algoritmo em bases de dados em RDF e bancos de dados relacionais, mais especificamente o Oracle, Postgres e Jena TDBA.
Algumas referências da tese que podem ser interessantes para a minha pesquisa em Buscas Semânticas
QIN, L.; YU, J. X.; CHANG, L. Keyword search in databases. In: Proceedings of the 35th SIGMOD international conference on Management of data -SIGMOD ’09. New York, New York, USA: ACM Press, 2009. retrieved <http://portal.acm.org/citation.cfm?doid=1559845.1559917>. accessed Jun./11/19. ISBN: 9781605585512, DOI: 10.1145/1559845.1559917
ELBASSUONI, S.; BLANCO, R. Keyword search over RDF graphs. In: Proceedings of the 20th ACM international conference on Information and knowledge management -CIKM ’11. New York, New York, USA: ACM Press, 2011. retrieved <http://dl.acm.org/citation.cfm?doid=2063576.2063615>. accessed Jun./12/19. ISBN: 9781450307178, DOI: 10.1145/2063576.2063615.
GKIRTZOU, K.; PAPASTEFANATOS, G.; DALAMAGAS, T. RDF Keyword Search based on Keywords-To-SPARQL Translation. In: Proceedings of the First International Workshop on Novel Web Search Interfaces and Systems -NWSearch ’15. New York, New York, USA: ACM Press, 2015. retrieved <http://dl.acm.org/citation.cfm?doid=2810355.2810357>. accessed Jun./12/19. ISBN: 9781450337892, DOI: 10.1145/2810355.2810357.
HAN, S. et al. Keyword Search on RDF Graphs -A Query Graph Assembly Approach. In: Proceedings of the 2017 ACM on Conference on Information and Knowledge Management -CIKM ’17. New York, New York, USA: ACM Press, 2017. retrieved <http://dl.acm.org/citation.cfm?doid=3132847.3132957>. accessed Jun./12/19. ISBN: 9781450349185, DOI: 10.1145/3132847.3132957
RIHANY, M.; KEDAD, Z.; LOPES, S. Keyword Search Over RDF Graphs Using WordNet. BT -Proceedings of the 1st International Conference on Big Data and Cyber-Security Intelligence, BDCSIntell 2018, Hadath, Lebanon, December 13-15, 2018. [s.l.]: [s.n.], 2018. retrieved <http://ceur-ws.org/Vol-2343/paper15.pdf>
ZHENG, W. et al. Semantic SPARQL similarity search over RDF knowledge graphs. Proceedings of the VLDB Endowment, [s.l.], vol. 9, no. 11, p. 840–851, 2016. ISSN: 21508097, DOI: 10.14778/2983200.2983201
========================================================================
Em 2021.2 o Casanova deu uma aula sobre a ferramenta implementada na tese.
O vídeo está aqui -> https://youtu.be/vHK1RcfU0lc
Abordagem baseada em esquema para RDF e RDB para consultas por palavras chaves
Estado da Arte: (1) EDBT, gera uma única Steiner Tree (não tem ranqueamento) e (2) Quick gera várias soluções interativamente
Steiner Tree mínima para gerar o menor número possível de joins em consultas SQL mas que sejam pelo menos um grafo conectado e cobrirem o maior número de palavras chaves.
Uso de buscas avançadas como expressões booleanas e filtros. Também possam fazer match com os metadados (esquema do RDB ou RDF schema). Considerar a ordem das palavras na lista de palavras chaves pode ter uma atribuição semântica diferente (heurística).
Fazer backtracking para respostas alternativas é a parte mais difícil do que automatizar.
Algoritmo
1) Representar o esquema RDF ou RDB em um esquema abstrato. Funções de conversão.
2) Match da palavra-chave com um string de caracteres se dá por uma função de semelhança entre dois literais.
3) Encontrar o conjunto resultante mínimo de matches (do item 2). É um problema NP-Completo e por isso foram usadas heurísticas
3.1) H Match: reduzir os matches
Buckets são listas invertidas criadas para Entidades (rótulo da classe - metadados), Propriedades (rótulo da coluna - metadados) e Valores (instâncias). A função de similaridade (scores) do bucket é repassda para a próxima fase.
3.2) H Nucleuses: reduzir o número de entidades (núcleos) envolvidas na resposta
Usar o esquema para agrupar os matches nos buckets para formar núcleos. O score do núcleo é a combinação linear dos buckets. Usar os núcleos de maior score.
3.3) H Connection: como encontrar o menor caminho entre as entidades (núcleos)
Fecho transitivo no grafo para achar o caminho dos grafos. A árvore de steiner não é arvore geradora pq não precisa ter todos os nós do grafo mas tem que juntar os nós do match / núcleos (ser conexo). O esquema conceitual é usado nesse ponto.
O índice de caminhos mínimos pode ser pré computado se o esquema é conhecido. OU seja, se já se sabe qual é o caminho mínimo entre entidade A e B é possível deixar a consulta armazenada. Se o match das palavras chaves for com a entidade A e B então basta executar a consulta filtrando as entidades (incluir no WHERE clause).
Dijkstra acha o menor caminho para cada nó de saída. Floyd-Warshall acha o menor caminho entre cada par de nós do grafo. Na adaptação foi necessário calcular todos os caminhos ....
Feedback do usuário para solicitar novas respostas usando Backtracking. Não repetir as respostas.
Implementação
Query Parser com expressões entre aspas.
Framework: sistema abstrato e conexão com 4 fontes de dados, 2 RDB e 2 RDF. Para cada fonte de dados, as funções de matching e de pré processamento são pontos de flexibilização (hot spots) pq são dependentes da tecnologia.
Avaliação
Três datasets em RDB e dois em RDF. Atenção a versão dos datasets para comparabilidade. Comparou entre RDB e RDF ...
Fiz um posto sobre a última referência dessa lista. Se o meu problema de pesquisa for realmente sobre Busca Semântica, posso continuar analisando as demais publicações.
ResponderExcluirPara o Busc@NIMA e Quem@PUC tanto a WordCloud quanto a sugestão de palavras na digitação da caixa de busca são funcionalidades que podem ser interessantes.
ResponderExcluirUm ponto essencial aqui que diferencia da proposta do Busc@ é que as queries SPARQL são fixas pq o objetivo final da busca é encontrar pesquisadores/professores de acordo com a sua expertise.
ResponderExcluirFiz um exercício dos meus objetivos de pesquisa baseado na proposta dela:
ResponderExcluirObjetivos da Pesquisa
Projetar uma solução que dada uma consulta com uma lista de palavras chaves recupere um conjunto de subgrafos correspondentes (ou mais próximos) a essa consulta limitado pelo contexto temático do buscador e ordenado por um esquema de pesos das propriedades do subgrafo.
Implementar uma solução flexível onde o contexto possa ser definido dinamicamente sem a necessidade de um filtro prévio da base de dados. A medida de similaridade seria parametrizável de acordo com o contexto da busca (tema) e aos critérios de ordenação das dimensões (propriedades) das entidades. A ordenação poderia ser global (única por esquema) ou local (de acordo com a consulta).
Avaliar a solução implementada através de experimentos com dados reais que contemplem múltiplos domínios.