Validitet og reliabilitet

Esta se¸c˜ao apresenta as principais regras alg´ebricas envolvendo condi¸c˜oes baseadas em tupla e condi¸c˜oes baseadas em agrega¸c˜ao em geral.

Regra 4.1 (Condi¸c˜ao nula) Um operador ckNN com condi¸c˜ao nula ´e equivalente ao

operador kNN convencional em uma sele¸c˜ao por similaridade agregada, isto ´e: ¨

σSckNN[δ,∆,k,NULL] Q(R) ⇔ ¨σS kNN[δ,∆,k] Q(R) (4.1)

A regra da condi¸c˜ao nula ´e a propriedade fundamental do operador ckNN como uma

extens˜ao do operador kNN. Desta forma, o operador ckNN ´e capaz de responder a con-

sultas aos k-vizinhos mais pr´oximos agregados, e tamb´em a consultas aos k-vizinhos mais pr´oximos convencionais, quando o conjunto de elementos de referˆencia ´e unit´ario e omite- se a fun¸c˜ao agregadora de distˆancias ∆.

Regra 4.2 (Antecipa¸c˜ao de condi¸c˜oes baseadas em tupla) Uma sele¸c˜ao por simi- laridade envolvendo um operador ckNN, cuja condi¸c˜ao ´e uma condi¸c˜ao baseada em tupla

tcond, pode ser antecipada por uma sele¸c˜ao convencional cuja express˜ao condicional ´e tcond, ou seja:

¨

σSckNN[δ,∆,k,tcond] Q(R) ⇔ ¨σSckNN[δ,∆,k] Q(σtcond(R)) (4.2)

A Regra 4.2 possibilita explorar planos alternativos de consulta, com base na seletivi- dade de tcond e na existˆencia de estruturas de indexa¸c˜ao que permitam agilizar o acesso

aos dados com base nesta condi¸c˜ao. Esta regra n˜ao se aplica se a condi¸c˜ao do operador

ckNN ´e uma acond, pois condi¸c˜oes baseadas em agrega¸c˜ao n˜ao s˜ao v´alidas como express˜ao

condicional de uma sele¸c˜ao convencional. As regras a seguir tratam da antecipa¸c˜ao de tconds em conjun¸c˜oes e disjun¸c˜oes de condi¸c˜oes.

Regra 4.3 (Antecipa¸c˜ao de tcond em conjun¸c˜oes de tconds) Uma sele¸c˜ao por similaridade envolvendo um operador ckNN, cuja condi¸c˜ao ´e uma express˜ao conjuntiva

envolvendo duas condi¸c˜oes quaisquer baseadas em tupla tcond1 e tcond2, pode ser ante-

cipada por uma sele¸c˜ao convencional cuja express˜ao condicional ´e qualquer uma dessas condi¸c˜oes, conforme estabelecem as duas equivalˆencias a seguir:

¨

σSckNN[δ,∆,k,tcond₁∧tcond₂] Q(R) ⇔ ¨σSckNN[δ,∆,k,tcond₁] Q(σtcond₂(R)) (4.3)

¨

σSckNN[δ,∆,k,tcond1∧tcond2] Q(R) ⇔ ¨σSckNN[δ,∆,k,tcond2] Q(σtcond1(R)) (4.4)

A combina¸c˜ao das equivalˆencias 4.3 e 4.4 permite gerar uma sequˆencia de sele¸c˜oes con- vencionais antecipadas `a sele¸c˜ao por similaridade, derivando, por consequˆencia, a Equi- valˆencia 4.5.

¨

σSckNN[δ,∆,k,tcond1∧tcond2] Q(R) ⇔ ¨σSckNN[δ,∆,k] Q(σtcond1∧tcond2(R)) (4.5)

Caso umack-NNq seja restrita por uma conjun¸c˜ao de uma condi¸c˜ao baseada em tupla

tcond e de uma condi¸c˜ao baseada em agrega¸c˜ao acond, vale a regra a seguir. Regra 4.4 (Antecipa¸c˜ao de tcond em conjun¸c˜oes de tconds com aconds) Uma sele¸c˜ao por similaridade envolvendo um operador ckNN, cuja condi¸c˜ao ´e uma

express˜ao conjuntiva envolvendo uma condi¸c˜ao baseada em tupla tcond e uma condi¸c˜ao baseada em agrega¸c˜ao acond, pode ser antecipada por uma sele¸c˜ao convencional cuja express˜ao condicional ´e a condi¸c˜ao tcond, isto ´e:

¨

σSckNN[δ,∆,k,tcond∧acond] Q(R) ⇔ ¨σSckNN[δ,∆,k,acond] Q(σtcond(R)) (4.6)

Caso a condi¸c˜ao do operador ck-NN seja uma disjun¸c˜ao de condi¸c˜oes, as propriedades

v´alidas s˜ao diferentes. Se cond ´e uma uma disjun¸c˜ao de duas condi¸c˜oes tcond e c, sendo que tcond ´e uma condi¸c˜ao baseada em tupla e c ´e uma condi¸c˜ao de qualquer tipo (baseada em tupla ou baseada em agrega¸c˜ao), n˜ao se pode antecipar `a sele¸c˜ao por similaridade uma sele¸c˜ao convencional tendo apenas tcond como predicado, como mostra a Express˜ao 4.7.

