Relaciones

Introducción.

Una relación es una correspondencia entre dos elementos de dos conjuntos con ciertas propiedades. En computación las relaciones se utilizan en bases de datos, estructuras de datos, redes, autómatas y lenguajes. Por ejemplo, se pueden guardar datos personales de un trabajador, numero, de control, registro federal de causantes, puesto ocupado, antigüedad y salario, entre otros. Para relacionar los datos de este archivo con otra información, se establece el campo relación y las reglas que permitirán la búsqueda y asignación de información. Una vez que se establece la relación, es posible llevar a cabo varias operaciones entre relaciones utilizando para ello a. álgebra relaciona. Las estructuras de datos son relaciones que permite acceder de manera más rápida y ordenada la información; por lo general la relación la establece el orden en que se deseen recorrer los datos (orden alfabético, antigüedad, salario, etc.) usando como elemento físico de relación entre los nodos los apuntadores.

Las funciones son una clase especial de relación y se utilizan prácticamente en todas las áreas de las matemáticas, en particular en cálculo diferencial e integral, geometría analítica, trigonometría y álgebra. En computación las funciones tienen aplicación directa en lenguajes de programación, ya que cada uno de estos tiene sus propias librerías de funciones estándar permitiendo al usuario adicionar más funciones con el objeto de hacerlos más ricos, fáciles y poderosos en el momento de programar.

Definición de Relación.

El concepto de relación surge de manera natural en el análisis de un sistema. Un ejemplo, en los números Naturales se establece la relación “… es menor que...”. Bajo esta relación R el número 2 se relaciona con el 3, 2 es menor que 3, pero no así al contrario (3 no es menor que 2). 

Una relación es un conjunto de pares ordenados. Un par ordenado (también llamada pareja ordenada) consta de dos elementos: (a, b) en donde el orden en que aparece (primero a, después b) indica la relación: a Rb de a con b. 

Una relación R se forma al unir elementos de diferentes conjuntos que cumplen con cierta propiedad o característica. Los elementos que se unen pueden ser de dos, tres o más conjuntos.

Ejemplos:

 Se tienen los conjuntos A, B y C, además de que elementos del conjunto A están relacionados con elementos del conjunto B y elementos del conjunto C porque cumplen con ciertas propiedades, de forma que se puede tener una relación R integrada por tripletas.

Los conjuntos son:

A = {1,2, 3, 4, 5, 6,7}

B = {a, e, m, p, u}

C = {verde, azul, café, amarillo}

Considérese que R está formada por tripletas que contienen un elemento de A que es divisible entre 3, uno de B que es una letra vocal y uno de C que es un color básico:

R =      {(3, a, azul), (3, a, amarillo), (3, e, azul), (3, e, amarillo), (3, u, azul), (3, u, amarillo)

(6, a, azul), (6, a, amarillo), (6, e, azul), (6, e, amarillo), (6, u, azul), (6, u, amarillo)

Esta relación es una relación trinaría porque está conformada por elementos de tres conjuntos distintos.

Las relaciones más comunes en ciencias de la computación son las relaciones binarias, que están integradas por pares de elementos de dos conjuntos.

Sean A y B dos conjuntos no vacíos. Una relación binaria R es un conjunto de pares ordenados, en donde el primer elemento a esta relacionado con el segundo elemento b por medio de cierta propiedad o característica, el cual se indica como aRb mientras que para la relación se tiene que

R = {(a, b) | a € A y b € B}

• Producto cartesiano (A x B)

 Es la combinación de todos los elementos del conjunto A con todos los elementos del conjunto B.

• Dominio de R (Dom(R))

Conjunto de todos los primeros elementos de los pares encontrados en una relación.

• Codominio de R (Cod(R))

Está conformado por los segundos elementos de los pares de la relación R.

Matriz de una relación (MR)

Si A y B son dos conjuntos finitos y si R una relación de A en B, es posible representar a R como una matriz MR donde un elemento de la matriz es:

1 si (a, b) € R

0 si (a, b) € R

Grafo de una relación (GR)

Se puede representar una relación por medio de una gráfica integrada por nodos y flechas, y a dicha gráfica se le conoce como “grafo dirigido” de R, en donde los elementos de los conjuntos A y B se representan como nodos y la relación que existe entre dichos elementos se indica por medio de una flecha que va del elemento del conjunto A al elemento del conjunto B con el que está relacionado.

·         Grafos dirigidos y no dirigidos.

En un grafo dirigido se representa la relación entre un elemento del conjunto A y un elemento del conjunto B por medio de una flecha que va de a hacia b. Sin embargo, en un grafo no dirigido de la relación es en ambos sentidos, esto significa que aRb y que bRa, por esa razón la relación se representa por una sola línea sin cabeza de flecha.

Tipos de Relaciones:

Las relaciones y funciones deben cumplir con ciertos requisitos para que sean consideradas como tales y como cada una de ellas tiene sus características propias es posible establecer cierta clasificación. En la siguiente clasificación de relaciones se considera que los conjuntos A y B son iguales, lo que implica que su representación matricial siempre es cuadrada.

-Propiedades de las relaciones. 

En una relación es común que los elementos de A también sean elementos de B, es decir que A = B. Por ejemplo, en una red de computadoras A y B tienen los mismos elementos porque relacionan computadoras, en una red carretera A y B tienen los mismos elementos porque relacionan ciudades, o en una red de agua potable A y B tienen los mismos elementos porque relacionan válvulas. Cuando ocurre que A = B, las relaciones pueden tener una, varias o ninguna de las siguientes propiedades:

Propiedad	Condición
Reflexiva	aRa; V a € A. Esto es: Todos los elementos de A están relacionados consigo mismo
Irreflexiva	(a, a) € R V a € A. Esto es: ningún elemento de A está relacionado con él mismo.
Simétrica	Cuando (a, b) € R entonces (b, a) € R, o bien cuando (a, b) € R entonces (b, a) € R. Esto es: los elementos simétricos de la relación son iguales
Asimétrica	Cuando (a, b) € R entonces (b, a) € R, además si a=b entonces (a, a) € R. Esto es, en ningún caso los dos pares simétricos están en la relación.
Anti simétrica	(a, b) € R o bien (b, a) € R. Esto es: cuando a ≠ b en ningún caso los dos pares simétricos están en la relación
Transitiva	Si (a, b) € R y (b, c) € R, entonces (a, c) € R. Esto es cuando aRb y bRc entonces aRc.

Relación de equivalencia.

Es aquella que es reflexiva, simétrica; transitiva. Si la relación es la comunicación en una red de computadoras, dicha red debe ser una relación de equivalencia, porque toda computadora se puede comunicar con ella misma (reflexiva), si la computadora X se puede comunicar con la computadora W entonces la computadora W se puede comunicar con la X (simétrica). Si la computadora X se puede comunicar con la W y la computadora W se puede comunicar con la Z entonces la computadora X se puede comunicar con la computadora Z (transitiva).

·         Clases de equivalencia [a]. 

Son conjuntos que contienen a todos los elementos b € B que están relacionados con a  € A.

[a] = {b | b€ B, aRb}

·         Partición ( ﭏ)

 Es un conjunto de clases de equivalencia con las siguientes propiedades:

a) Deberán estar contenidos todos los elementos del conjunto A.

