Cálculo relacional de tupla

cálculo de tupla é um cálculo criado e introduzido por Edgar F. Codd como parte do modelo relacional, a fim de fornecer um idioma declarativo de banco de dados para manipulação de dados nesse modelo de dados. Ele formou a inspiração para os idiomas de banco de dados Quel e SQL, dos quais o último, embora muito menos fiel ao modelo relacional e cálculo original, agora é a linguagem de banco de dados padrão de fato; Um dialeto do SQL é usado por quase todos os sistemas de gerenciamento 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 o CODD, mostrou que esses dois cálculos (assim como a álgebra relacional) são equivalentes no poder expressivo. Posteriormente, os idiomas de consulta para o modelo relacional foram chamados de completa de se eles pudessem expressar pelo menos todas essas consultas.

Como o cálculo é um idioma de consulta para bancos de dados relacionais, primeiro precisamos definir um banco de dados relacional. O bloco de construção relacional básico é o domínio (um pouco 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 são mapeadas vagamente aos conceitos tradicionais de banco de dados. Uma tabela é uma representação visual aceita de uma relação; Uma tupla é semelhante ao conceito de uma fila.

Primeiro, assumimos a existência de um conjunto C de nomes de colunas, cujos exemplos são o nome " #34;, etc. 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 (consulte o modelo relacional para mais sobre as noções de e valor atômico ), R é um conjunto finito de nomes de relações e

h: R → 2^C

Uma função que associa um cabeçalho a cada nome de 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 colunas, mas também mapeia esses nomes de colunas para um domínio.) Dado um domínio d Definimos uma tuple sobre d como uma função parcial que mapeia alguns nomes de colunas para um valor atômico em d . Um exemplo seria (nome: " Harry ", 25).

): C ⇸ D

O conjunto de todas as tuplas sobre d é denotado como t d . O subconjunto de c para o qual uma tupla t é definido é chamado de domínio de t (a não ser confuso com o domínio no esquema) e indicado como dom ( t ).

Finalmente, definimos um banco de dados relacional dado um esquema s = ( d , r , H ) como uma função

D: R → 2^T_D

que mapeia os nomes de relação em r para subconjuntos finitos de t d , de modo que para cada relação nome r em r e tupla t em db ( r )

Dom!()) = h(R).

O último requisito simplesmente diz que todas as tuplas em uma relação devem conter os mesmos nomes de colunas, a saber, os definidos para ele no esquema.

Para a construção das fórmulas, assumiremos um conjunto infinito v de variáveis de tupla. As fórmulas são definidas, dado um esquema de banco de dados s = ( d , r , h ) e uma função parcial < i> type : v ⇸ 2 c , chamado em TIPO AQUIDAMENTO , que atribui cabeçalhos a 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 O quê? em V, um em tipo(v) e b) em tipo(O quê?) então a fórmula v.um = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = O quê?.b) em ANão.S,tipo]
2. se v em V, um em tipo(v) e k denota um valor em D então a fórmula v.um = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = k em ANão.S,tipoE
3. se v em V, R em R e tipo(v) = h(R) então a fórmula R(v) está em ANão.S,tipo].

Exemplos de átomos são:

• ().age = S— ) tem um atributo de idade e S tem um atributo de idade com o mesmo valor
• ().name = "Codd") — tupla ) tem um atributo de nome e seu valor é "Codd"
• Livro()) — tuplas ) está presente em relação Livro.

A semântica formal de tais átomos é definida, dado um banco de dados db sobre s e uma variável de tupla de ligação val : v → t d que mapeia variáveis de tupla para tuplas sobre o domínio em s :

1. v.um = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = O quê?.b) é verdade se e somente se valor(v)um) = valor(O quê?)b))
2. v.um = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = k é verdade se e somente se valor(v)um) = k
3. R(v) é verdade se e somente se valor(v) está em D(R)

Os átomos podem ser combinados em fórmulas, como é habitual 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 ANão.S,tipoTambém está dentro FNão.S,tipo]
2. se f₁ e f₂ em FNão.S,tipo] então a fórmula f₁ ∧ f₂ também está em FNão.S,tipo]
3. se f₁ e f₂ em FNão.S,tipo] então a fórmula f₁ ∨ f₂ também está em FNão.S,tipo]
4. se f em FNão.S,tipoEntão a fórmula f também está em FNão.S,tipo]
5. se v em V, H. H. H. um cabeçalho e f uma fórmula em FNão.S,tipo_{Não.v- Sim.H. H. H.]}] então a fórmula ∃ v: H. H. H. (f) também está em FNão.S,tipoOnde? tipo_{Não.v- Sim.H. H. H.]} denota a função que é igual a tipo exceto que mapeia v para H. H. H.,
6. se v em V, H. H. H. um cabeçalho e f uma fórmula em FNão.S,tipo_{Não.v- Sim.H. H. H.]}] então a fórmula ∀ v: H. H. H. (f) também está em FNão.S,tipo]

Exemplos de fórmulas:

• ).name = "C. J. Date" ∨ )Nome = "H. Darwen"
• Livro()) ∨ Magazine())
• Gerenciamento de contas ): {autor, título, assunto} (Livro()) ).author = "C. J. Date" ∧ ¬ ().subject = "modelo relacional")))

Observe que a última fórmula afirma que todos os livros que são escritos por C. J. Date têm como sujeito o modelo relacional. Como sempre, omitimos suportes se isso não causa ambiguidade sobre a semântica da fórmula.

Vamos assumir que os quantificadores quantificam sobre o universo de todas as tuplas sobre o domínio no esquema. Isso leva à seguinte semântica formal para fórmulas, dado um banco de dados db sobre s e uma variável de tupla de ligação val : v > -& gt; t d :

