Relações. Parte I

A teoria formal da modelagem usa relações algébricas, incluindo-as nas assinaturas de modelos de estruturas algébricas, que descrevem objetos físicos, técnicos e informacionais reais, os processos de seu funcionamento. Entre os últimos, incluo, por exemplo, bancos de dados (bancos de dados relacionais (RDBs)). Considero a área da tomada de decisão não menos importante, que consiste em duas principais estatísticas e algébricas, baseadas inteiramente na teoria das relações. O nível educacional dos especialistas nesta teoria é próximo a zero.



Abra o livro de especialização e lá você verá, na melhor das hipóteses, sobre equivalências, que são interpretadas pelos autores de uma forma muito peculiar. Pergunto a um DTN já defendido: Você considera a relação de equivalência não indicando nem o portador do relacionamento, nem um relacionamento específico, como fica no seu prontuário? Resposta: o que parece - geralmente. Acontece que ele tem uma ideia muito vaga de tudo isso.



Acho difícil nomear publicações sobre o projeto de um ReDB, exceto para artigos estrangeiros. Na década de 90, ele foi um adversário, escreveu a resenha de uma tese, que considerava bancos de dados hierárquicos, em rede e relacionais. Mas uma vez por ano, há um ano e meio, voltou a haver trabalho em revista, o autor já escreve apenas sobre o DB, sobre a normalização das relações do DB, mas não apresentou nenhuma novidade teórica. Muitas universidades ministram um curso sobre bancos de dados, mas não sobre como criá-los, criar um SGBD, mas, via de regra, sobre como operar um banco de dados pronto (estrangeiro).



Rev. a equipe não está pronta para ensinar especialistas de TI a criar DBMS, SO e linguagens de programação domésticos, sem mencionar LSI, VLSI, LSI customizado. Aqui, aparentemente, o trem partiu por muito tempo e por muito tempo. Então, em vão, algumas bochechas estão infladas de orgulho (leia-se esnobismo), isso pode ser visto nos comentários nas publicações de outras pessoas, mostre-se que você pode, e não se entregue a traduções inúteis e recanto de outras pessoas por causa do orgulho - "classificação" e "carma". Afeta não só a falta de criatividade, mas a simples educação e criação.



O segundo domínio que está inextricavelmente ligado aos relacionamentos é a tomada de decisão. Cada um de nós está constantemente ocupado com isso. Não vamos levantar um dedo sem uma decisão do consciente ou do inconsciente. Poucos entendem e menos ainda escrevem sobre soluções. A decisão de qualquer tomador de decisão (tomador de decisão) é baseada na preferência por alternativas. E o modelo de preferência é justamente esse tipo de relacionamento, que é chamado de “espaço de relações de preferência”. Mas quem os estuda. Quando cheguei a um “especialista” em relações com uma pergunta sobre o número de relacionamentos de cada tipo, ele, sem saber a resposta, “matou” com uma contra-pergunta, por que você precisa?

Conceito de relacionamento

Acho que o termo atitude é familiar a todos os leitores, mas pedir uma definição confundirá muito. Há muitas razões para isto. São mais frequentemente em professores que, se usaram relacionamentos no processo de ensino, não focalizaram este termo, aparentemente não citaram exemplos memoráveis.



Na minha memória, há vários exemplos memoráveis ​​para toda a vida. Sobre mapeamentos e sobre relacionamentos. Vou falar sobre mapeamentos primeiro. Existem dois baldes de tinta. Em um branco, no outro - preto. E tem uma caixa de cubos (muitos). Os rostos têm números em relevo. De quantas maneiras você pode colorir as faces dos cubos com duas cores? A resposta é inesperada - até números binários de 6 bits, ou 2 ⁶= 64. Deixe-me explicar com mais detalhes f: 2 → 6 2 objetos são exibidos em 6. Cada linha da tabela é uma exibição discreta de fi.



