Graph Modeling from Relational Databases

Silas P. Lima Filho Maria C. Cavalcanti Claudia M. Justel

Instituto Militar de Engenharia Instituto Militar de Engenharia Instituto Militar de Engenharia
Rio de Janeiro, RJ, Brasil Rio de Janeiro, RJ, Brasil Rio de Janeiro, RJ, Brasil
Email: silasplfilho@[Link] Email: yoko@[Link] Email: cjustel@[Link]

Abstract—The importance of mapping data from the relational O objetivo desse trabalho é mostrar que modelagens
model to other models and technology have been widely diferentes podem levar a conclusões diferentes. Em outras
discussed. Bring them to graph model is an example of that palavras, duas modelagens derivadas do mesmo conjunto de
discussion. The graph model allows to analyze the topology dados, podem identificar diferentes conjuntos de nós como
such as social networks, link prediction and recommendation mais centrais. A ideia é apoiar o usuário na consideração
systems. There are initiatives to map a relational database to de modelagens alternativas, identificando, a partir de um
a graph representation. However, they are not concerned with esquema conceitual do banco de dados, o que precisa ser
the different ways to generate a graph, especially when the explicitado como nó do grafo, de modo a permitir que
main objective is to perform topological analysis. This work as análises topológicas tragam resultados úteis. A principal
proposes some heuristics aiming a mapping systematization contribuição deste trabalho é a identificação de heurı́sticas
from relational model data to graph representation. The main que levam em consideração as análises topológicas inten-
contribution is to provide support for an adequate choice of cionadas. Elas foram identificadas com base nos resultados
the graph model, according to the analysis to be performed. obtidos de experimentos de análise topológica (e.g. medidas
Experiments are presented and show interesting results includ- de centralidade) sobre diferentes modelagens.
ing heuristics to support the user on the graph model choice. Este artigo se divide da seguinte maneira. Na seção
2 estão apresentados os elementos necessários para o en-
tendimento do trabalho. Na seção 3 estão relacionados os
Index Terms—Data Models, Social Networks, Graph Analysis, trabalhos que consideram o mesmo problema aqui abor-
Relational Data Modeling dado. A contribuição do trabalho é descrita na seção 4.
O método utilizado para mapear um banco relacional para
um grafo é apresentado na seção 5, assim como o modo
1. Introdução como as heurı́sticas foram construı́das. Em sequência, os
experimentos iniciais usando conjuntos de dados menores
Uma das principais razões para converter dados armaze- são detalhados na seção 6. Um experimento maior com
nados em bancos de dados relacionais em uma representação o intuito de confirmar o comportamento dos experimentos
em grafo é para facilitar a tomada de decisão. Por décadas, anteriores é feito na seção 6.3. Finalizando, na seção 7, com
o modelo de grafos tem sido amplamente explorado para a conclusão do trabalho realizado com pontos destacados,
fins de análises topológicas. Existem vários algoritmos possı́veis de trabalhos futuros.
e aplicações na literatura. Normalmente, esses algoritmos
são utilizados no contexto de redes sociais, sistemas de 2. Fundamentos Básicos
recomendação, predição de ligações e outros.
Com o crescimento da disponibilidade de grafos na Web Nessa seção, parte do fundamento teórico necessário
de Dados, e com o surgimento de novas tecnologias, o uso para o desenvolvimento do trabalho é apresentado.
de grafos e parte de sua teoria tem sido aplicada em dados
disponı́veis na Web, como na iniciativa Linked Data. Nessa 2.1. Análise de Redes Sociais
direção, algumas alternativas para mapear dados relacionais
para grafos RDF surgiram, como o D2R [1]. No entanto, As redes sociais têm sido amplamente usadas nos
essa abordagem foca em um mapeamento sintático e não nas últimos tempos, devido a sua aplicação na solução de diver-
questões de modelagem de grafos. Por outro lado, existem sos problemas que envolvem relacionamentos entre pessoas
trabalhos que analisam a modelagem de grafos, como por ou objetos. Existem diferentes maneiras de analisar uma
exemplo [2], [3] e [4]. No entanto, os autores utilizam uma rede social. O foco deste trabalho é fazer uma análise
abordagem especı́fica que não leva em consideração alter- topológica de uma rede. Ou seja, a rede será modelada
nativas de modelagem e as consequências da modelagem como um grafo, e serão aplicados algoritmos para determi-
escolhida em alguma análise topológica. nar informações sobre grau de nós, caminhos e distâncias

c 2017 IEEE
978-1-5386-3057-0/17/$31.00 
Authorized licensed use limited to: Universidad Federal de Pernambuco. Downloaded on December 09,2024 at [Link] UTC from IEEE Xplore. Restrictions apply.
entre pares de nós. Uma das possı́veis análises topológicas [8] é amplamente usado para criar esquemas lógicos, onde
consiste em determinar a influencia dos nós na rede levando tabelas são definidas como estruturas que irão efetivamente
em consideração a quantidade de conexões entre eles. Es- armazenar os dados.
sas conexões (relações) permitem determinar quais nós são Diferente da modelagem de um banco de dados, cujo
mais ou menos relevantes, ou podem transmitir informação alvo é o armazenamento e gerenciamento de dados, a mo-
que trafega pela rede. Diferentes medidas de centralidade delagem em grafos é direcionada para a análise topológica
foram definidas na literatura para permitir essas análises. dos dados, como no caso de análise usando medidas de
São apresentadas a seguir as medidas que serão utilizadas centralidade. A necessidade de atender ambos os objetivos,
neste trabalho. o armazenamento/gerenciamento e a análise topológica, per-
Seja G = (V (G), E(G)) um grafo que representa uma mitiu a criação dos Sistemas de Gerenciamento de Banco de
rede. A centralidade de Grau é simplesmente a medida Dados Orientado a Grafos (SGBDG). Esses sistemas usam
definida como a quantidade de arestas conectadas a um nó uma estrutura de um grafo para armazenar os dados. Neo4J1
x ∈ V (G), formalmente, Cd (x) = |Γ(x)|, onde Γ(x) é o é um dos GDBMS mais usados na atualidade.
subconjunto de vértices em V (G) adjacentes a x. A medida Em [9] Rodriguez analisa diferentes estruturas de grafos,
Proximidade leva em consideração a distância de um de- algumas das quais permitem representar diferentes carac-
terminado nó para todos os outros nós do grafo e é definida terı́sticas para os nós e arestas, tais como rótulos, atributos,
como a soma dos inversos das distâncias entre x e todos1 os peso, etc. Nesse artigo, é apresentada uma classificação
nós do grafo. Formalmente Cc (x) = s∈V (G),s=x d(x,s) , hierárquica, onde as estruturas de grafos são organizadas
onde d(x, s) é a distância (comprimento do menor ca- de acordo com a sua expressividade (número de carac-
minho) entre os nós x, s em V (G). A centralidade de terı́sticas permitidas). O grafo de propriedades (property
Intermediação mede a quantidade de vezes que um nó x graph), é a estrutura mais usada por algumas ferramentas de
estará presente no menor caminho entre outros dois nós manipulação (e.g. Neo4j), devido a sua alta expressividade.
do grafo, s, t. Nós com valor de intermediação alto são Grafos podem ser modelados a partir de alguns elemen-
mais propensos a controlar o fluxo de informação no grafo. tos de um banco de dados. Para atingir o objetivo de mapear
 nx