1. f₁ ∧ f₂ é verdade se e somente se f₁ é verdade e f₂ é verdade,
2. f₁ ∨ f₂ é verdade se e somente se f₁ é verdade ou f₂ é verdade ou ambos são verdadeiros,
3. ? f é verdade se e somente se f não é verdade,
4. Detalhe v: H. H. H. (f) é verdade se e somente se houver um tupla ) sobre D tal que Dom!()) = H. H. H. e a fórmula f é verdade valor_{Não.v- Sim.)]}e
5. Gerenciamento de contas v: H. H. H. (f) é verdade se e somente se para todas as tuplas ) sobre D tal que Dom!()) = H. H. H. a fórmula f é verdade valor_{Não.v- Sim.)]}.

Finalmente, definimos como é uma expressão de consulta, dado um esquema s = ( d , r , h ):

( v: H. H. H. | f(v?

onde v é uma variável de tupla, h um cabeçalho e f ( v ) uma fórmula em < i> f [ s , tipo ] onde type = {( v , H )} e com v como é apenas uma 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:

• ( ): {name} | ∃ S(nome, salário)S) S.wage = 50.000 ∧ ).name = S- Nome?
• ( ): {supplier, article} | ∃ S: {s#, sname} (Fornecedor(S) S.sname = ).supplier ∧ ∃ p(p#, pname) (Produto(p) p.pname = ).article ∧ ∃ um(Supplies()um) SNão. umNão. umNão. p.p#))

Como a semântica dos quantificadores é tal que eles quantificam todas as tuplas sobre o domínio no esquema, pode ser que uma consulta possa retornar um resultado diferente para um determinado banco de dados se outro esquema for presumido. Por exemplo, considere os dois esquemas s ₁ = ( 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:

D (₁", { ("a", 1) }

Se considerarmos a seguinte expressão de consulta

( ): ).a = )- Sim.

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 um conjunto infinito, o resultado da consulta também será infinito. Para resolver esses problemas, restringiremos 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 de tupla variam sobre as tuplas sobre o chamado domínio ativo do banco de dados, que é o subconjunto do domínio que ocorre em AT em AT Pelo menos uma tupla no banco de dados ou na expressão da consulta, a semântica das expressões de consulta não muda. De fato, 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 do domínio independente.

Para limitar as expressões de consulta, de modo que elas expressam apenas consultas independentes do 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. O primeiro é se um par de colunas variáveis t . Dois pares de colunas variáveis são equivocadas direta ou indiretamente (denotado t . v == s . w ).

Para derivar a limitação, apresentamos as seguintes regras de raciocínio:

1. em " v.um = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = O quê?.b) "nenhum par de coluna variável é limitado,
2. em " v.um = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = k "o par variável-coluna v.um está ligado,
3. em " R(v) " todos os pares v.um estão ligados um em tipo(v),
4. em " f₁ ∧ f₂ "todos os pares estão ligados ou dentro f₁ ou em f₂,
5. em " f₁ ∨ f₂ "todos os pares são amarrados que estão ligados tanto em f₁ e em f₂,
6. em " f "nenhum par está ligado,
7. em " v: H. H. H. (f" um par O quê?.um está ligado se estiver ligado f e O quê? <> ve
8. em " v: H. H. H. (f" um par O quê?.um está ligado se estiver ligado f e O quê? <> v.

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

1. em " v.um = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = O quê?.b) "detém que v.um - Sim. O quê?.b),
2. em " v.um = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = k "nenhum par é igualado,
3. em " R(v) " nenhum par é igualado,
4. em " f₁ ∧ f₂ "detém que v.um - Sim. O quê?.b) se ele se agarrar f₁ ou em f₂,
5. em " f₁ ∨ f₂ "detém que v.um - Sim. O quê?.b) se segurar ambos f₁ e em f₂,
6. em " f "nenhum par é igualado,
7. em " v: H. H. H. (f) "detém que O quê?.um - Sim. x.b) se ele se agarrar f e O quê?<>v e x<>ve
8. em " v: H. H. H. (f) "detém que O quê?.um - Sim. x.b) se ele se agarrar f e O quê?<>v e x<>v.

Dizemos então que uma expressão de consulta {v: h | f (v)} é seguro se

• para cada nome de coluna um em H. H. H. nós podemos derivar v.um é igualado com um par em f,
• para cada subexpressão de f da forma " Ÿ O quê?: G (g) " podemos derivar isso para cada nome da coluna um em G nós podemos derivar O quê?.um é igualado com um par em ge
• para cada subexpressão de f da forma " ∃ O quê?: G (g) " podemos derivar isso para cada nome da coluna um em G nós podemos derivar O quê?.um é igualado com um par em g.

A restrição às expressões de consulta segura não limita a expressividade, uma vez que todas as consultas independentes do domínio que podem ser expressas também podem ser expressas por uma expressão de consulta segura. Isso pode ser comprovado mostrando que para um esquema s = ( d , r , h ), um dado Definir 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 afirma que seu valor está no domínio ativo. Por exemplo, suponha que k = {1,2}, r = {" r "} e h = { (("

v.b = 1 ∨ v.b = 2 ∨ ∃ O quê? (r(w) ∧ (v.b = O quê?.a ∨ v.b = O quê?.b))

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

• DES – Uma ferramenta educacional para trabalhar com Tuple Relacional Calculus e outras linguagens formais
• WinRDBI – Uma ferramenta educacional para trabalhar com Tuple Relacional Calculus e outras linguagens formais

• Álgebra relacional
• Cálculo relacional
  • Cálculo relacional de domínio (DRC)

• Edgar F. Codd: Um modelo relacional de dados para grandes compartilhados Bancos de Dados. Comunicações da ACM, 13(6):377–387, 1970.