Vamos construir uma tabela com 6 colunas e as cores corresponderão ao número branco - zero, preto - um, e as faces do cubo são colunas. Começamos com o fato de que todas as 6 faces são brancas - este é um vetor zero 6-dimensional. A segunda linha é uma face preta, ou seja, o bit menos significativo é preenchido com 1. e assim por diante até que os números binários de 6 bits se esgotem. Colocamos os cubos em uma longa fila comum. Cada um deles parece ter um número de 0 a 63.



Agora o display está invertido. Um pacote de folhas de papel (muitas) e 6 tintas (canetas hidrográficas).

Marque os dois lados das folhas de papel com canetas hidrográficas de cores diferentes. Quantas folhas são necessárias. Resposta f: 6 → 2 ou 6 ² = 36. Esses são mapeamentos arbitrários.



Vamos passar para os relacionamentos. Vamos começar com um conjunto abstrato - o portador da relação

= {a1, a2, a3, ..., an}.

Você pode ler sobre isso aqui . Para melhor compreensão, vamos reduzir o conjunto para 3 elementos, ou seja, A = {a1, a2, a3}. Agora realizamos multiplicação cartesiana × = ² ,

× = {(a1, a1), (a1, a2), (a1, a3), (a2, a1), (a2, a2), (a2, a3 ), (a3, a1), (a3, a2), (a3, a3)}.



Nós obtivemos 9 pares ordenados de elementos de A × A, em um par o primeiro elemento é do primeiro fator, o segundo do segundo. Agora, vamos tentar obter todos os subconjuntos do quadrado cartesiano A × A. Primeiro, um exemplo simples.



Exemplo 1... Um conjunto A = {a, b, c, d} de 4 elementos é dado. Escreva todos os seus subconjuntos. B (A) = {Ø}; {a}; {b}; {c}; {d}; {ab}; {ac}; {ad}; {bc}; {bd}; {cd}; { abc}; {abd}; {acd}; {bcd}; {abcd}; 2 ⁴ = 16 subconjuntos. Este é o booleano B (A) do conjunto A e inclui um subconjunto vazio.



Os subconjuntos conterão de A × A um número diferente de elementos (pares): um, dois, três e assim por diante até todos os 9 pares. Também incluímos o conjunto vazio (Ø) nesta lista. Quantos subconjuntos existem? Muitos, a saber 2 ⁹ = 512 elementos.



Definição . Qualquer subconjunto do produto cartesiano (temos um quadrado) de um conjunto é chamado de relação . Observe que a obra usa o mesmo conjunto. Se os conjuntos forem diferentes, não há uma relação, mas uma correspondência...



Se for um produto cartesiano de dois fatores, então a relação é binária , se de 3 é interna, de 4 é tetrar e de n é n-ária. Arity é o número de lugares em uma relação. Os relacionamentos recebem os nomes de letras maiúsculas R, H, P, S ... Detenhamo-nos nas relações binárias (BO), pois desempenham um papel muito importante na teoria das relações. Na verdade, todos os outros podem ser reduzidos a relações binárias.



O símbolo de relação é colocado à esquerda dos elementos R (x, y) ou entre eles x R y; x, y є A.

Definição O conjunto de todos os subconjuntos do conjunto A é chamado de Booleano. Nosso booleano consiste em 2 ^{| A × A |} elementos, aqui | A × A | É a cardinalidade do conjunto.



As relações podem ser definidas em diferentes representações sobre = {a1, a2, a3, a4}:

• enumeração de elementos; R1 = {(a1, a2), (a1, a3), (a2, a3) (a2, a4) (a3, a2) (a3, a4}
• binário n = vetor de 16 bits; <0110001101010000>;
• matriz;

Figura 1.2. a) matriz 4 × 4 da relação binária b) numeração das células da matriz



Aqui, os números de células são usados, preenchidos com uns na Fig. 1b)