Formalmente, Cb (x) = s,t
s=t=x∈V (G) gs,t , onde nxs,t é o os elementos de um banco de dados relacional para um
número de caminhos mı́nimos entre os nós s e t que contém grafo, é necessário utilizar os dois esquemas, conceitual e
o nó x; e gs,t é o número total de caminhos mı́nimos entre os lógico. O usuário pode usar esses esquemas para identificar
nós s e t, ∀s = t ∈ V (G). As medidas de centralidade Hub e quais itens serão representados como vértices e que tipo de
Autoridade são definidas para redes direcionadas. Newman referências serão arestas no grafo. Porem, essa não é uma
[5] afirma que nós com alta centralidade são aqueles que tarefa fácil, especialmente, quando há diversas análises que
são apontados por outros nós com centralidade alta. Porém podem ser realizadas. No entanto, até aonde foi possı́vel
também é possı́vel ter um nó com alta centralidade quando investigar, não achamos métodos ou guias que ajudem o
ele aponta para nós de alta centralidade. Dessa forma podem usuário em tal tarefa, levando em conta a análise desejada
ser definidos dois tipos de nós centrais numa rede direcio- sobre o grafo.
nada, Authoridade e Hub. Esses conceitos foram criados
para identificar páginas relevantes na Web, baseados na ideia 3. Trabalhos Relacionados
de reconhecer páginas com muitas conexões a outras páginas
que por sua vez altamente conectadas. Na literatura existem métodos diferentes com o objetivo
de modelar um grafo a partir de um modelo de banco de
2.2. Modelagem de Bancos Relacionais e de Grafos dados relacional. Por exemplo, em [2] é tratado o problema
de modelagem de um grafo procurando pela melhora da per-
Heuser [6] afirma que um modelo de dados deve ser formance de uma consulta num banco de dados em grafos.
expressivo o suficiente para criar esquemas de dados, isto Outro artigo, [3], procura evitar perda semântica durante a
é, de modo a refletir objetos do mundo real. Modelar um modelagem. Já em [4] o objetivo é evitar redundância nos
esquema de banco de dados é uma tarefa que normalmente dados.
abrange duas etapas com diferentes nı́veis de abstração: A ideia principal do artigo de Wardani e Küng, [3], é
conceitual e lógico. Estas duas etapas são necessárias em construir um grafo o mais próximo possı́vel ao esquema
razão da complexidade da realidade que o usuário encarre- conceitual do banco de dados relacional, evitando perdas
gado da modelagem pretende representar. A idéia principal é semânticas. Os autores usam os dois esquemas, conceitual
conduzir o usuário desde a realidade até alguma estrutura de e relacional, para criar regras de mapeamento especı́ficas,
dados lógica que pode representar objetos reais. O Modelo como o uso de atributos de chave estrangeira para mapear
ER [7] é frequentemente usado para modelar esquemas a(n) relacionamentos/arestas entre pares de nós. A partir
conceituais, onde objetos e relacionamentos do mundo real dessas regras, o grafo pode ser construı́do.
são representados como entidades (classes de objetos) e De maneira semelhante, o artigo de De Virgilio et al.,
seus tipos de relacionamento (veja a Figura 2). Em um [10], começa com uma análise do esquema relacional. E
segundo momento estas entidades e relacionamentos são
mapeados para um esquema lógico. O Modelo Relacional 1. [Link]

