DIAGRAMAS

Una entidad asociativa es un término usado en la teoría relacional y entidad-relación . Una base de datos relacional requiere la implementación de una relación base (o tabla base) para resolver relaciones de muchos a muchos . Una relación de base que representa este tipo de entidad se llama, informalmente, una tabla asociativa .

Una entidad asociativa (usando la notación de Chen )

Como se mencionó anteriormente, las entidades asociativas se implementan en una estructura de base de datos utilizando tablas asociativas, que son tablas que pueden contener referencias a columnas de la misma o diferentes tablas de base de datos dentro de la misma base de datos.

Una tabla asociativa (o unión) asigna dos o más tablas juntas haciendo referencia a las claves primarias de cada tabla de datos. En efecto, contiene una cantidad de claves externas, cada una en una relación de muchos a uno desde la tabla de unión a las tablas de datos individuales. La PK de la tabla asociativa se compone típicamente de las propias columnas FK.

Tablas asociativas se coloquialmente conocidos bajo muchos nombres, incluyendo tabla de asociación , tabla del puente , tabla de referencia cruzada , paso de peatones , tabla intermediario , tabla de intersección , tabla de unión , tabla de unión , tabla de enlace , que une mesa , muchos-a-muchos de resolución , tabla de mapa , tabla de asignación , tabla de emparejamiento , tabla dinámica (como se usa incorrectamente en laravel - que no debe confundirse con el uso correcto de tabla dinámica en hojas de cálculo), o tabla de transición .

Usando tablas asociativas [ editar ]

Un ejemplo del uso práctico de una tabla asociativa sería asignar permisos a los usuarios. Puede haber varios usuarios, y cada usuario puede tener asignados cero o más permisos. Se pueden otorgar permisos individuales a uno o más usuarios.

CREAR  TABLA  Usuarios  ( 
    UserLogin  varchar ( 50 )  CLAVE PRIMARIA  , UserPassword varchar ( 50 ) NOT NULL , UserName varchar ( 50 ) NOT NULL );
       
       


CREAR  TABLA  Permisos  ( 
    PermissionKey  varchar ( 50 )  CLAVE PRIMARIA  , PermissionDescription varchar ( 500 ) NOT NULL );
       


- Esta es la mesa de unión. 
CREAR  TABLA  UserPermissions  ( 
    UserLogin  varchar ( 50 )  REFERENCES  Usuarios  ( UserLogin ), 
    PermissionKey  varchar ( 50 )  REFERENCES  Permissions  ( PermissionKey ), 
    PRIMARY  KEY  ( UserLogin ,  PermissionKey ) 
);

Una declaración SELECT en una tabla de unión generalmente implica unir la tabla principal con la tabla de unión:

SELECT  *  FROM  Users 
JOIN  UserPermissions  USING  ( UserLogin );

Esto devolverá una lista de todos los usuarios y sus permisos.

Insertar en una tabla de unión implica varios pasos: primero inserte en la (s) tabla (s) principal (es), luego actualice la tabla de unión.

- Creación de un nuevo usuario 
INSERT  INTO  Users  ( UserLogin ,  UserPassword ,  UserName ) 
VALUES  ( 'SomeUser' ,  'SecretPassword' ,  'UserName' );

- Creación de un nuevo permiso 
INSERT  INTO  Permisos  ( PermissionKey ,  PermissionDescription ) 
VALUES  ( 'TheKey' ,  'Una clave utilizada para varios permisos' );

- Finalmente, actualizando la unión 
INSERT  INTO  UserPermissions  ( UserLogin ,  PermissionKey ) 
VALUES  ( 'SomeUser' ,  'TheKey' );

Usando claves externas, la base de datos eliminará automáticamente los valores de la tabla UserPermissions a sus propias tablas.

Un diagrama de base muestra o describe los "pines" de un componente electrónico . Esta parte generalmente tiene más de dos pines, por lo que se necesita un diagrama de base para mostrar qué pin hace qué. Muchos diagramas de base también muestran dimensiones .

diagrama de decisión binario ( BDD ) o un programa de derivación es una estructura de datos que se utiliza para representar una función booleana . En un nivel más abstracto, las BDD se pueden considerar como una representación comprimida de conjuntos o relaciones . A diferencia de otras representaciones comprimidas, las operaciones se realizan directamente en la representación comprimida, es decir, sin descompresión. Otras estructuras de datos utilizadas para representar funciones booleanas incluyen la forma normal de negación (NNF), los polinomios de Zhegalkin yGráficos acíclicos proposicionales dirigidos(PDAG).

Definición [ editar ]