- Representação vetorial. Um vetor binário para representar uma relação binária é formado a partir dos elementos {0,1} da seguinte maneira:



O exemplo considerado de configuração de um relacionamento na forma vetorial será semelhante a este:





- Representação gráfica. Vamos associar os elementos do conjunto

A = {x1, x2, z3, ..., xn} com pontos no plano, ou seja, os vértices do gráfico G = [Q, R].



Desenhe um arco no gráfico de (xi) a (xj) se e somente se o par (xi, xj) є R (para i = j, o arco (xi, xi) se transforma em um loop no vértice (xi). Exemplo (Fig. 1a) a representação da relação binária A [4 × 4] por um gráfico é mostrada na Fig.2.2.



Figura 2.2. Representação de uma relação por um grafo direcionado



Catálogo de relações binárias (n = 3)



Grande é visto à distância. Para ter uma ideia de sua diversidade, tive que criar manualmente um catálogo de relacionamento binário sobre um conjunto de 3 elementos, que incluía todos (mais de 500 relacionamentos) relacionamentos. Depois disso, veio ou acabou o relacionamento.



Obviamente, o catálogo incluirá 2 ^{3 × 3} = 2 ⁹relações, e cada um deles será equipado com um conjunto de propriedades inerentes. Abaixo (Tabela 3) está uma lista completa de todas as 512 relações no conjunto A, | A | = 3, de três elementos. Os resultados do cálculo do número de razões (Tabela 2), representados por combinações dos números de células do quadrado cartesiano 3 × 3, de diferentes subclasses para diferentes valores da cardinalidade do conjunto portador (n = 3) também são dados. Para cada relação, são indicadas suas propriedades básicas e pertencentes ao tipo (Tabela 3). As abreviaturas utilizadas no catálogo são divulgadas na Tabela 2

Tabela 2. Características quantitativas do catálogo para diferentes n





É conveniente explicar a essência das operações com relações e sua técnica usando exemplos que são especialmente simples e compreensíveis para relações binárias. As operações podem envolver dois e / ou mais relacionamentos. As operações realizadas nas relações individuais são operações unárias. Por exemplo, operações de reverter (obter inverso) uma relação, tomar um complemento, estreitar (limitar) uma relação. Um exemplo ilustrará como usar o catálogo.



Exemplo 2 . Considere a linha Npr = 14 da tabela do catálogo. Tem a forma



Os primeiros 9 caracteres da linha (à direita da igualdade) é um vetor binário correspondente a uma combinação de 9 a 2, ou seja, o número da primeira célula (contando da esquerda para a direita) é o número da 5ª célula da matriz da relação binária, ou seja, elementos a1a1 = a2a2 = 1. Essa combinação tem um número de série Ncc = 4 e um número até Npr = 14 na lista de todas as relações. O resto desta linha contém zeros ou uns. Zeros indicam a ausência de uma propriedade correspondente ao nome da coluna zero, e uns indicam a presença de tal propriedade na relação considerada.

Propriedades e características quantitativas das relações

Consideremos as propriedades mais importantes das relações, o que nos permitirá destacar ainda mais os tipos (classes) de relações usadas em bancos de dados relacionais na teoria da escolha e tomada de decisão e outras aplicações. A seguir, denotamos a relação pelo símbolo [R, Ω]. R é o nome da relação, Ω é o conjunto portador da relação.



1. Reflexividade. A relação [R, Ω] é chamada reflexiva se cada elemento do conjunto estiver na relação R consigo mesmo (Fig. 2.3). O gráfico de um BO reflexivo possui loops (arcos) em todos os vértices, e a matriz de relação contém (E) a diagonal principal unitária.





Figura 2.3. Atitude reflexiva



2. Antirreflexão. A relação [R, Ω] é chamada de anti-reflexiva se nenhum elemento do conjunto estiver na relação R consigo mesmo (Fig. 2.4). Uma relação anti-reflexiva é chamada de estrita.





Figura 2.4. Atitude



anti-reflexiva 3. Reflexividade parcial. A relação [R, Ω] é chamada parcialmente

reflexiva se um ou mais elementos do conjunto não estiverem na relação R consigo mesmo (Fig. 2.5).





4. Simetria. Uma relação [R, Ω] é denominada simétrica se, junto com um par ordenado (x, y), a relação também contém um par ordenado (y, x) (Fig. 2.6).





5. Antissimetria. Uma relação [R, Ω] é chamada de antissimétrica se, se, para qualquer par ordenado (x, y) є R, um par ordenado

(y, x) єR, apenas no caso x = y. Para tais razões R∩R ^-1 ⊆ E (Fig. 2.7).





6. Assimetria. Uma relação [R, Ω] é chamada assimétrica se for anti-reflexiva e para qualquer par ordenado (x, y) є R um par ordenado (y, x) ∉ R, para relações R ∩ R ^-1 = Ø (Fig. 2.8).





7. Transitividade. A relação [R, Ω] é chamada transitiva se para quaisquer pares ordenados (x, y), (y, z) є R, na relação R houver um par ordenado (x, z) є R ou se R × R⊆R (Fig. . 2.9).





8. Ciclicidade. Uma relação [R, Ω] é chamada cíclica se para seus elementos {x1, x2, z3, ..., xn} houver um subconjunto de elementos {xi, xi + 1, ... xr, ..., xj, xi}, para o qual podemos escrever a sequência xiRxi + 1R ... RxjRxi. Essa sequência é chamada de ciclo ou loop (Figura 2.10).





9. Aciclicidade. Relações em que não há contornos são chamadas acíclicas. Para relações acíclicas, a relação R ^k ∩R = Ø para qualquer k> 1 é válida (Fig. 2.11).







10. Completude (conectividade). A relação [R, Ω] é chamada de completa (conectada) se para quaisquer dois elementos (y, z) є Ω um deles está em relação ao outro (Fig. 2.12). Linearidade. Relacionamentos lineares são relacionamentos minimamente completos.





Figura 2.12. Relação linear



Assim, estabelecemos que as relações, como objetos matemáticos, têm certas propriedades, cuja definição é dada anteriormente. No próximo parágrafo, consideraremos a essência e a manifestação de algumas propriedades:

1. Reflexividade x є A (xRx).
2. Anti-reflexividade x є A ¬ (xRx).
3. Simetria x, y є A (xRy → yRx).
4. Antissimetria (xRy & yRx → x = y).
5. Transitividade; x, y, z є A (xRy & yRz → xRz).
6. Ciclicidade; x, y є A; ...
7. Completude x, y є (xRy, yRx);
8. Conectividade (x ≠ y → xRy, yRx).
9. Linearidade x, y є (xRy, yRx).

A análise do espaço das relações é uma tarefa complexa da teoria e, deve-se notar, está longe de estar completa. Os principais resultados devem incluir a seleção de subconjuntos de relações que formam espaços completos de relações com todas as consequências decorrentes.



As relações quantitativas de tais espaços discretos são de grande

interesse teórico e prático. Alguns aspectos das características quantitativas associadas às propriedades das relações de diferentes tipos são considerados a seguir.

Operações nas relações

Como a maioria dos sistemas numéricos com relações, as seguintes operações são realizadas:

• unário;
• binário;
• n-ário.

Abaixo estão as tabelas de adição e multiplicação Booleana ⊕ e de duas variáveis ​​x1 e x2, adição mod 2 e soma binária:





Acima, o conceito de relação binária foi introduzido, como um subconjunto de pares ordenados do produto cartesiano dos conjuntos, e as propriedades das relações também foram consideradas. Além disso, as relações binárias e a representação matricial das relações foram mencionadas. Consideremos agora o conceito de relação com mais detalhes, além disso, consideremos as operações básicas das relações binárias, as mais importantes de seu conjunto de relações.



Para eles, as seguintes condições devem ser atendidas:

• A aridade dos operandos na operação deve corresponder;
• o resultado da operação deve ser uma relação da mesma aridade.

Para relações binárias e n-árias, o seguinte deve ser satisfeito: a área de chegada do primeiro operando deve corresponder à área de origem do segundo operando.



Operações unárias em relações



Inversão de relações . O inverso da relação R é a razão R ^-1 , definida pela condição xR ^-1 y <=> yRx. Mais corretamente, essa operação deve ser chamada de pseudo-inversão, pois p · p ^-1 ≠ E = Δ.



Que a relação seja escrita na forma de listar os pares ordenados incluídos nela. Se em cada par os componentes são trocados, os novos pares formam a razão P ^-1 , que é chamada de inversa de P.



A relação inversa à relação P é aquela formada por pares (ai aj) para os quais (aj ai) є P ^-1 . Para relações em forma de matriz, as relações inversas são obtidas pela transposição da matriz P.



9. A relação dual (P ^d ) para a relação P é a relação formada por todos aqueles pares que pertencem à relação universal e não pertencem à relação inversa (adição ao inverso):



P ^d = {(ai aj) | ((ai aj) єA × A) & (ai aj) ∉ P ^-1 )} = (A × A) \ P ^-1 .