Authorized licensed use limited to: Universidad Federal de Pernambuco. Downloaded on December 09,2024 at [Link] UTC from IEEE Xplore. Restrictions apply.
num outro artigo, [2], os mesmos autores destacam a neces- as mesmas, aquela que será mais útil para suas análises.
sidade de fazer uma análise cuidadosa a partir do esquema
conceitual ER, de modo a resolver possı́veis conflitos ao 4. Contribuição
agregar entidades e relacionamentos. Para tal fim, propõe
primeiramente o resgate do esquema conceitual ER a partir Neste trabalho assume-se que é possı́vel derivar um es-
do esquema relacional. Com base nessa representação é con- quema ER de um esquema relacional, oriundo de um banco
cebido um grafo ”template” associado ao esquema lógico de dados relacional usando técnicas de engenharia reversa
de dados a serem utilizados. Nesse esquema, as entidades [6]. Essa técnica é utilizada normalmente quando o banco já
e relacionamentos são convenientemente agrupados, respei- está implementado. O esquema lógico traz informações de
tando as restrições de integridade referencial definidas no quais tabelas estão implementadas fisicamente no banco e é
esquema relacional, e algumas regras definidas pelo autor. o primeiro a ser obtido no processo de engenharia reversa.
A ideia é agrupar entidades cujas instâncias irão aparecer Em seguida, é obtido o esquema ER. Dessa forma, a partir
juntas em algum resultado de consulta, otimizando dessa de um esquema ER, e para cada par de entidades (E1 , E2 ),
forma o processamento dessas consultas. que contém um relacionamento (R) entre elas no esquema,
Enquanto os métodos previamente descritos propõem aplica-se um conjunto de heurı́sticas H . Cada heurı́stica leva
a criação de um grafo de propriedades, Bordoloi et al., em conta o tipo de análise que se deseja realizar. Baseado em
[4], apresentam um método de construção de um hiper- tais análises, o modelador é motivado a pensar nos vizinhos
grafo que parte de um esquema relacional. Inicialmente, das entidades e nos atributos dos relacionamentos como
são construı́dos grafos estrela e grafos de dependência, potenciais vértices do grafo. Dependendo da análise que
mostrando as relações de dependência entre os atributos para será feita, uma exploração maior no esquema é incentivada
cada tabela. Depois, esses grafos são unidos formando um para que se obtenha um grafo mais rico em informações.
único hipergrafo. Semelhante ao grafo chamado ”template” A Figura 1 resume bem a proposta deste trabalho e seu
no artigo de De Virgilio, [2], este hipergrafo representa contexto que se resume em: dado um esquema lógico (de-
o esquema do banco, onde os nós são os atributos das notado por EL), extrai-se o esquema conceitual (denotado
tabelas, e as arestas representam as dependências entre os EC). Aplicando o conjunto de heurı́sticas H sobre EL, e
atributos. Com base nesse hipergrafo, poderia ser gerado o ainda considerando o tipo de análise A que se pretende
hipergrafo dos dados, onde cada valor de atributo nas tuplas fazer, gera-se um conjunto de regras de mapeamento RM,
das relações passa a ser um nó, e as relações de dependência responsável por traduzir/transportar as tuplas do esquema
também são instanciadas. No entanto, este é um grafo relacional em vértices e arestas do grafo G.
complexo, com muitos nós. Para reduzir este grafo e evitar Podemos separar as etapas da migração, representados
redundância de nós, o método proposto inclui uma análise de na Figura 1 da seguinte maneira:
domı́nios comuns entre os atributos. Então, outro hipergrafo 1o - Dado um banco de dados, extrair o esquema rela-
esquema é construı́do levando em conta aquela análise, no cional EL. Nesse esquema estão representadas as relações
qual atributos do mesmo domı́nio, que apareçam em tabelas (tabelas), as ligações entre si, a definição dos atributos,
diferentes, são representados de maneira única. Finalmente, a conexão de tais atributos como chave estrangeira e as
um hipergrafo de dados, no qual um nó representa um valor restrições aplicadas a todo o conjunto.
de um domı́nio especı́fico, é construı́do baseado no hiper- 2o - Uma vez extraı́do EL, gerar o esquema conceitual
grafo esquema. Embora nesta abordagem todos os valores EC usando engenharia reversa. Por ser a abstração dos dados
atributos podem ser analisados, o hipergrafo não é fácil de que mais se aproxima da realidade a qual se quer modelar,
tratar, pois muitas das ferramentas e algoritmos não admitem o esquema conceitual é de mais fácil utilização.
este tipo de estrutura como entrada. 3o - Na etapa de geração de regras de mapeamento
Um trabalho recente de Xirogiannopoulos et al., [11], são utilizados como entrada, o esquema conceitual EC, o
apresenta uma ferramenta de extração de dados de um banco esquema relacional EL, o conjunto de heurı́sticas H, um
de dados relacional para um modelo em grafo, denominada conjunto de análises A da qual algumas serão escolhidas,
GraphGen, que permite ao usuário realizar análise do grafo, além de contar com a interação do usuário para selecionar
ou executar algoritmos usando o grafo obtido como entrada. os elementos do banco que serão levados em conta para a
Essa ferramenta utiliza a linguagem DSL, que é baseada em análise. Utilizando como base EL e EC, o usuário deve
Datalog, para realizar as extrações do banco relacional. Este informar quais entidades de EC serão mapeadas para o
trabalho é o único dos achados que discute a relevância grafo. O usuário também deve escolher o tipo de análise
de obter diferentes modelos de grafos a partir do mesmo que será realizado sobre o grafo. O conjunto de heurı́sticas
conjunto de dados. Porém, não conduz o usuário para fazer criado na geração das RM é útil para guiar o usuário na
a escolha desses modelos. escolha da modelagem desejada.
No entanto, mesmo que o usuário consiga fazer análises 4o - Com as etapas ‘preparatórias’ concluı́das, são gera-
sobre o grafo extraı́do (modelagem escolhida), não há um das as regras de mapeamento RM, que consistem num con-
estudo sobre o impacto dessa escolha, nos resultados das junto de algoritmos e procedimentos para fazer a migração
análises. Assim, embora o usuário tenha a liberdade de de dados do banco no grafo. Nessa etapa, são identificadas
escolher a modelagem do grafo, sente-se a necessidade de as instâncias de entidades e relacionamentos do banco de
garantir que ele explore as alternativas, identificando entre dados que serão representados no grafo.

Authorized licensed use limited to: Universidad Federal de Pernambuco. Downloaded on December 09,2024 at [Link] UTC from IEEE Xplore. Restrictions apply.
 Figura 1. Fluxo utilizado para a escolha de uma modelagem de grafos

A principal contribuição deste trabalho é mostrar que a

escolha do modelo do grafo deve levar em consideração a
análise a ser realizada. Na próxima seção são apresentados
os experimentos realizados e os bancos de dados utilizados.
Em cada experimento foram usadas diferentes modelagens
de grafos para analisar medidas de centralidade. Nos dois
primeiros experimentos foram extraı́das heurı́sticas. O ter-
ceiro experimento foi utilizado para validar os resultados
das medidas de centralidade obtidos neste caso usando as
Figura 2. Situação tı́pica em esquemas conceituais: duas entidades e vários
heurı́sticas produzidas no segundo experimento. relacionamentos.

5. Preparação para os Experimentos