Una función booleana se puede representar como un gráfico acíclico, enraizado , que consta de varios nodos de decisión y nodos terminales. Hay dos tipos de nodos terminales llamados 0-terminal y 1-terminal. Cada nodo de decisión$${\ displaystyle N} está etiquetado por variable booleana $${\ displaystyle V_ {N}}y tiene dos nodos hijos llamados niño bajo y niño alto. El borde del nodo$${\ displaystyle V_ {N}} a un niño bajo (o alto) representa una asignación de $${\ displaystyle V_ {N}}a 0 (respectivamente 1). Dicha BDDse llama "ordenada" si aparecen diferentes variables en el mismo orden en todas las rutas desde la raíz. Se dice que un BDD se 'reduce' si las siguientes dos reglas se han aplicado a su gráfica:

• Fusionar cualquier subgrafo isomorfo .
• Elimina cualquier nodo cuyos dos hijos sean isomorfos.

En el uso popular, el término BDD casi siempre se refiere al Diagrama de Decisión Binario Ordenado Reducido ( ROBDD en la literatura, utilizado cuando se deben enfatizar los aspectos de ordenación y reducción). La ventaja de un ROBDD es que es canónico (único) para una función particular y un orden variable. ^[1] Esta propiedad lo hace útil en la comprobación de equivalencia funcional y otras operaciones como el mapeo de tecnología funcional.

Una ruta desde el nodo raíz al terminal 1 representa una asignación de variable (posiblemente parcial) para la cual la función booleana representada es verdadera. A medida que la ruta desciende a un hijo bajo (o alto) desde un nodo, la variable de ese nodo se asigna a 0 (respectivamente 1).

Ejemplo [ editar ]

La figura de la izquierda a continuación muestra un árbol de decisión binario (las reglas de reducción no se aplican) y una tabla de verdad , cada una representa la función f (x1, x2, x3). En el árbol de la izquierda, el valor de la función se puede determinar para una asignación de variable dada siguiendo una ruta que baja del gráfico a un terminal. En las figuras a continuación, las líneas de puntos representan los bordes de un niño bajo, mientras que las líneas continuas representan los bordes de un niño alto. Por lo tanto, para encontrar (x1 = 0, x2 = 1, x3 = 1), comience en x1, cruce la línea de puntos hasta x2 (ya que x1 tiene una asignación a 0), luego baje dos líneas continuas (ya que x2 y x3 cada una tener una asignacion a uno). Esto conduce al terminal 1, que es el valor de f (x1 = 0, x2 = 1, x3 = 1).

El árbol de decisión binario de la figura de la izquierda se puede transformar en un diagrama de decisión binario al reducirlo al máximo de acuerdo con las dos reglas de reducción. El BDD resultante se muestra en la figura de la derecha.

Árbol de decisión binario y tabla de verdad para la función.$${\ displaystyle f (x_ {1}, x_ {2}, x_ {3}) = {\ bar {x}} _ {1} {\ bar {x}} _ {2} {\ bar {x}} _ {3} + x_ {1} x_ {2} + x_ {2} x_ {3}}

BDD para la función f

Historia [ editar ]

La idea básica a partir de la cual se creó la estructura de datos es la expansión de Shannon . Una función de conmutación se divide en dos subfunciones (cofactores) asignando una variable (véase la forma normal de if-then-else ). Si dicha subfunción se considera un subárbol, puede representarse mediante un árbol de decisión binario . Los diagramas de decisión binarios (BDD) fueron introducidos por Lee, ^[2] y posteriormente estudiados y dados a conocer por Akers ^[3] y Boute. ^[4]

Randal Bryant, de la Universidad Carnegie Mellon, investigó todo el potencial de los algoritmos eficientes basados ​​en la estructura de datos : sus extensiones clave fueron el uso de una ordenación variable fija (para representación canónica) y sub-gráficos compartidos (para compresión). La aplicación de estos dos conceptos da como resultado una estructura de datos y algoritmos eficientes para la representación de conjuntos y relaciones. ^[5] [6] Al extender la compartición a varios BDD, es decir, varios BDD utilizan un subgrafo, se define el Diagrama de Decisión Binario Compartido Reducido Ordenado . ^[7] La noción de un BDD ahora se usa generalmente para referirse a esa estructura de datos en particular.

En su video conferencia Fun With Binary Decision Diagrams (BDD) , ^[8] Donald Knuth llama a los BDD "una de las únicas estructuras de datos realmente fundamentales que surgieron en los últimos veinticinco años" y menciona que el artículo de Bryant de 1986 fue por algún tiempo Uno de los trabajos más citados en informática.

Adnan Darwiche y sus colaboradores han demostrado que los BDD son una de varias formas normales para las funciones booleanas, cada una inducida por una combinación diferente de requisitos. Otra forma normal importante identificada por Darwiche es la forma normal de negación descomponible o DNNF.

Aplicaciones [ editar ]

Los BDD se usan ampliamente en software CAD para sintetizar circuitos ( síntesis lógica ) y en verificación formal. Hay varias aplicaciones menos conocidas de BDD, que incluyen el análisis del árbol de fallas , el razonamiento bayesiano , la configuración del producto y la recuperación de información privada . ^{[9] [10] [ citación necesitada ]}

