Artigo SQL Magazine 38 - Busca em redes sociais e árvores usando PL/pgSQL

Clique aqui para ler todos os artigos desta edição

Busca em redes sociais e árvores usando PL/pgSQL

Algoritmo do Orkut, Oráculo de Bacon, Número de Erdös e outras histórias

Rodrigo Hjort

Leitura obrigatória: “Árvores em PL/pgSQL: Recursividade em busca hierárquica”, Edição 35 da SQL Magazine

Que analista de sistemas nunca se viu imaginando como funcionariam os algoritmos de busca para a classificação de páginas no Google ou como seriam obtidas as ligações entre indivíduos em sites de relacionamento como o Orkut? Ou melhor: como seriam feitas as modelagens de dados para essas aplicações, se é que um SGBD relacional poderia ser usado? Os algoritmos teriam que ficar na camada de aplicativo ou de banco de dados? E quantos acadêmicos já se perguntaram “onde é que eu vou usar Teoria dos Grafos no dia-a-dia”? A análise a seguir tentará responder sucintamente essas questões, que aparentemente não são nada triviais.

Neste artigo será implementado no PostgreSQL um algoritmo de busca em largura em estruturas com relacionamento recursivo. Para isso, serão utilizados conceitos de Teoria dos Grafos aplicados com a construção de funções nas linguagens procedurais PL/pgSQL e SQL associadas a triggers e arrays.

A Figura 1 exemplifica o tipo de relacionamento tratado na análise. Numa rede social (ver Nota 1), cada nó representa um indivíduo, que por sua vez relaciona-se a um ou mais outros nós. Neste caso, Jack Nicholson seria o mais “popular”, pois está ligado, ou seja, relaciona-se, a outras seis pessoas. Em oposição, Angelina Jolie, Cameron Diaz e Kim Basinger são as que menos relações possuem: uma cada.

Nota 1. Definição de rede social.

Rede social é uma das formas de representação dos relacionamentos afetivos ou profissionais dos seres humanos entre si ou entre seus agrupamentos de interesses mútuos.

Figura 1. Estrutura de uma rede social: relacionamento entre indivíduos.

As instruções SQL contidas neste artigo foram executadas utilizando a ferramenta pgAdmin III (www.pgadmin.org), que já vem instalada com o PostgreSQL 8.1 no Windows e é facilmente instalada no Linux, FreeBSD ou Mac OS X. Além disso, estas instruções funcionam em qualquer aplicativo cliente do PostgreSQL, como psql, phpPgAdmin ou PgAccess, e em qualquer plataforma. Portanto, use a ferramenta que achar mais conveniente.

Um overview das aplicações

No início de 2004 o Google, que sempre trouxe inovações tecnológicas ao mundo da Internet, lançou uma nova onda na grande rede: os sites de relacionamento. Na realidade, já existiam diversos produtos semelhantes, como Friendster, Tribe e LinkedIn. Porém, o Orkut, criado por um funcionário do Google, um engenheiro turco chamado Orkut Büyükkokten, foi o que ganhou a maior popularidade, especialmente entre os usuários brasileiros.

Quem já visitou o serviço Orkut deve ter notado que, ao abrir o perfil de uma pessoa ainda não pertencente à sua rede, o sistema traz alguns possíveis mapeamentos para relacionar o indivíduo selecionado ao usuário atual. Por exemplo, é mostrado o seguinte texto: Fulano > Beltrano > Sicrano > Você. Foi baseada nesta idéia, a Teoria dos Seis Graus de Separação, que o Orkut foi desenvolvido. Sucintamente, esta teoria diz que todas as pessoas no mundo podem ser conectadas a qualquer outra por uma rede de no máximo cinco intermediários. Apesar de ser provado que ela estava errada, alguns estudiosos afirmam que essa teoria pode ajudar a esclarecer diversos fenômenos, como epidemias, modas culturais, comportamento dos mercados de ações e organizações que sobrevivem a mudanças.

Um segundo exemplo de aplicação para redes sociais é abordado no The Oracle of Bacon. O jogo, criado por um cientista da computação nos EUA, mostra como um ator, no caso Kevin Bacon, se relaciona com os demais artistas, sejam de filmes norte-americanos ou não. Alimentado periodicamente com informações provenientes do portal IMDB (Internet Movie Database), quando o usuário digita o nome de um determinado artista, o sistema faz um mapeamento entre ele e Kevin Bacon, exibindo os filmes em que tiveram participação juntos. Na Nota 2 é apresentado o resultado quando a atriz Audrey Tautou é especificada. Note que o sistema também informa o “Número de Bacon” do indivíduo, o qual se refere ao número de ligações entre os dois artistas.

Nota 2. Exemplo de resultado exibido no The Oracle of Bacon

Audrey Tautou has a Bacon number of 2.

Audrey Tautou was in Da Vinci Code, The (2006) with Tom Hanks

Tom Hanks was in Apollo 13 (1995) with Kevin Bacon

Para finalizar os exemplos, podemos citar o Erdös Number Project, um projeto que tem como objetivo estudar a colaboração nos trabalhos de pesquisa entre os cientistas. Na realidade, os “números de Erdös” sempre fizeram parte da cultura dos matemáticos contemporâneos. Paul Erdös (1913-1996), um dos maiores matemáticos do século passado, nasceu na Hungria e viajou o mundo escrevendo centenas de trabalhos nas mais diversas áreas do conhecimento, e muitos deles em colaboração com outros pesquisadores. Seu número de Erdös é 0. Os seus co-autores têm número de Erdös 1. Outras pessoas que publicaram algum trabalho em conjunto com pessoas que possuem número de Erdös 1, mas não com o próprio Erdös, possuem número de Erdös 2, e assim por diante. Se uma pessoa não possui ligação de co-autoria com Erdös, mesmo que de forma indireta, seu número de Erdös é dito infinito. Na "