No sentido de guiar o usuário na escolha da modelagem
em grafo entre as alternativas, um conjunto de experimentos
foi realizado. Estes estão relatados na próxima seção. Para
realizá-los, foi necessário tomar como ponto de partida um Figura 3. Situação tı́pica em esquemas conceituais: duas entidades e um
esquema conceitual (EC). Usualmente, um esquema con- relacionamento n:m.
ceitual tem várias entidades e relacionamentos, mas nesse
estudo realizado, foram escolhidas duas situações de mode- avaliação, foi possı́vel identificar heurı́sticas genéricas que
lagem comuns (recortes), que aparecem com frequência nos visam ajudar neste processo. Em outras palavras, essas
projetos de banco de dados. O primeiro recorte escolhido heurı́sticas poderão ser usadas para apoiar os usuários na
(a) consiste de um par de entidades (E1 , E2 ) com n escolha da modelagem mais útil.
relacionamentos. O segundo recorte escolhido (b), envolve
A Figura 4 exibe um fluxo de construção de uma
um par de entidades (E1 , E2 ) e apenas um relaciona-
heurı́stica. A partir de um conjunto de dados (BD) e de um
mento binário n:m R, ao qual está associado um atributo
esquema conceitual (EC), são geradas diferentes alternativas
multivalorado A.
de modelagem de grafos (G1 , G2 , ..., Gn ), e para cada uma
As Figuras 2 e 3 mostram estes recortes utilizando o
dessas alternativas, são aplicadas análises pré-selecionadas
modelo ER. Neste trabalho, apenas estes dois recortes foram
(A1 , A2 , ..., An ). A partir dos resultados de cada grafo,
analisados. Porém, vale mencionar, que um esquema pode
(Ri (Gi , Ai ), 1 ≤ i ≤ n), foi possı́vel compará-los e definir
ser visto como um conjunto de recortes, que podem ser
uma heurı́stica (H ).
analisados, um de cada vez, de modo incremental.
Os experimentos deram-se da seguinte forma: escolheu-
se um banco de dados, e a partir de um recorte de seu 6. Experimentos
esquema conceitual (extraı́do a partir de seu esquema lógico)
foram geradas diferentes alternativas de modelagem em As próximas subseções apresentam os experimentos re-
grafo. Para cada grafo, foi aplicado um conjunto de análises alizados e seus resultados, bem como as heurı́sticas identifi-
topológicas. O objetivo desses experimentos foi avaliar o cadas. Os bancos de dados escolhidos para os primeiros ex-
impacto que cada alternativa de modelagem teve nos re- perimentos foram intencionalmente de pequeno porte, para
sultados de análises realizadas sobre elas. E, a partir desta explorar como as diferentes alternativas de modelagem de

Authorized licensed use limited to: Universidad Federal de Pernambuco. Downloaded on December 09,2024 at [Link] UTC from IEEE Xplore. Restrictions apply.
 Figura 4. Fluxo para definição de uma heurı́stica em um experimento

dados em grafos podem impactar nas análises que se objetiva primeira etapa, o grafo analisado (Modelagem 1), que é
fazer. Embora existam diferentes tipos de grafos, para este apresentado na Figura 6, foi gerado com nós representando
trabalho foi utilizado o grafo de propriedades, apresentado pessoas, e arestas representando ambos os tipos de relacio-
na seção 2.2. Os motivos da escolha são: permitir uma maior namento. Na segunda etapa, o grafo analisado (Modelagem
liberdade de modelagem e o fato desse tipo de grafo ser 2) foi similar ao primeiro, mas neste não foram consideradas
usado largamente na literatura. as arestas que representam o relacionamento “Lutou com”,
Os experimentos foram realizados com grau de dificul- mantendo assim a rede de amizade original do conjunto de
dade crescente, aumentando também a quantidade de dados Zachary, como mostra a Figura 7. O resultado das análises
usados. As análises topológicas escolhidas para os experi- realizadas com as duas modelagens pode ser conferido na
mentos foram medidas de centralidade, que são comumente Tabela 1.
usadas para análise de redes sociais. Para o armazenamento dos dados, utilizou-se o software
Neo4j. Enquanto que para o cálculo das medidas utilizou-
6.1. Experimento Zachary se a ferramenta de manipulação e visualização de grafos,
Gephi.
No experimento Zachary, utilizou-se uma base de da-
dos sobre os relacionamentos dos membros de uma aca-
demia de karatê criado a partir da rede de Zachary [12].
Nesse conjunto, os membros de um clube de karatê podem
relacionar-se de duas formas, pelo relacionamento “Amigo
de” ou então pelo relacionamento “Lutou com”, este último
visando representar resultados de lutas em campeonatos e
torneios.

Figura 6. Modelagem 1 para o Experimento Zachary.

Modelagem 1 Modelagem 2
Nó Intermediação Proximidade Grau Intermediação Proximidade Grau
1 152,19 1,6 16 231,0 1,758 16
Figura 5. Esquema conceitual do Banco de Dados para o Experimento 34 102,99 1,66 17 160,5 1,81 17
Zachary. 4 12,5 2 7 6,2 2,15 6
22 24 1,9 6 0 2,6 2
24 14,6 2,0 8 9,3 2,5 5
A Figura 5 representa o esquema conceitual do banco 30 9,7 1,9 7 1,5 2,6 4
Tabela 1. R ESULTADOS DAS MEDIDAS DE CENTRALIDADE PARA AS
relacional usado nesse experimento. O esquema é similar DUAS MODELAGENS DO E XPERIMENTO Z ACHARY.
ao recorte (a), onde E1 == E2 == P essoa e os auto-
relacionamentos “Amigo de” e “Lutou com” do esquema,
representam os dois tipos de relacionamento que podem
existir entre as pessoas. 6.1.1. Análise dos Resultados. Observando os resultados
Esse experimento foi dividido em duas etapas para aten- na Tabela 1 podemos concluir que o experimento demons-
der às duas alternativas de modelagem a serem investigadas. tra a influência da modelagem escolhida nas medidas de
Em ambas foram analisadas algumas medidas de centra- centralidade obtidas. Dependendo da modelagem escolhida,
lidade, sendo elas intermediação, proximidade e grau. Na informações importantes para a análise do usuário devem

Authorized licensed use limited to: Universidad Federal de Pernambuco. Downloaded on December 09,2024 at [Link] UTC from IEEE Xplore. Restrictions apply.
 23 16 nas uma entidade tenha sido considerada, de modo mais
21
genérico, a mesma observação deve ser feita em uma
29
10 34
27 situação de modelagem onde banco de dados envolve duas
31
30
19
entidades distintas, que possuam mais de um tipo de relaci-
20
9 22
onamento entre elas.
33
32
Mesmo usando algumas medidas de centralidade para
2 3
26
descobrir quais são os nós mais centrais, a descoberta de
14
tais nós não chegou a ser um fator de influência direta para
15 28
18
8 4 24
a obtenção da primeira heurı́stica. O valor de cada medida
1
12 de centralidade de cada nó foi comparado para as duas
13
11 7 modelagens. E desse estado então, foi compreendido que a
5
25 escolha de relacionamentos pode interferir na determinação
6
dos nós mais centrais do grafo. A conclusão mais relevante
17
neste experimento foi o entendimento da diferença entre
relacionamentos e sua semântica, pois dependendo da forma
Figura 7. Modelagem 2 para o Experimento Zachary. de representação, afetará o resultado da análise das medidas
de centralidade utilizadas.