Cada BDD arbitrario (incluso si no está reducido o ordenado) puede implementarse directamente en el hardware reemplazando cada nodo con un multiplexor de 2 a 1 ; cada multiplexor puede ser implementado directamente por una 4-LUT en un FPGA . No es tan sencillo convertir de una red arbitraria de puertas lógicas a un BDD ^{[ cita requerida ]} (a diferencia del gráfico e inversor ).

Ordenamiento de variables [ editar ]

El tamaño de la BDD se determina tanto por la función que se representa como por el orden elegido de las variables. Existen funciones booleanas.$${\ displaystyle f (x_ {1}, \ ldots, x_ {n})}para lo cual, dependiendo del orden de las variables, obtendríamos un gráfico cuyo número de nodos sería lineal (en  n ) en el mejor de los casos y exponencial en el peor de los casos (por ejemplo, un sumador de acarreo de rizado ). Consideremos la función booleana.$${\ displaystyle f (x_ {1}, \ ldots, x_ {2n}) = x_ {1} x_ {2} + x_ {3} x_ {4} + \ cdots + x_ {2n-1} x_ {2n} .} Usando la ordenación de variables {\ displaystyle x_ {1} , el BDD necesita 2 ^n +1 nodos para representar la función. Usando el pedido{\ displaystyle x_ {1} , el BDD consta de 2 n  + 2 nodos.

BDD para la función ƒ ( x 1 , ..., x 8 ) = x 1 x 2 + x 3 x 4 + x 5 x 6 + x 7 x 8 usando orden de variable incorrecto

Buen orden variable

Es de crucial importancia preocuparse por el orden de las variables al aplicar esta estructura de datos en la práctica. El problema de encontrar la mejor orden de variables es NP-duro . ^[11] Para cualquier constante c  > 1, incluso NP-es difícil calcular una ordenación variable que resulta en un OBDD con un tamaño que es, como máximo, c veces más grande que el óptimo. ^[12] Sin embargo, existen heurísticas eficientes para abordar el problema. ^[13]

Existen funciones para las cuales el tamaño del gráfico es siempre exponencial, independientemente del orden de las variables. Esto es válido, por ejemplo, para la función de multiplicación. ^[1] De hecho, la función calcula el bit medio del producto de dos$${\ displaystyle n}Los números de bits no tienen un OBDD más pequeño que $${\ displaystyle 2 ^ {\ lfloor n / 2 \ rfloor} / 61-4}vértices. ^[14] (Si la función de multiplicación tuviera OBDD de tamaño polinomial, mostraría que la factorización de enteros está en P / poli , que no se sabe que sea verdadera. ^[15] )

Para los autómatas celulares con comportamiento simple, el BDD mínimo normalmente crece linealmente en pasos sucesivos. Para la regla 254, por ejemplo, es 8t + 2, mientras que para la regla 90 es 4t + 2. Para los autómatas celulares con un comportamiento más complejo, típicamente crece aproximadamente exponencialmente. Así, para la regla 30 es {7, 14, 29, 60, 129} y para la regla 110 {7, 15, 27, 52, 88}. El tamaño de la BDD mínima puede depender del orden en que se especifican las variables; así, por ejemplo, simplemente reflejando la regla 30 para dar los rendimientos de la regla 86 {6, 11, 20, 36, 63}.

Los investigadores han sugerido mejoras en la estructura de datos BDD que dan paso a una serie de gráficos relacionados, como BMD ( diagramas de momento binarios ), ZDD ( diagrama de decisión de supresión cero ), FDD ( diagramas de decisión binarios libres ), PDD ( diagramas de decisión de paridad ) , y MTBDDs (BDDs de múltiples terminales).

Operaciones lógicas en BDDs [ editar ]

Muchas operaciones lógicas en BDD se pueden implementar mediante algoritmos de manipulación de gráficos de tiempo polinómico: ^[16] : 20

• conjunción
• disyunción
• negación

Sin embargo, la repetición de estas operaciones varias veces, por ejemplo, formando la conjunción o disyunción de un conjunto de BDD, puede en el peor de los casos resultar en un BDD exponencialmente grande. Esto se debe a que cualquiera de las operaciones anteriores para dos BDD puede dar como resultado un BDD con un tamaño proporcional al producto de los tamaños de los BDD y, por lo tanto, para varios BDD, el tamaño puede ser exponencial. Además, dado que la construcción del BDD de una función booleana resuelve el problema de satisfacción booleana NP-completa y el problema de tautología co-NP completa , la construcción del BDD puede llevar un tiempo exponencial en el tamaño de la fórmula booleana incluso cuando el BDD resultante es pequeño.

El cálculo de la abstracción existencial sobre múltiples variables de BDD reducidas es NP-completo.