Cálculo relacional de tupla - Tuple relational calculus

O cálculo de tupla é um cálculo que foi criado e introduzido por Edgar F. Codd como parte do modelo relacional , a fim de fornecer uma linguagem de consulta de banco de dados declarativa para manipulação de dados neste modelo de dados . Ele serviu de inspiração para as linguagens de consulta de banco de dados QUEL e SQL , das quais a última, embora muito menos fiel ao modelo relacional e cálculo original, é agora a linguagem de consulta de banco de dados padrão de fato; um dialeto do SQL é usado por quase todos os sistemas de gerenciamento de banco de dados relacional . Michel Lacroix e Alain Pirotte propuseram cálculo de domínio , que está mais próximo da lógica de primeira ordem e juntamente com Codd mostraram que ambos os cálculos (assim como a álgebra relacional ) são equivalentes em poder expressivo. Posteriormente, as linguagens de consulta para o modelo relacional foram chamadas de relacionalmente completas se pudessem expressar pelo menos todas essas consultas.

Definição do cálculo

Banco de dados relacional

Como o cálculo é uma linguagem de consulta para bancos de dados relacionais , primeiro temos que definir um banco de dados relacional. O bloco de construção relacional básico é o domínio (algo semelhante, mas não igual a, um tipo de dados ). Uma tupla é uma sequência finita de atributos , que são pares ordenados de domínios e valores. Uma relação é um conjunto de tuplas (compatíveis). Embora esses conceitos relacionais sejam definidos matematicamente, essas definições mapeiam vagamente para os conceitos tradicionais de banco de dados. Uma mesa é uma representação visual aceita de uma relação; uma tupla é semelhante ao conceito de linha .

Em primeiro lugar, assumimos a existência de um conjunto C de nomes de colunas, exemplos dos quais são "nome", "autor", "endereço", etc. Nós definimos cabeçalhos como subconjuntos finitos de C . Um esquema de banco de dados relacional é definido como uma tupla S = ( D , R , h ) onde D é o domínio dos valores atômicos (veja o modelo relacional para mais noções de domínio e valor atômico ), R é um conjunto finito de nomes de relação , e

h  : R → 2 C

uma função que associa um cabeçalho com cada nome relação em R . (Observe que esta é uma simplificação do modelo relacional completo onde há mais de um domínio e um cabeçalho não é apenas um conjunto de nomes de coluna, mas também mapeia esses nomes de coluna para um domínio.) Dado um domínio D , definimos uma tupla sobre D como uma função parcial que mapeia alguns nomes das colunas para um valor atómica em D . Um exemplo seria (nome: "Harry", idade: 25).

t  : C ⇸ D

O conjunto de todos os tuplos mais D é indicada como T D . O subconjunto de C para o qual uma tupla t é definida é chamado de domínio de t (não deve ser confundido com o domínio no esquema) e denotado como dom ( t ).

Finalmente, definimos um banco de dados relacional dado um esquema S = ( D , R , h ) como uma função

db  : R → 2 T D

que mapeia os nomes de relação em R para subconjuntos finitos de T D , de modo que para cada nome de relação r em R e tupla t em db ( r ), ele mantém que

dom ( t ) = h ( r ).

O último requisito simplesmente diz que todas as tuplas em uma relação devem conter os mesmos nomes de coluna, ou seja, aqueles definidos para ela no esquema.

Átomos

Para a construção das fórmulas, assumiremos um conjunto infinito V de variáveis ​​de tupla. As fórmulas são definidas a partir de um esquema de banco de dados S = ( D , R , h ) e um tipo de função parcial  : V ⇸ 2 C , chamado na atribuição de tipo , que atribui cabeçalhos a algumas variáveis ​​de tupla. Em seguida, definimos o conjunto de fórmulas atômicas A [ S , tipo ] com as seguintes regras:

  1. se v e w em V , a no tipo ( v ) eb no tipo ( w ), então a fórmula v . a = w . b está em A [ S , tipo ],
  2. se v em V , a no tipo ( v ) ek denota um valor em D, então a fórmula v . a = k está em A [ S , tipo ], e
  3. se v em V , r em R e tipo ( v ) = h ( r ) então a fórmula r ( v ) está em A [ S , tipo ].

Exemplos de átomos são:

  • ( t. idade = s. idade) - t tem um atributo de idade es tem um atributo de idade com o mesmo valor
  • ( t .name = "Codd") - tupla t tem um atributo de nome e seu valor é "Codd"
  • Livro ( t ) - tupla t está presente na relação Livro.

A semântica formal de tais átomos é definida dado um banco de dados db sobre S e uma ligação variável de tupla val  : V → T D que mapeia variáveis ​​de tupla para tuplas sobre o domínio em S :

  1. v . a = w . b é verdadeiro se e somente se val ( v ) ( a ) = val ( w ) ( b )
  2. v . a = k é verdadeiro se e somente se val ( v ) ( a ) = k
  3. r ( v ) é verdadeiro se e somente se val ( v ) está em db ( r )