ser consideradas ou não. No caso da Modelagem 2, onde 6.1.2. Heurı́stica 1. A partir da conclusão obtida no experi-
são analisados apenas os relacionamentos de amizade, os mento Zachary, foi obtida uma heurı́stica que será apresen-
nós 1 e 34 são os mais centrais segundo a medida de tada a seguir. Dadas duas entidades E1 e E2 de um esquema
centralidade intermediação. Na Modelagem 1, por mais que conceitual EC , não necessariamente distintas, que se rela-
os nós mais centrais continuem os mesmos, houve uma cionam por relacionamentos distintos R1 , R2 , ..., Rn . Se a
mudança significativa nos valores de centralidade dos nós 4, análise a ser realizada tem como foco um relacionamento Ri
22, 24 e 30. Esta mudança pode ser interpretada da seguinte a ser modelado no grafo, então para todo j = i tal que Rj
forma, tais nós representam pessoas que participaram de tenha a mesma relevância semântica2 que Ri , Rj também
vários torneios e lutas, como é o caso do nó 22, cujo deve ser modelado no grafo. Ou mais formalmente, como
valor do grau e de intermediação teve a maior alteração. se segue.
Assim, caso o modelador deseje encontrar os lutadores de Sejam:
maior visibilidade social no grafo, deve levantar todas as • G = (V, A); grafo
relações envolvendo os lutadores. Se achar que a relação • EC = (E, R); esquema conceitual
de amizade é a mais útil para identificar os lutadores, então • E = {E1 , E2 , ..., Ep }; conjunto de entidades do
esta deve ser considerada. Mas, se a visibilidade social pode esquema EC
ser alcançada também com as relações de luta, esta deve ser • R = {R1 , R2 , ..., Rq }; conjunto de relacionamentos
considerada além da relação de amizade. Assim, ambas as do esquema EC
relações (amizade e luta) devem ser representadas no grafo. • Ei = {e1i , e2i , ...}; conjunto de instâncias da entidade
De modo mais genérico, esta situação de modelagem Ei
pode envolver duas entidades distintas, que possuam mais • Rk = {rk1 , rk2 , ...}; conjunto de instâncias do relaci-
de um tipo de relacionamento entre elas. Em casos onde onamento Rk
existam muito mais que dois tipos de relacionamentos en- • rkz = (exi , eyj ); um instância de R conecta um par de
tre duas entidades, a consequência gerada nos valores das instâncias de entidades de E
medidas de centralidade pode ser muito mais significativa.
Em tais casos, uma análise cuidadosa por parte do usuário Dado que:
sobre quais relacionamentos são semanticamente relevantes, • E1 , E2 ∈ E; ex1 ∈ E1 ; ey2 ∈ E2 ;
deve ser feita. • R1 ∈ R ;
À medida que mais tipos de relações são considerados, • r1z ∈ R1 ; r1z = (ex1 , ey2 );
mais arestas surgirão no grafo, e naturalmente as medidas
de centralidade serão impactadas. Assim, se o objetivo é No mapeamento para o grafo G temos:
encontrar os nós mais centrais ou de maior intermediação, • ∀ex1 ∈ E1 , ex1 ∈ V ;
por exemplo, é preciso analisar para o contexto dos dados • ∀ey2 ∈ E2 , ey2 ∈ V ;
em questão, quais os tipos de relacionamento que devem • ∀r1z ∈ R1 , r1z ∈ A;
ser levados em consideração. Em geral, há uma diferença • Se ∃j = 1 | rjc = (ea1 , eb2 ) e Rj ≈ R1 então ∀rjc ∈
semântica entre os dois tipos de relacionamento, e é o que Rj ; rjc ∈ A
justifica o fato de serem representados de modo distinto no
A Figura 8 ilustra a escolha dos relacionamentos
banco de dados. Mas, se para fins da análise da rede, ambos
Ri , ...Rj entre as entidades E1 e E2 do esquema conceitual
podem ser considerados semanticamente relevantes, então
ambos devem ser representados no grafo. 2. Obs: o simbolo ≈ foi usado com o significado de semanticamente
Embora no banco de dados usado no experimento, ape- relevante.

Authorized licensed use limited to: Universidad Federal de Pernambuco. Downloaded on December 09,2024 at [Link] UTC from IEEE Xplore. Restrictions apply.
que serão utilizados para construir um grafo onde cada nó uma modelagem em grafo. Em todas as etapas foram ana-
representa uma entidade, e cada aresta representa um dos lisadas as seguintes medidas topológicas para os nós do
relacionamentos escolhidos. grafo obtido: intermediação e proximidade. Foram também
medidos o valor de hub e autoridade de cada nó, utilizando
a orientação das arestas do grafo.
Na primeira etapa, da mesma forma que no experimento
Zachary, as entidades do esquema conceitual são transfor-
madas em nós no grafo. Agora, existem dois tipos de nós,
Pessoa e Filme, e os relacionamentos são transformados
Figura 8. Representação da heurı́stica obtida no Experimento Zachary em arestas no grafo. Também agora existem dois tipos de
relacionamento, Atuação e Direção. A Figura 10 ilustra
o grafo obtido nessa etapa (Modelagem 3). No caso do
relacionamento Atuação do modelo ER, temos um atributo
6.2. Experimento SMDB Papel associado. Essa informação é mantida no grafo como
atributo de aresta.
Nesse experimento, utilizou-se um subconjunto de dados
do banco de dados disponibilizado pela ferramenta Neo4j
para introduzir a linguagem Cypher, responsável por re-
alizar as consultas no banco. Nesse banco, são mantidas
informações sobre dois tipos de entidades (pessoas e filmes),
e os distintos relacionamentos entre essas duas entidades.
Foram usados apenas os relacionamentos sobre ações de Figura 10. Esquema do grafo para a Modelagem 3
atuação e direção das pessoas dessa base. O esquema con-
ceitual do banco relacional pode ser visto na figura 9. Na segunda etapa, diferente do experimento Zachary,
os relacionamentos foram transformados em nós. Assim, o
grafo nessa etapa possui quatro tipos distintos de nós. Nessa
modelagem os relacionamentos não possuem atributos ou
rótulos, todos eles estão no mesmo nı́vel. Existem arestas
entre os nós Pessoa e Atuação, Atuação e Filme, Filme e
Direção e entre Direção e Filme. A Figura 11 representa o
esquema do grafo (Modelagem 4).