As relações duais e inversas no agregado contêm todos os pares do produto cartesiano A × A e não têm pares comuns, eles, como as relações P e P formar uma partição A × A





Observe que para qualquer relação P não é satisfeito P P = ^d .



Estreitamento (PA1). A relação [R1, A1] é chamada de restrição da relação [R, A] ao conjunto Ω1 se Ω1⊆ Ω e R1 = R∩Ω1 × Ω1. A relação PA1 no conjunto A1 ⊆ A é a relação PA1 no conjunto A1, formada por todos aqueles pares que pertencem à relação P e fazem simultaneamente parte do produto cartesiano A1 × A1. Em outras palavras, PA1 é a interseção das relações P e A1 × A1. Seja A1 = {a1, a3, a4}, então para as relações P e Q na forma de matriz, as relações de estreitamento terão a forma:





Operações binárias As operações que



requerem pelo menos duas relações são n-ário (n-ário). Apenas relações da mesma aridade podem participar de tais operações. Exemplos de tais operações: intersecção, união, diferença, diferença simétrica de relações e algumas outras. Se a operação usar mais de duas relações, ela será realizada sequencialmente para as duas primeiras e, em seguida, para a relação final e a terceira, etc.



Em outras palavras, essas operações são definidas para duas relações. Nas operações sobre relações, assume-se que os domínios para especificar relações (operandos e o resultado) coincidem, as aridades das relações coincidem e o resultado da operação é novamente uma relação da mesma aridade. Como exemplos, vamos considerar as operações nas relações binárias P e Q definidas em um conjunto discreto