Fórmulas

Os átomos podem ser combinados em fórmulas, como é usual na lógica de primeira ordem, com os operadores lógicos ∧ (e), ∨ (ou) e ¬ (não), e podemos usar o quantificador existencial (∃) e o quantificador universal (∀) para ligar as variáveis. Definimos o conjunto de fórmulas F [ S , tipo ] indutivamente com as seguintes regras:

  1. cada átomo em A [ S , tipo ] também está em F [ S , tipo ]
  2. se f 1 e f 2 estão em F [ S , tipo ], então a fórmula f 1 ∧ f 2 também está em F [ S , tipo ]
  3. se f 1 e f 2 estão em F [ S , tipo ], então a fórmula f 1 ∨ f 2 também está em F [ S , tipo ]
  4. se f está em F [ S , tipo ], então a fórmula ¬ f também está em F [ S , tipo ]
  5. se v em V , H um cabeçalho ef a fórmula em F [ S , digite [ v -> H ] ] então a fórmula ∃ v  : H ( f ) também está em F [ S , tipo ], onde tipo [ v - > H ] denota a função que é igual ao tipo, exceto que mapeia v para H ,
  6. se v em V , H um cabeçalho ef a fórmula em F [ S , digite [ v -> H ] ], então a fórmula ∀ v  : H ( f ) também está em F [ S , tipo ]

Exemplos de fórmulas:

  • t .name = "Data CJ" ∨ t .name = "H. Darwen"
  • Livro ( t ) ∨ Revista ( t )
  • ∀ t  : {autor, título, assunto} (¬ (Livro ( t ) ∧ t .author = "CJ Date" ∧ ¬ ( t .subject = "modelo relacional")))

Observe que a última fórmula afirma que todos os livros escritos por CJ Date têm como assunto o modelo relacional. Como de costume, omitimos colchetes se isso não causar ambigüidade sobre a semântica da fórmula.

Assumiremos que os quantificadores quantificam no universo de todas as tuplas no domínio do esquema. Isso leva à seguinte semântica formal para fórmulas dadas um banco de dados db sobre S e uma variável de ligação de tupla val  : V -> T D :

  1. f 1 ∧ f 2 é verdadeiro se e somente se f 1 for verdadeiro e f 2 for verdadeiro,
  2. f 1 ∨ f 2 é verdadeiro se e somente se f 1 for verdadeiro ou f 2 for verdadeiro ou ambos forem verdadeiros,
  3. ¬ f é verdadeiro se e somente se f não for verdadeiro,
  4. ∃ v  : H ( f ) é verdadeiro se e somente se houver uma tupla t sobre D tal que dom ( t ) = H e a fórmula f é verdadeira para val [ v -> t ] , e
  5. ∀ v  : H ( f ) é verdadeiro se e somente se para todas as tuplas t sobre D tal que dom ( t ) = H a fórmula f é verdadeira para val [ v -> t ] .

Consultas

Finalmente, definimos a aparência de uma expressão de consulta dado um esquema S = ( D , R , h ):

{ v  : H | f ( v )}

onde v é uma variável tupla, H um cabeçalho ef ( v ) uma fórmula em F [ S , tipo ] onde tipo = {( v , H )} e com v como sua única variável livre. O resultado de tal consulta para um determinado banco de dados db sobre S é o conjunto de todas as tuplas t sobre D com dom ( t ) = H tal que f é verdadeiro para db e val = {( v , t )}.