Figura 9. Esquema conceitual do Banco de Dados para o Experimento

SMDB. Figura 11. Esquema do grafo para a Modelagem 4

Para a realização desse experimento, não foram usadas Na terceira etapa, a modelagem mantém os mesmos
as mesmas ferramentas do experimento Zachary. As medidas tipos de nós e arestas que a modelagem 4, mas foi inserido
de centralidade foram calculadas usando Gephi 3 e os dados um novo tipo de nó que representa cada tipo de atuação que
foram armazenados usando Neo4j. Nesse experimento, foi um mesmo ator teve no filme, Papel, e novos tipos de aresta
analisado uma situação de modelagem semelhante ao recorte entre nós Ator e Papel, e entre os nós Papel e Filme. Isto
(b), descrito na seção 5, onde o esquema conceitual possui é, no caso dos nós do tipo Atuou em em que um ator fez
um par de entidades (E1 , E2 ) ligados por dois relaciona- mais de um papel no mesmo filme, incluı́mos novos nós que
mentos binários. deixam explı́citos todos os papéis representados pelo ator.
Embora a situação de modelagem de BD seja semelhante A Figura 12 representa o esquema do grafo nessa terceira
à situação do primeiro experimento, neste caso, temos duas etapa (Modelagem 5).
entidades distintas, além de dois relacionamentos distintos a
considerar. A partir desta situação de modelagem de BD foi 6.2.1. Análise dos Resultados. As Tabelas 2, 3 e 4 mostram
possı́vel explorar três variações de modelagens em grafo, os resultados obtidos para as medidas de centralidade pro-
considerando a explicitação das relações como nós, e de ximidade, intermediação, autoridade e hub dos grafos cons-
atributos como nós. truı́dos usando as três modelagens do experimento SMDB.
Assim, esse experimento foi dividido em três etapas. Para o cálculo das centralidades, foram consideradas as
Cada etapa considerou uma forma de migração, isto é, opções de grafo não direcionado e direcionado. Os nós
identificados nas tabelas correspondem aos 5 que tiveram
3. [Link] maior valor de centralidade em cada caso.

Authorized licensed use limited to: Universidad Federal de Pernambuco. Downloaded on December 09,2024 at [Link] UTC from IEEE Xplore. Restrictions apply.
 Modelagem 4
Não Direcionado Direcionado
Proximidade Intermediação Autoridade Hub
Richard Harris Tom Hanks A Few Good Men Aaron Sorkin
Clint Eastwood A few good men Jerry Macguire Al Pacino
Chris Columbus Cloud Atlas Speed Racer Andy Wach.
ACTED IN ACTED IN The Green Mile
ACTED IN Keanu Reeves Stand By Me
DIRECTED Jack Nicholson A League Their Own
Dina Meyer The Green Mile Cloud Atlas
Tabela 3. R ESULTADOS DAS MEDIDAS DE CENTRALIDADE PARA
MODELAGEM 4 NO EXPERIMETO SMDB

Figura 12. Esquema do grafo para a Modelagem 5 Modelagem 5

Não Direcionado Direcionado
Modelagem 3 Proximidade Intermediação Autoridade Hub
Não Direcionado Direcionado Richard Harris Tom Hanks Cloud Atlas Aaron Sorkin
Proximidade Intermediação Autoridade Hub Clint Eastwood Cloud Atlas A few good men Al Pacino
Clint Eastwood Tom Hanks A few good men Aaron Sorkin Chris Columbus A few good men Jerry Macguire Andy Wach
Richard Harris A few good men Jerry Macguire Al Pacino English Bob Keanu Reeves Speed Racer
Chris Columbus Cloud Atlas Speed Racer Andy Wach. Bill Munny The Green Mile The green mile
Dina Meyer Keanu Reeves The Green Mile Annabella Sci. DIRECTED Jack Nicholson Stand By Me
Ice-T Jack Nicholson Stand By Me Dina Meyer Hugo Weaving A League Their Own
Tabela 2. R ESULTADOS DAS MEDIDAS DE CENTRALIDADE PARA Ice-T ”Paul Edgecomb” Sleepless in Seattle
M ODELAGEM 3 NO EXPERIMENTO SMDB Tabela 4. R ESULTADOS DAS MEDIDAS DE CENTRALIDADE PARA
MODELAGEM 5 NO EXPERIMENTO SMDB

O experimento apresentado nesta seção difere do expe-

rimento da seção 6.1 no que se refere à representação das ranking.
entidades e relacionamentos no grafo, o que altera signifi- Em outras palavras, atributos de um relacionamento
cativamente os resultados das medidas de centralidade. no esquema conceitual podem aumentar a importância das
Para as medidas de Proximidade e Intermediação, os entidades nas análises, e por isso é importante avaliar se
três nós com maior valor de centralidade são os mesmos. devem ser representados como nós o como arestas do grafo.
Já nas modelagens 3 e 4 é possı́vel notar uma mudança
entre o segundo e terceiro colocados. Na modelagem 5, o nó
que representa o filme Cloud Atlas toma a segunda posição 6.2.2. Heurı́stica 2. A partir das observações mencionadas
mais alta no ranking de intermediação, que era ocupada na no experimento SMDB, foi obtida uma heurı́stica que será
modelagem 4 pelo nó A Few Good Men. Essa alteração apresentada a seguir. Dado um relacionamento R do tipo
se deve ao fato do filme Cloud Atlas possuir vários papéis muitos-para-muitos (n : m) entre 2 entidades E1 e E2 , se
representados pelos mesmos atores. Esse nó do tipo Filme um atributo P associado ao relacionamento R é relevante
também acaba sendo o de maior autoridade no grafo da para a análise, então P deve ser modelado como um nó do
modelagem 5; ou seja, vários outros nós apontam para esse grafo.
Filme. Ligado aos nós que representam as entidades E1 e E2
Outro nó que não estava presente no ranking de por meio de duas arestas R e R . Ou mais formalmente,
Intermediação para as modelagens 3 e 4 é o que representa como se segue.
o ator Hugo Weaving. Esse ator possui vários papéis em Sejam:
Cloud Atlas e está ligado a outros filmes no grafo. Portanto,
o nó Hugo Weaving possui maior probabilidade de estar no • G = (V, A); grafo
caminho mı́nimo entre pares de nós, e por isso apresenta • EC = (E, R, P e, P r); esquema conceitual
maior valor de intermediação na modelagem 5. • E = {E1 , E2 , ...}; conjunto de entidades do es-
De forma geral, entende-se que os nós com maior valor quema EC
de intermediação influenciam o valor dos nós ao redor. • R = {R1 , R2 , ...}; conjunto de relacionamentos do
Assim, pode-se concluir que, o fato de considerar um rela- esquema EC
cionamento como nó no grafo não chega a ter um impacto • Ei = {e1i , e2i , ...}; conjunto de instâncias da entidade
tão grande, como verificado contrastando os resultados das Ei
modelagens 3 e 4. • Rk = {rk1 , rk2 , ...}; conjunto de instâncias do relaci-
No entanto, ao representar o atributo multivalorado do onamento Rk
relacionamento entre duas entidades como um nó, isso faz • rkz = (exi , eyj ); uma instância de Rk conecta um par
com que as entidades envolvidas ganhem maior centralidade, de instâncias de entidades de E
em termos de intermediação e autoridade. Isso quer dizer, • P e = {P e1 , P e2 , ...}; conjunto de propriedades
que se um nó já apresentasse um valor de centralidade (atributos) de Entidades do esquema EC
significativo na modelagem 4, há um potencial aumento • P r = {P r1 , P r2 , ...}; conjunto de propriedades
deste valor na modelagem 5, aumentando sua posição no (atributos) de Relacionamentos do esquema EC