¨

σSckNN[δ,∆,k,tcond∨c] Q(R) < ¨σSckNN[δ,∆,k,c] Q(σtcond(R)) (4.7)

Entretanto, se cond for uma disjun¸c˜ao de duas condi¸c˜oes baseadas em tupla, embora as condi¸c˜oes baseadas em tupla n˜ao possam ser antecipadas isoladamente, ´e poss´ıvel fazer

a antecipa¸c˜ao considerando a express˜ao disjuntiva como um todo, como enuncia a regra a seguir.

Regra 4.5 (Antecipa¸c˜ao de disjun¸c˜oes de tconds) Uma sele¸c˜ao por similaridade envolvendo um operador ckNN, cuja condi¸c˜ao ´e uma express˜ao disjuntiva envolvendo

quaisquer duas condi¸c˜oes baseadas em tupla tcond1 e tcond2, pode ser antecipada por

uma sele¸c˜ao convencional cuja express˜ao condicional ´e a express˜ao disjuntiva, conforme estabelece a equivalˆencia a seguir:

¨

σSckNN[δ,∆,k,tcond1∨tcond2] Q(R) ⇔ ¨σSckNN[δ,∆,k] Q(σtcond1∨tcond2(R)) (4.8)

A aplica¸c˜ao da Regra 4.5 pode ser extrapolada para conjun¸c˜oes de condi¸c˜oes, quando uma express˜ao disjuntiva de condi¸c˜oes baseadas em tupla pode ser tratada como uma condi¸c˜ao composta, como mostra a Equivalˆencia 4.9:

¨

σSckNN[δ,∆,k,c∧(tcond₁∨tcond₂)] Q(R) ⇔ ¨σSckNN[δ,∆,k,c] Q(σtcond1∨tcond2(R)) (4.9)

onde c ´e uma condi¸c˜ao de qualquer tipo (baseada em tupla ou baseada em agrega¸c˜ao). Neste caso, a express˜ao disjuntiva pode ser movimentada pois ´e uma condi¸c˜ao composta, delimitada por parˆenteses.

Vale ressaltar que n˜ao se pode transformar uma conjun¸c˜ao de duas condi¸c˜oes no opera- dorckNN de uma sele¸c˜ao por similaridade em uma interse¸c˜ao de duas sele¸c˜oes por simila-

ridade, cada uma com uma das condi¸c˜oes, independentemente do tipo das condi¸c˜oes. Da mesma forma, uma disjun¸c˜ao de condi¸c˜oes no operador ckNN n˜ao pode ser transformada

em uma uni˜ao de sele¸c˜oes. Ou seja, uma sele¸c˜ao por similaridade envolvendo um operador

ckNN, cuja condi¸c˜ao ´e uma express˜ao conjuntiva, ou disjuntiva, de condi¸c˜oes simples, n˜ao

´e equivalente `a interse¸c˜ao, ou `a uni˜ao, de sele¸c˜oes por similaridade envolvendo o operador

ckNN, cujas condi¸c˜oes s˜ao partes partes da express˜ao original da consulta, independen-

temente dos tipos das condi¸c˜oes. Esta observa¸c˜ao ´e expressa algebricamente por meio das express˜oes 4.10 e 4.11, sendo c1 e c2 duas condi¸c˜oes quaisquer (baseadas em tupla ou

baseadas em agrega¸c˜ao). ¨

σSckNN[δ,∆,k,c1∧c2] Q(R) < ¨σSckNN[δ,∆,k,c1] Q(R) ∩ ¨σSckNN[δ,∆,k,c2] Q(R) (4.10)

¨

σSckNN[δ,∆,k,c₁∨c₂] Q(R) < ¨σSckNN[δ,∆,k,c₁] Q(R) ∪ ¨σSckNN[δ,∆,k,c₂] Q(R) (4.11)

Isso explicita que a interpreta¸c˜ao que uma sele¸c˜ao conjuntiva/disjuntiva pode ser ex- pressa por uma interse¸c˜ao/uni˜ao de sele¸c˜oes, v´alida para a sele¸c˜ao tradicional, n˜ao se aplica `a sele¸c˜ao por similaridade ¨σ com um operador ckNN. As se¸c˜oes a seguir apresen-

tam regras de equivalˆencia para os diferentes tipos de condi¸c˜oes baseadas em agrega¸c˜ao propostos.

4.3.2

Regras

Alg´ebricas

Envolvendo

Condi¸c˜oes

Baseadas

em