Exemplos de expressões de consulta são:

  • { t  : {nome} | ∃ s  : {nome, salário} (Funcionário ( s ) ∧ s .wage = 50.000 ∧ t .nome = s .nome)}
  • { t  : {fornecedor, artigo} | ∃ s  : {s #, sname} (Fornecedor ( es ) ∧ s .sname = t .supplier ∧ ∃ p  : {p #, pname} (Produto ( p ) ∧ p .pname = t .artigo ∧ ∃ a  : { s #, p #} (Suprimentos ( a ) ∧ s .s # = a .s # ∧ a .p # = p .p #)))}

Restrição semântica e sintática do cálculo

Consultas independentes de domínio

Como a semântica dos quantificadores é tal que eles quantificam todas as tuplas do domínio no esquema, pode ser que uma consulta retorne um resultado diferente para um determinado banco de dados se outro esquema for presumido. Por exemplo, considere os dois esquemas S 1 = ( D 1 , R , h ) e S 2 = ( D 2 , R , h ) com domínios D 1 = {1}, D 2 = {1, 2}, nomes de relação R = {"r 1 "} e cabeçalhos h = {("r 1 ", {"a"})}. Ambos os esquemas têm uma instância comum:

db = {("r 1 ", {("a", 1)})}

Se considerarmos a seguinte expressão de consulta

{ t  : {a} | t .a = t .a}

então seu resultado em db é {(a: 1)} em S 1 ou {(a: 1), (a: 2)} em S 2 . Também ficará claro que, se considerarmos o domínio como um conjunto infinito, o resultado da consulta também será infinito. Para resolver esses problemas, vamos restringir nossa atenção às consultas que são independentes do domínio , ou seja, as consultas que retornam o mesmo resultado para um banco de dados em todos os seus esquemas.

Uma propriedade interessante dessas consultas é que, se assumirmos que as variáveis ​​da tupla variam sobre as tuplas no chamado domínio ativo do banco de dados, que é o subconjunto do domínio que ocorre em pelo menos uma tupla no banco de dados ou na consulta expressão, então a semântica das expressões de consulta não muda. Na verdade, em muitas definições do cálculo da tupla, é assim que a semântica dos quantificadores é definida, o que torna todas as consultas por definição independentes do domínio.

Consultas seguras

Para limitar as expressões de consulta de modo que expressem apenas consultas independentes de domínio, geralmente é introduzida uma noção sintática de consulta segura . Para determinar se uma expressão de consulta é segura, derivaremos dois tipos de informações de uma consulta. A primeira é se um par de coluna variável t . a está ligado à coluna de uma relação ou constante, e a segunda é se dois pares de coluna variável são direta ou indiretamente equacionados (denotado t . v == s . w ).

Para derivar limites, introduzimos as seguintes regras de raciocínio:

  1. em " v . a = w . b " nenhum par variável-coluna está vinculado,
  2. em " v . a = k " o par de coluna variável v . a está ligado,
  3. em " r ( v )" todos os pares v . a são vinculados a a no tipo ( v ),
  4. em " f 1 ∧ f 2 " estão ligados todos os pares que estão ligados em f 1 ou em f 2 ,
  5. em " f 1 ∨ f 2 " estão ligados todos os pares que estão ligados tanto em f 1 quanto em f 2 ,
  6. em "¬ f " nenhum par está ligado,
  7. em "∃ v  : H ( f )" um par w . a é limitado se for limitado em f e w <> v , e
  8. em "∀ v  : H ( f )" um par w . a é limitado se for limitado em f e w <> v .

Para derivar equação, introduzimos as seguintes regras de raciocínio (ao lado das regras de raciocínio usuais para relações de equivalência: reflexividade, simetria e transitividade):

  1. em " v . a = w . b ", ele mantém que v . a == w . b ,
  2. em " v . a = k " nenhum par é igualado,
  3. em " r ( v )" nenhum par é igualado,
  4. em " f 1 ∧ f 2 ", considera-se que v . a == w . b se for válido em f 1 ou em f 2 ,
  5. em " f 1 ∨ f 2 ", considera-se que v . a == w . b se for válido tanto em f 1 quanto em f 2 ,
  6. em "¬ f " nenhum par é igualado,
  7. em "∃ v  : H ( f )" ele sustenta que w . a == x . b se for válido em f e w <> v e x <> v , e
  8. em "∀ v  : H ( f )" ele sustenta que w . a == x . b se detém na f e w <> v e x <> v .

Em seguida, dizemos que uma expressão de consulta {v: H | f (v)} é seguro se

  • para cada nome de coluna a em H podemos derivar que v . a é igualado a um par ligado em f ,
  • para cada subexpressão de f da forma "∀ w  : G ( g )", podemos derivar que, para cada nome de coluna a em G , podemos derivar esse w . a é igualado a um par ligado em g , e
  • para cada subexpressão de f da forma "∃ w  : G ( g )", podemos derivar que, para cada nome de coluna a em G , podemos derivar esse w . a é igualado a um par ligado em g .

A restrição a expressões de consulta seguras não limita a expressividade, pois todas as consultas independentes de domínio que podem ser expressas também podem ser expressas por uma expressão de consulta segura. Isso pode ser provado mostrando que para um esquema S = ( D , R , h ), um determinado conjunto K de constantes na expressão de consulta, uma variável de tupla v e um cabeçalho H podemos construir uma fórmula segura para cada par v . a com a em H que indica que seu valor está no domínio ativo. Por exemplo, suponha que K = {1,2}, R = {"r"} e h = {("r", {"a," b "})}, então a fórmula segura correspondente para v .b é:

v .b = 1 ∨ v .b = 2 ∨ ∃ w (r (w) ∧ ( v .b = w .a ∨ v .b = w .b))

Esta fórmula, então, pode ser usada para reescrever qualquer expressão de consulta insegura em uma expressão de consulta segura equivalente, adicionando tal fórmula para cada variável v e nome de coluna a em seu tipo onde é usado na expressão. Efetivamente, isso significa que deixamos todas as variáveis ​​variarem no domínio ativo, o que, como já foi explicado, não altera a semântica se a consulta expressa for independente do domínio.

Sistemas

Veja também

Referências