Authorized licensed use limited to: Universidad Federal de Pernambuco. Downloaded on December 09,2024 at [Link] UTC from IEEE Xplore. Restrictions apply.
 • P rk = {P rk1 , P rk2 , ...}; conjunto de propriedades Assim, pode-se chegar nas mesmas conclusões:
(atributos) de um Rk do conjunto R do esquema (i) o fato de considerar um relacionamento como nó no
EC grafo não chega a ter um impacto tão grande, como verifi-
• prkw,z = (v1 , v2 , ...); conjunto de valores do atributo cado contrastando os resultados das modelagens 3 e 4;
P rkw de um relacionamento Rk , associado a uma (ii) se um nó já apresentasse um valor de centralidade
instância de relacionamento rkz significativo na modelagem 4, há um potencial aumento
deste valor na modelagem 5, aumentando sua posição no
Dado que: ranking.
• E1 , E2 ∈ E; ex1 ∈ E1 ; ey2 ∈ E2 ;
• R1 ∈ R ;
• r1z ∈ R1 ; r1z = (ex1 , ey2 ); 7. Conclusão
• P r11 ∈ P r1 ;
• pr11,z = (v1 , v2 , ..); Este trabalho abordou a tarefa de mapear dados relacio-
nais para a representação em grafos, propondo um conjunto
No mapeamento para o grafo G temos:
de heurı́sticas que visam auxiliar um usuário na tarefa de
• ∀ex1 ∈ E1 , ex1 ∈ V ; modelar o grafo. Em comparação com os trabalhos que
• ∀ey2 ∈ E2 , ey2 ∈ V ; abordam o mesmo problema, este trabalho difere por levar
• Se P r11 é importante para o relacionamento R1 e em consideração que um grafo pode seguir distintos modelos
P r11 é multivalorado então e modelagens. Além de levar em conta a análise topológica
∀r1z e ∀vs ∈ pr11,z : vs ∈ V e (ex1 , vs ), (vs , ey2 ) ∈ A do grafo como fator para escolha da modelagem. Destaca-se
que, mesmo com o conjunto de coeficientes de análise em
mãos, antes de aplicá-los, é necessário conhecer os esque-
6.3. Experimento TMDB
mas conceitual e relacional do banco de dados relacional
para melhor entender os dados e os resultados das medidas
Visando confirmar os resultados obtidos na seção 6.2, fo-
topológicas, para então alcançar uma boa modelagem do
ram realizados novos experimentos utilizando um conjunto
grafo.
de dados maior, e o mesmo tipo de análises apresentadas
anteriormente. O conjunto de dados utilizado nessa fase é Além das heurı́sticas abstraı́das, os experimentos per-
uma base que contém dados sobre filmes e atores chamado mitiram compreender como as métricas da teoria de grafos
TMDB4 . Da base original do TMDB, foi extraı́do um sub- possuem interpretações diferentes. As interpretações estão
conjunto de dados usando o filtro gênero, “Crime” neste relacionadas com a influência dos vértices no grafo. Em
caso, e utilizando unicamente as informações sobre filmes e alguns momentos, as informações sobre as ligações e in-
atores. Os experimentos dessa etapa reproduzem as mesmas fluências, extrapolavam a vizinhança de vértices, exigindo
três modelagens do experimento SMDB. Para garantir o uma visão mais abrangente dos resultados das análises.
cálculo das medidas de centralidade, foi considerado o maior São reportados experimentos iniciais que gradativamente
componente conexo do grafo obtido para cada modelagem. se tornavam mais complexos e permitiram identificar um
O grafo gerado a partir da modelagem 3 possui 4486 nós conjunto de heurı́sticas. Esses experimentos foram realiza-
e 5046 arestas. O grafo para a modelagem 4, 9532 nós dos para análises topológicas, usando diferentes métricas em
e 10092 arestas. E o grafo da modelagem 5, 9561 nós e três conjuntos de dados: Zachary e SMDB, como conjuntos
10150 arestas. O objetivo desse experimento foi conferir menores (toy examples), e TMDB, como conjunto de maior
se os comportamentos notados nos experimentos anteriores porte. No entanto, experimentos adicionais são necessários
se repetiriam em um conjunto de dados maior. O fato do para validar e estender tais heurı́sticas. O uso de conjuntos
conjunto utilizado nesse experimento ser do mesmo domı́nio de dados de diferentes domı́nios, de um conjunto maior
que no experimento SMDB, faz com que a expectativa de de coeficientes analı́ticos e o uso de outros construtos5 de
repetição do comportamento seja maior. Nesse experimento, modelagem (e.g. relacionamentos n-ários), são planejados
as heurı́sticas até aqui obtidas não foram aplicadas, mas era para experimentos futuros.
esperado que o mesmo raciocı́nio para a geração dessas,
fosse aqui usado.
O comportamento das medidas de centralidade para o
Agradecimentos
novo conjunto de dados nas três modelagens foi seme-
lhante ao observado no experimento SMDB. Em particular, Este trabalho contou com o apoio parcial das agências
observa-se que as primeiras posições do ranking obtido em de fomento CAPES-Demanda Social e CNPq (Processo Nro.
cada uma das três modelagens foi parecido ao obtido nos 307.647/2012-9).
experimentos da seção 5.2.
As Tabelas 5, 6 e 7 mostram os 10 primeiros colocados
4. [Link]
no ranking obtido para cada uma das três modelagem usa- 5. Pode-se definir construtos como elementos de um modelo (e.g. en-
das, considerando as medidas de centralidade proximidade, tidades e relacionamentos são construtos do modelo ER), que podem ser
intermediação, hub e autoridade. replicados em diferentes esquemas. [13]

