Artigo SQL Magazine 38 - 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 Tabela 1 estão alguns exemplos de vencedores de prêmios Nobel e seus respectivos números de Erdös.

Tabela 1. Alguns vencedores de prêmios Nobel e seus respectivos números de Erdös.

Agora que o tema da análise foi proposto, mostraremos um estudo de caso na seção a seguir.

Primeiro estudo de caso: redes sociais

Com um olhar de analista de sistemas especialista em modelagem de dados, imaginamos como poderíamos representar as informações no diagrama da Figura 1 em um banco de dados relacional. A entidade que representa uma pessoa seria a tabela PERFIS. Como cada pessoa pode ter uma relação mútua com uma outra ou diversas outras pessoas, precisamos também de uma tabela associativa, a RELACOES. A Figura 2 ilustra o diagrama entidade-relacionamento em questão. Trata-se de um relacionamento recursivo do tipo rede (ver Nota 3).

Figura 2. Modelagem: tabela de perfis com relacionamento recursivo do tipo rede.

Nota 3. Resumo sobre relacionamentos recursivos

Um relacionamento recursivo acontece quando uma entidade refere-se a si mesma, e é ilustrado no caso em que uma empresa pode pertencer a outra. Neste tipo de relacionamento, a entidade (ou tabela) pai e a filho são a mesma. Existem duas variações de relacionamento recursivo:

·         Hierárquico (recursão unitária). Neste tipo de relacionamento, uma entidade (ou tabela) pai pode ter qualquer número de filhos, mas cada filho pode ter um único pai. Exemplo: empregado que possui um supervisor, que por sua vez será outro empregado e que terá diversos subordinados. Esse exemplo de relacionamento foi abordado no artigo “Árvores em PL/pgSQL” publicado na edição 35 da SQL Magazine.

·         Em rede (recursão dupla). Neste tipo de relacionamento, uma entidade (ou tabela) pai pode ter qualquer número de filhos, e um filho pode ter diversos pais. Exemplo: rede de relacionamentos, onde uma pessoa pode conhecer uma ou mais outras pessoas.