Aprende cómo podemos usar los CID para crear estructuras de datos direccionables por contenido para la web distribuida
Last updated
Antes de que podamos crear estructuras de datos direccionables por contenido, tenemos que definir esas estructuras de una manera que nos permita hablar de ellas de forma precisa y sin ambigüedades. Para este propósito, recurrimos a los gráficos.
Un gráfico es una abstracción matemática que se utiliza para representar relaciones entre una colección de objetos. Es común usar el término nodo para referirse a un objeto en un gráfico, y el término arista para referirse a una relación entre objetos. Más comúnmente, los gráficos se utilizan para representar relaciones por pares entre objetos. Por ejemplo, un gráfico podría usarse para mapear las carreteras que conectan pares de ciudades, o las amistades entre estudiantes en una escuela.
La jerarquía de archivos que introdujimos en la lección anterior también forma un gráfico (los directorios y archivos actúan como nuestros nodos, y la relación entre un directorio y los archivos que contiene nos da nuestras aristas). Lo hemos representado de nuevo en la figura a continuación:
Dado un gráfico, podemos imaginar comenzar en un nodo y moverse a lo largo de sus aristas para llegar a otro nodo. Por ejemplo, podríamos comenzar en el directorio raíz, "pics", en la figura anterior, y moverse progresivamente más profundamente en la jerarquía para alcanzar un archivo deseado.
Un gráfico se llama dirigido si cada arista tiene algún sentido de dirección. En la figura anterior, por ejemplo, las aristas representan contención: un directorio contiene un archivo, pero un archivo no contiene a su directorio. Las relaciones entre nodos solo se asocian correctamente en una dirección, y esta dirección está indicada por una flecha de una sola cabeza. Términos genealógicos como antecesor, descendiente, padre e hijo se usan frecuentemente para referirse a los nodos en un gráfico dirigido. Por ejemplo, en nuestra figura, se diría que el nodo correspondiente al directorio "cats" es padre de los dos nodos de archivo que contiene.
Los nodos que no tienen padres se llaman frecuentemente nodos raíz, mientras que aquellos sin hijos se llaman nodos hoja. Los nodos con padres e hijos se llaman nodos intermedios, ya que se encuentran entre las raíces y las hojas del gráfico. También es común usar el término no hoja para referirse tanto a los nodos intermedios como a los nodos raíz.
Un gráfico se llama acíclico si no hay bucles en el gráfico, es decir, dado cualquier nodo en el gráfico, no hay manera de navegar desde ese nodo de regreso a sí mismo a lo largo de las aristas del gráfico. En un gráfico dirigido como nuestra jerarquía de archivos, solo podemos movernos de nodos padres a nodos hijos.
Un gráfico que es tanto dirigido como acíclico se llama, apropiadamente, un gráfico acíclico dirigido. Resulta que estas son una estructura muy comúnmente estudiada—tan común, de hecho, que el acrónimo DAG se usa frecuentemente para referirse a ellos! Los datos jerárquicos, en particular, se representan muy naturalmente a través de DAGs.
