Bienvenidos al vídeo dedicado a "Graph processing". Durante esta sesión vamos a realizar un repaso, un breve estudio de todo lo relacionado con el procesamiento de bases de datos orientadas a grafos, para las cuales ya hicimos una breve introducción hace un par de semanas. Como veis, haremos un repaso sobre la estructura y la tipología de los datos en los grafos, qué tipo de consultas haremos, las etapas, los componentes y las características principales de estos. Recordando lo que dijimos hace un par de semanas, las bases de datos orientadas a grafos representan entidades individuales y sus relaciones. Las entidades de un grafo se conocen como nodos o vértices, y las relaciones entre entidades dentro de un grafo se conocen como arcos o conexiones. Tanto los nodos como los arcos presentan sus propias propiedades y, en general, el punto de vista que debemos tener a la hora de tratar con bases de datos orientadas a grafos, es que nuestras consultas han de estar orientadas a procesar la información de nodos que están interrelacionados entre sí, extrayendo todos los datos que podamos obtener a partir de sus relaciones, y normalmente partiendo de un nodo o subconjunto de nodos, y explorando las conexiones o arcos que tiene. Dicho de otra manera, las bases de datos orientadas a grafos elevan el protagonismo de las relaciones por encima de las propias entidades. Los grafos, en este caso, tradicionalmente se representan de tres maneras muy concretas. En primer lugar, tenemos lo que sería las listas de adyacencia donde cada vértice de un grafo corresponde con una lista del resto de vértices adyacentes a él, es decir, los vértices que tienen conexiones directas con este nodo. De este modo, vemos en este ejemplo que tenemos un grafo completamente conectado, donde "A" conecta con "B" y "C", "B" conecta con "A" y "C", y "C" conecta con "A" y "B". Otra manera de representar los grafos es con la denominada matriz de adyacencia donde vemos, como en este caso, que tanto las filas como las columnas corresponden al mismo conjunto de vértices que componen el grafo, de manera que cada celda "I J", denota la conexión o la relación del nodo "I" con el nodo "J". Si no existe conexión, esta celda estará vacía y si existe conexión, esta celda, o bien contendrá un valor binario verdadero, o bien, incluso puede contener las propiedades que tiene esa conexión, ese arco dentro del grafo, como podemos ver en este bonito y colorido ejemplo que tenemos. La tercera manera de representar los grafos es mediante la denominada matriz de incidencia donde, en esta ocasión, las filas representan cada uno de los nodos del grafo, pero las columnas, ahora, representan las conexiones de manera que, generalmente, esta matriz es binaria y donde un valor de cero o falso indicará que ese determinado nodo no tiene esa determinada conexión con ningún otro nodo, y un valor verdadero, lo contrario, que ese nodo contiene, o es origen, o destino de esa conexión. A lo largo del curso es evidente y sois plenamente conscientes de que en la actualidad los datos son importantísimos, todos los datos, generados, toda la gran cantidad de datos que se generan son valiosísimos y, desde luego, es muy importante y necesario saber extraer eficientemente la información de ellos. Los grafos nos permiten la posibilidad de recorrer estos datos de una manera muy provechosa en determinados problemas, para atender a determinadas necesidades. Entonces, hay que saber bien qué preguntar y cómo preguntar, para explorar eficazmente las relaciones existentes e, incluso, descubrir nuevas relaciones entre entidades. Pongamos, por ejemplo, un caso basado en el fútbol. Estoy seguro de que muchos de los estudiantes argentinos estarán muy contentos al escuchar que es evidente que Maradona es uno de los grandes iconos de la historia de este deporte. En este caso podemos tener una entidad, que es jugador de fútbol, con una propiedad, que es su nombre y que correspondería a Maradona. También tenemos otras propiedades como su fecha de nacimiento, su pierna dominante, etcétera. Esta entidad, podemos observar que se relaciona con otro tipo de entidades, en este caso tenemos la entidad equipo de fútbol, también con su propiedad nombre y con el año de fundación o creación. En este caso vemos que Maradona ha jugado, entre otros, jugó en el Nápoles, ha jugado en el Fútbol Club Barcelona y también ha jugado en la selección nacional de Argentina. Como vemos, las relaciones tienen sus propias propiedades, en este caso hemos definido dos campos que es el año de su debut en cada uno de estos equipos y el año de su último partido. A Maradona, normalmente, se le relaciona con Leo Messi. Aparte de por muchos motivos subjetivos, ¿qué relaciones objetivas podemos encontrar entre Diego Armando Maradona y Lionel Messi? Una que está muy clara es que Leo Messi ha jugado en dos equipos en los que ha jugado también Maradona, como son la selección Argentina y el Fútbol Club Barcelona. También hay otros jugadores que han jugado en la selección Argentina como, por ejemplo, el Kun Agüero, en este caso, no obstante, tan sólo ha compartido un equipo con Diego Armando Maradona, por lo tanto, podríamos entender que la relación entre Maradona y Messi es más fuerte que la que puede tener con el Kun Agüero. Además, sabemos que estos jugadores tienen una relación muy especial con el gol, de manera que Maradona marcó muchísimos goles con sus equipos de la misma manera que los marcó Messi. Maradona, además, marcó un famosísimo gol con la mano y, de hecho, Messi también marcó otro gol con la mano, aunque éste con menos trascendencia. Por lo tanto, aquí podemos ver que la relación incluso se hace más fuerte. Claro, en este caso estaríamos hablando de una relación a nivel profesional, es decir, ahora estaríamos indagando y explorando y, quizás, concluyendo que la relación entre Maradona y Messi es más fuerte. Pero resulta que tenemos una entidad persona, con un campo, nombre, que corresponde a Benjamín Agüero. Esta entidad resulta que se relaciona con el Kun Agüero de manera que el Kun Agüero es el padre de Benjamín y, a su vez, Benjamín es el nieto de Diego Armando Maradona. Por lo tanto, aquí ya podemos empezar a ver que la relación, dependiendo del plano en el que nos movamos, es más fuerte en un sentido o en otro. Además, el Kun Agüero también es un jugador que ha marcado muchísimos goles y, de hecho, también ha marcado goles con la mano, o sea que podríamos inferir en este caso que quizás la relación con el Kun Agüero, dependiendo de las preguntas que nos hagamos y cómo recorramos el grafo, es más fuerte en este caso con Maradona. Este es un ejemplo simpático para poder mostrar el tipo de preguntas que nos podemos hacer. Por ejemplo, nos podemos hacer con una estructura de base de datos orientada a grafos, nos podemos hacer preguntas simples como, ¿cuántos equipos tienen en común Messi y Maradona?, lo cual nos puede dar una cierta métrica de la relación entre estas entidades a nivel profesional. De manera análoga, nos podríamos preguntar cuántas personas en común tienen Agüero y Maradona, en este caso, la relación sería más de ámbito personal. Pero también, nos podemos hacer preguntas y explorar la información de manera más compleja, de manera que podríamos llegar a preguntas tipo, ¿qué selección ha tenido más jugadores profesionales que han marcado goles con la mano?, qué sería bastante peculiar. Supongo que, en este caso, no sé si los estudiantes argentinos estarían orgullosos o no de este dato. Dejando aparte las bromas, vemos que la forma de recorrer los grafos nos permite descubrir aspectos de nuestros datos muy importantes y de manera muy diferente. Por ejemplo, en este caso vemos que aparte de encontrar distintas agrupaciones, lo cual de por sí ya es muy importante, vemos que además podemos identificar ciertos puntos donde la información ha de pasar obligatoriamente para fluir entre una agrupación y otra. Es decir, a de pasar sí o sí y actúan como lo que se denominan "vértices puente". Esto, como os podéis imaginar, es algo importantísimo dependiendo del negocio, dado que, imaginaos que este grafo corresponde a nuestra red de clientes, es evidente que estos vértices puente son importantísimos para mantener los distintos conjuntos de clientes. Como este tipo de algoritmos o de descubrimientos que podemos realizar, hay muchos algoritmos tradicionales basados en bases de datos orientadas a grafos. Tenemos algoritmos de particionamiento, como acabamos de ver, para identificar distintas porciones de los grafos. Tenemos, como ya comentamos anteriormente, los algoritmos de análisis del camino más corto. Esto, evidentemente, es importantísimo para cualquier aspecto logístico o cualquier empresa dedicada a logística o transporte. Tenemos algoritmos de componentes conectados, tienen muchísimas aplicaciones, como cualquiera que haya estudiado teoría de grafos puede conocer, y tenemos algoritmos como Page Rank y Centrality que caracterizan la importancia de un vértice dentro del gráfico en función de distintas métricas o distintos valores que queramos evaluar. En el siguiente vídeo, nos dedicaremos a explorar un poco más en profundidad las etapas y componentes propias del "Graph processing", del procesamiento de grafos, hablaremos de las características que diferencian este tipo de paradigma y repasaremos, mencionaremos, algunas de las herramientas que lo implementan.