b) La intersección entre las clases de equivalencia debe ser vacía. 

 ﭏ = {[a] | a €  A; la  intersección entre clases de equivalencia es vacía }

·         Cerraduras. 

No todas las relaciones son de equivalencia, pero es posible hacer que tengan esta propiedad agregando los pares ordenados necesarios mínimos usando para ello las cerraduras: 

Reflexiva (R ᴗ I), simétrica (R ᴗ R-1) y transitiva (R ᴗ R2).

·         Operación entre relaciones.

De la misma manera como se realizan operaciones entre conjuntos, también se pueden llevar a cabo las siguientes operaciones entre relaciones:

a) Complemento de R (R'). Son a todos los pares ordenados que están en el producto cartesiano A x B pero que no están en R.

b) Intersección de R y S (RᴒS). Sean R y S relaciones de un conjunto A en B, entonces se puede formar R ᴒ S. En términos de relación se puede ver que si a(RᴒS) b, entonces aRb y aSb. Por medio de matrices MRᴒS es el resultado de multiplicar elemento por elemento las matrices booleanas de R y S.

c) Unión de R y S (RᴗS). La unión de dos relaciones (R ᴗ S) significa que aRb o bien aSb. Por medio de matrices se lleva a cabo una suma de matrices booleanas entre MR y Ms para obtener MRᴗS.

d) Inversa de R (R -1). La inversa de R se encuentra intercambiando la posición de a y b, esto implica que si (a, b) € R entonces (b, a) € R. En el caso de matrices la inversa se encuentra intercambiando filas por columnas (MR-1).

            e) Composición de R y S (R ° S). La composición de relaciones R y S equivale a la propiedad transitiva, esto significa que si (a, b) € R y (b, c) € S, entonces (a, c) € (R ° S). Es posible también encontrar la composición de dos relaciones por medio de una multiplicación booleana de las matrices de las relaciones

(R ° S = MR°S = MR ٠MS ).

·         Una función f. 

Asigna a cada elemento x de un conjunto A un único elemento b de un conjunto B. Sean A y B conjuntos no vacíos. Una función f de A en B se escribe f: A → B.

 Se puede decir que todas las funciones son relaciones, pero no todas las relaciones son funciones. Para que una relación sea considerada como una función, deberá cumplir con las siguientes condiciones:

a) Dom(f) = A, esto es, el conjunto de los primeros elementos de todos los pares ordenados de la relación es el dominio de la función y también es igual al conjunto A.

b) Los elementos del dominio solamente deberán estar relacionados con un elemento del codominio.

·         Función inyectiva (o uno a uno).

Una función f: A → B se llama inyectiva. Si a cada elemento distinto del conjunto A corresponde un elemento distinto del conjunto B.

·         Función suprayectiva (o sobre).

Una función f: A → B se llama suprayectiva, si el conjunto de los segundos elementos de los pares ordenados de la función es igual al conjunto B.

·         Función biyectiva (o correspondencia uno a uno). 

Cuando una función es inyectiva y suprayectiva a la vez, se dice que es biyectiva.

·         Función invertible.

 Una función f: A → B es invertible si su relación inversa f-1 es también una función. Por otro lado, una relación es invertible si se trata de una función biyectiva.

Aplicación de las relaciones.

Las relaciones se pueden aplicar en bases de datos si un archivo se considera como una relación (o en otro texto, una base de datos). También se aplican en estructuras de datos ya que una relación es una lista enlazada, una pila y también un árbol. Otra aplicación es en teoría de grafos partiendo de que una relación también es un grafo. En programación también se aplican ya que una función es una relación con ciertas características.