Authorized licensed use limited to: Universidad Federal de Pernambuco. Downloaded on December 09,2024 at [Link] UTC from IEEE Xplore. Restrictions apply.
 Modelagem 3
Não Direcionado Direcionado
Proximidade Intermediação Autoridade Hub
Dogville Dogville Angels & Demons Angels & Demons
Ben Gazzara Bloodline Dogville Dogville
Bloodline Gert Fröbe Armin Mueller-Stahl Armin Mueller-Stahl
At Close Range Ben Gazzara Stellan Skarsgård Stellan Skarsgård
The Big Sleep Ten Little Indians Dancer in the Dark Dancer in the Dark
Lauren Bacall The Big Sleep Carmen Argenziano Carmen Argenziano
Candy Clark Humphrey Bogart Tom Hanks Tom Hanks
Patricia Clarkson Vera Brühne Elya Baskin Elya Baskin
The Pledge At Close Range Ewan McGregor Ewan McGregor
Nicole Kidman Fritz Wepper Thure Lindhardt Thure Lindhardt
Tabela 5. R ANKING DAS MEDIDAS DE CENTRALIDADE PARA A M ODELAGEM 3 NO EXPERIMENTO TMDB

Modelagem 4
Não Direcionado Direcionado
Proximidade Intermediação Autoridade Hub
Dogville Dogville Straus Angels & Demons
Jack McKay Bloodline Richter Straus
Ma Ginger Gert Fröbe Silvano Ventivoglio Richter
Ben Gazzara Ben Gazzara Cardinal Silvano Ventivoglio
Vera Rhys Williams Robert Langdon Cardinal
Grace Margaret Mulligan Jack McKay Carlo Ventresca Robert Langdon
Rhys Williams Ten Little Indians Chartrand Carlo Ventresca
Chuck The Big Sleep Mr. Gray Chartrand
Bloodline Humphrey Bogart Father Simeon Mr. Gray
Tom Edison Senior Inspector Max Hornung Swissguard Father Simeon
Tabela 6. R ANKING DAS MEDIDAS DE CENTRALIDADE PARA A M ODELAGEM 4 NO EXPERIMENTO TMDB

Modelagem 5
Não Direcionado Direcionado
Proximidade Intermediação Autoridade Hub
Dogville Dogville Angels & Demons Angels & Demons
Jack McKay Bloodline Straus Straus
Ma Ginger Gert Fröbe Richter Richter
Ben Gazzara Ben Gazzara Silvano Ventivoglio Silvano Ventivoglio
Vera Rhys Williams Cardinal Cardinal
Grace Margaret Mulligan Jack McKay Robert Langdon Robert Langdon
Rhys Williams Ten Little Indians Carlo Ventresca Carlo Ventresca
Chuck The Big Sleep Chartrand Chartrand
Bloodline Humphrey Bogart Mr. Gray Mr. Gray
Tom Edison Senior Inspector Max Hornung Father Simeon Father Simeon
Tabela 7. R ANKING DAS MEDIDAS DE CENTRALIDADE PARA A M ODELAGEM 5 NO EXPERIMENTO TMDB

Referências [8] E. F. Codd, “A relational model of data for large shared data banks,”
Commun. ACM, pp. 377–387, 1970.
[1] C. Bizer, “The d2rq mapping language,” 2016, 14 nov. de 2016. [9] M. A. Rodriguez and P. Neubauer, “Constructions from dots and
[Online]. Available: [Link] lines,” Bulletin of the American Society for Information Science and
[2] R. D. Virgilio, A. Maccioni, and R. Torlone, Model-Driven Design of Technology, vol. 36, no. 6, pp. 35–41, 2010.
Graph Databases. Cham: Springer International Publishing, 2014, [10] R. D. Virgilio, A. Maccioni, and R. Torlone, “Converting relational
pp. 172–185. to graph databases,” in First International Workshop on Graph Data
[3] D. Wardani and J. Küng, “Semantic mapping relational to graph Management Experiences and Systems, ser. GRADES ’13, no. 1.
model,” in Computer, Control, Informatics and Its Applications New York, NY, USA: ACM, 2013, p. 6.
(IC3INA), International Conference on, Oct 2014, pp. 160–165. [11] K. Xirogiannopoulos, U. Khurana, and A. Deshpande, “Graphgen:
[4] S. Bordoloi and B. Kalita, “Article: Designing graph database models Exploring interesting graphs in relational data,” PVLDB, vol. 8,
from existing relational databases,” Int. J. of Computer Applications, no. 12, pp. 2032–2035, 2015.
vol. 74, no. 1, pp. 25–31, July 2013. [12] W. W. Zachary, “An information flow model for conflict and fission
[5] M. Newman, Networks: An Introduction. New York, NY, USA: in small groups,” Journal of Anthropological Research, vol. 33, no. 4,
Oxford University Press, Inc., 2010. pp. 452–473, 1977.
[6] C. A. Heuser, Projeto de banco de dados. Sagra Luzzatto, 2001. [13] Y. Wand, V. C. Storey, and R. Weber, “An ontological analysis of the
[7] P. P.-S. Chen, “The entity-relationship model—toward a unified view relationship construct in conceptual modeling,” ACM Trans. Database
of data,” ACM Trans. Database Syst., vol. 1, no. 1, pp. 9–36, Mar. Syst., vol. 24, no. 4, pp. 494–528, 1999.
1976.

Authorized licensed use limited to: Universidad Federal de Pernambuco. Downloaded on December 09,2024 at [Link] UTC from IEEE Xplore. Restrictions apply.