= {a1, a2, a3, a4} por matrizes booleanas (como regra, zeros não cabem na matriz):





1. A intersecção (P ∩ Q) é uma relação formada por todos aqueles pares de elementos de A que estão incluídos em ambas as relações, ou seja, comum a P e Q,

P ∩ Q = {(ai aj) | ((ai aj) є P) & ((ai aj) є Q)}.



A matriz de razão P ∩ Q é obtida como a interseção booleana das matrizes P e Q:





Na ausência de tais pares comuns, a interseção de relações é considerada vazia, ou seja, é uma relação nula. A interseção das relações R1 e R2 (R1∩R2) é a relação determinada pela interseção dos subconjuntos correspondentes de A × A.



2. União (PUQ). A união das relações R1 e R2 (R1UR2) é a relação definida pela união dos subconjuntos correspondentes de A × A. A razão formada por todos os pares que constituem a razão P ou a razão Q, ou seja, por pares pertencentes a pelo menos uma das relações (o conectivo ∨ - ou o unificador)

PUQ = {(ai aj) | ((ai aj) є P) ∨ ((ai aj) є Q)}.



Se no conjunto A × A não houver outros pares que não estejam incluídos na relação PUQ, e sua interseção for zero, então as relações P e Q formam uma relação completa A × A quando combinadas, e seu sistema é uma partição dessa relação completa. A união das matrizes de relacionamento é formada como uma soma booleana das matrizes de relacionamento:





3. A diferença (P \ Q) é a razão formada pelos pares de P que não estão incluídos na relação Q

P \ Q = {(ai aj) | ((ai aj) є P) & ((ai aj) ∉Q)}.



A diferença para as relações na representação da matriz é





4. Multiplicação de relacionamentos. Os pares ordenados que formam um relacionamento podem ou não conter os mesmos elementos. Dentre os pares que possuem os mesmos elementos em sua composição, destacamos esses pares ordenados, que chamamos de adjacentes (contíguos) e que possuem o 1º elemento no segundo par, e o 2º elemento no primeiro par é o mesmo. Vamos definir o produto de pares adjacentes como um par ordenado:

(ai ak) ∙ (ak aj) => (ai aj).



Em termos de teoria de grafos, isso significa que os pares adjacentes formam uma rota do ponto (ai) ao ponto (aj) em trânsito pelo ponto (ak), que consiste em 2 arcos adjacentes. O produto desses arcos é o terceiro arco do ponto (ai) ao ponto (aj), que implementa a transição entre os pontos extremos da rota na mesma direção, contornando o ponto intermediário (ak). Diz-se que o arco (ai aj) fecha esses pontos diretamente.



5. A diferença simétrica (P∆Q) é uma razão formada pelos pares que estão incluídos na união PUQ, mas não estão incluídos na interseção P∩Q. Outra forma de definição explica o nome da operação: P∆Q é formado por aqueles pares ordenados que são a união das diferenças P \ Q e Q \ P. Assim, a expressão para a diferença simétrica pode ser escrita de duas maneiras diferentes:

P∆ Q = (PU Q) \ (P ∩ Q) = (P \ Q) U (Q \ P).



A matriz de diferença simétrica é:





Do último registro conclui-se que a operação de diferença simétrica permite a permutação dos operandos, ou seja, é comutativa.



5. Composição ou produto (P ∙ Q) - a relação formada por todos os pares em que:

P ∙ Q = {(ai aj) | ((ai ak) є P) & ((ak aj) є Q)}.



Em outras palavras, cada par ordenado na relação resultante é o resultado da multiplicação de pares adjacentes, dos quais o 1º par pertence à primeira relação fatorial, o 2º - à segunda relação fatorial. A operação de composição não é comutativa.



Composição (◦Q) em um conjunto M é uma relação R definida no mesmo conjunto M que contém um par (x, y) quando existe Z є M tal que (x, z) є P e (z, y) є Q.



Na representação matricial de relações, a matriz de composição de relações é igual ao produto booleano das matrizes das relações originais:





Um caso especial de composição de relacionamentos é a quadratura do relacionamento.



Pode-se mostrar por indução que o enésimo grau de uma relação é definido recursivamente pela fórmula: P ⁿ = P ^n-1 ◦, o que significa que o par (x, y) є P ⁿ no caso em que na matriz há uma cadeia elementos: tal que (xi, xi + 1) є P, 1 <i <n - 1.



A operação de composição tem a propriedade de associatividade (como um produto de matrizes).



A composição das relações no conjunto M é o resultado de uma composição par a par de relações para qualquer arranjo de parênteses. A área para definir o resultado da composição não muda.



A composição para matrizes booleanas de relações é formada como resultado do produto booleano das matrizes dessas relações.



Tabela 3. Catálogo de relações binárias (n = 3). Clicável