Download Diapositiva 1 - fc

Modelo relacional
Informática aplicada
Contenido
• Estructura de las bases de datos
relacionales
• Operaciones básicas del álgebra
relacional
• Operaciones adicionales del álgebra
relacional
• Valores nulos
• Modificación de la base de datos
Ejemplo de una relación
Estructura básica
Formalmente, dados los conjuntos D1, D2, …, Dn una relación es un
subconjunto de
D1 D2,  Dn
Entonces, una relación es un conjunto de n-tuplas (a1, a2, …, an) donde
cada a1 D1.
• Ejemplo: Si
– custome_name = {Jones, Smith, Curry, Linsay, …} /*conjunto de todos los
nombre*/
– customer_street = {Main, North, Park, …} /*conjunto de todos los nombres de
calles*/
– customer_city = {Harrison, Rye, Pittsfield, ..} /*conjunto de todos los nombres de
ciudades*/
Entonces r = {(Jones, Main, Harrison),
(Smith, North, Rye),
(Curry, North, Rye),
(Linsay, Park, Pittsfield)}
Es una relación sobre
custome_name  customer_street  customer_city
Tipos de atributos
• Cada atributo de una relación tiene nombre
• El conjunto de valores permitidos para cada atributo es
llamado el dominio del atributo.
• Los valores de los atributos (normalmente) se requiere
que sea atómicos, esto es, idivisibles.
– Los valores multivaluados no son atómicos
– Los atributos compuestos no son atómicos
• Un valor especial null es miembro de todo dominio.
• Los valores nulos causan complicaciones en la
definición de mucha operaciones.
– Ignoraremos los efectos de los valores nulos en nuestra
presentación principal y consideraremos sus efectos después.
Esquema de relaciones
• A1, A2, …, An son atributos
• R = (A1, A2, …, An ) es un esquema de
relación
Customer_schema = (customer_name,
customer_street, customer_city)
• r(R) es una relación en el esquema de
relación R
customer(Customer_schema)
Esquemas del banco
• Account-schema = (account-number, branch-name,
balance)
• Branch-schema = (branch-name, branch-city, assets)
• Customer-schema = (customer-name, customer-street,
customer-city)
• Depositor -schema = (customer-name, account-number)
• Loan-schema = (loan-number, branch-name, amount)
• Borrower-schema = (customer-name, loan-number)
Instancia de relación
• Los valores actuales (instancia de relación) de una
relación son especificados por una tabla
• Un elemento t de r es una tupla, representada por un
renglón en la tabla
atributos
(o columnas)
customer-name customer-street
Jones
Smith
Curry
Lindsay
Main
North
North
Park
customer
customer-city
Harrison
Rye
Rye
Pittsfield
tuplas
(o renglones)
Las relaciones no tiene orden
• El orden en la tuplas es irrelevante (las tuplas se pueden almacenar
en orden arbitrario)
• Relación account con tuplas desordenadas
Bases de datos
• Una base de datos consiste de múltiples relaciones
• La información acerca de una empresa es rota en partes, con cada
relación guardando una parte de la información
– account: guarda información de las cuentas
– depositor: guarda información acerca de que cliente posee cual cuenta.
– customer: guarda información acerca de los clientes
• Guardando información como una relación simple como
bank(account_number, balance, customer_name, …) resulta en
– Repetición de infrormación (dos clientes poseen una cuenta)
– Necesidad de valores nulos (representar un cliente sin una cuenta)
• La teoría de normalización trata del diseño de esquemas
relacionales.
La relación customer
La relación depositor
Diagrama ER para el banco
Claves
• Sea K  R
• K es superllave de R los valores de K son suficientes para
identificar una tupla única de cada posible relación r(R)
– Por “posible r” queremos decir una relación r que puede existir en una
empresa que estemos modelando.
– Ejemplo: {cutomer_name, customer_street} y {cutomer_name}
– Son ambas superllaves de customer, si ningún par de clientes pueden
tener el mismo nombre.
• K es una llave candidata si K es mínima.
• Ejemplo: {cutomer_name} es una llave candidata para customer, ya
que es una supellave , y ningún subconjunto de esta es superllave.
• Debe cumplirse que si t1 y t2 están en r y t1  t2, entonces t1[K] 
t2[K].
Determinando claves desde
conjuntos ER
• Conjunto de entidades fuertes: La llave primaria de una entidad
viene a ser la llave primaria de la relación
• Conjunto de entidades débil: La llave primaria de la relación
consiste de la unión de la llave primaria de la entidad fuerte y el
discriminador de la entidad debil
• Conjunto de relaciones: La unión de las llaves primarias de los
conjuntos de entidades relacionadas es la superllave de una
relación.
– Para un conjunto de relaciones binarias de mucho a uno, la llave
primaria del conjunto de entidades “muchos” es la llave primaria de la
relación
– Para un conjunto de relaciones uno a uno, la llave primaria de la
relación puede ser cualquiera de las llaves de los conjuntos de
entidades.
– Para un conjunto de relaciones muchos a muchos, la unión de las
llaves primarias viene a ser la llave primaria de la relación
Diagrama esquema para la
empresa del banco
En el diagrama del esquema aparece cada relación como un rectángulo con
loa atributos listados adentro y el nombre de la relación arriba. En un recuadro
superior del rectángulo aparecen los atributos clave. Las dependencias de
llaves foráneas aparecen como flechas desde la llave foránea hasta la llave
primaria de la relación referenciada.
Lenguajes de consulta
• Lenguajes para que el usuario solicite
información de la base de datos
• Categorías de los lenguajes
– Procedural
– No Procedural
• Lenguajes puros
– Álgebra relacional
– Cálculo relacional de tuplas
– Cálculo relacional de dominios
• Los lenguajes puros forman la base de los
lenguajes de consulta que usa la gente
Álgebra relacional
• Lenguaje procedural
• Seis operadores básicos
–
–
–
–
–
–
Selección
Proyección
Unión
Diferencia de conjuntos
Producto cartesiano
Renombrado
• Los operadores toman dos o más relaciones
como entrada y generan una nueva relación
como resulatdo
Operación de selección - ejemplo
Relación r
A B C D
a
a
b
b
sA=B^D>5(r)
a
b
b
b
1 7
5 7
12 3
23 10
A B C D
a
b
a
b
1 7
23 10
Operación de selección
• Notación: sp(r)
• p es llamado predicado de selección
• Definido como:
sp(r) = {t | t  r y p(t)}
Donde p es una fórmula del cálculo proposicional
consistiendo de términos conectados por:  (y),  (o),
 (no)
Cada término es uno de:
<atributo> op <atributo> o <constante>
Donde op es uno de: =, , >,  ,<, 
• Ejemplo de selección:
sbranch_name(account)
Ejemplos
sbranch_name=‘Perryridge’ (loan)
sloan>1200 (loan)
sloan>1200 ^ branch_name=‘Perryridge’ (loan)
sloan>1200 ^ loan<4000 (loan)
Operación de proyección - ejemplo
Relación r
A B C
a
a
b
b
PA, C(r)
10
20
30
40
1
1
1
2
A C
A C
a
a
b
b
a
b
b
1
1
1
2
1
1
2
Operación de proyección
• Notación: PA1,A2,…,Ak(r)
• Donde A1, A2, son nombres de atributos y r es
el nombre de la relación
• El resultado está definido como una relación de
k columnas obtenidas al borrar las columnas no
listadas
• Los renglones duplicados son eliminados del
resultado, yaque son conjuntos
• Ejemplo: para eliminar el atributo branch_name
de account
Paccount_number, balance(account)
Operación de unión - ejemplo
Relaciones r y s
rs
A B
A B
a
a
b
a
b
1
2
1
A B
a
a
b
b
1
2
1
3
2
3
Operación de unión
•
•
Notación: r  s
Definido como:
•
Para que r  s sea válido
r  s = {t | t  r o t  s}
1. r y s deben tener la misma aridad (mismo número
de atributos)
2. Los atributos deben ser compatibles (los valores de
las columnas correspondientes debes ser del mismo
tipo)
•
Ejemplo: encontrar todos los clientes con una
cuenta o un préstamo
Pcustomer_name(depositor)  Pcustomer_name(borrowert
Operación de diferencia - ejemplo
Relaciones r y s
r-s
A B
A B
a
a
b
a
b
1
2
1
A B
a
b
1
1
2
3
Operación de diferencia
•
•
Notación: r - s
Definido como:
•
Para que r - s sea válido
r - s = {t | t  r y t  s}
1. r y s deben tener la misma aridad (mismo número
de atributos)
2. Los atributos deben ser compatibles (los valores de
las columnas correspondientes debes ser del mismo
tipo)
•
Ejemplo: encontrar todos los clientes con una
cuenta pero sin un préstamo
Pcustomer_name(depositor) - Pcustomer_name(borrower)
Operación de producto cartesiano ejemplo
Relaciones r y s
A B
C D E
a
b
a
b
b
g
1
2
A B C D E
rs
a
a
a
a
b
b
b
b
1
1
1
1
2
2
2
2
a
b
b
g
a
b
b
g
10
10
20
10
10
10
20
10
a
a
b
b
a
a
b
b
10
10
20
10
a
a
b
b
Operación de producto cartesiano
• Notación: r  s
• Definido como:
r  s = {t q | t  r y q  s}
• Se supone que los atributos de r(R) y
s(S) son disjuntos. (R  S = )
• Si no son disjuntos, se debe usar
renombrado.
Composición de operaciones
• Se pueden construir expresiones usando
múltiples operaciones
A B C D E
• Ejemplo: sA=B (r  s)
• rs
A B C D E
•
sA=B (r  s)
a
b
b
1
2
2
a
b
b
10
10
20
a
a
b
a
a
a
a
b
b
b
b
1
1
1
1
2
2
2
2
a
b
b
g
a
b
b
g
10
10
20
10
10
10
20
10
a
a
b
b
a
a
b
b
Ejemplos
• Nombres de clientes que viven en Harrison.
Pcustomer-name (scustomer-city =“Harrison”(customer))
• bcustomer_name, borrower.loan_number, loan.loan_number,
branch_name, amount
sbranch-name =“Perryridge”(borrower × loan)
• Misma que la anterior pero de clientes que SI tiene préstamo.
sborrower.loan_number = loan.loan_number (sbranch-name =“Perryridge”(borrower × loan))
• Solo los nombres
Pbcustomer_name(sborrower.loan_number = loan.loan_number (sbranch-name
=“Perryridge”(borrower × loan)))
Operación de renombrado
• Permite nombrar, y por lo tanto referirse a, el resultado
de una expresión del álgebra relacional
• Permite referirse a una relación con más de un noombre
Ejemplo:
r x (E)
regresa la expresión E bajo el nombre x.
Si la expresión de álgebra relacional E tiene aridad n,
entonces
r x(A1, A2,…, An) (E)
regresa la expresión E bajo el nombre x y con los atributos
renombrados A1, A2, …, An.
Banking Example
branch (branch-name, branch-city, assets)
customer (customer-name, customer-street,
customer-only)
account (account-number, branch-name, balance)
loan (loan-number, branch-name, amount)
depositor (customer-name, account-number)
borrower (customer-name, loan-number)
Example Queries
• Encontrar todos los préstamos sobre $1200
samount > 1200 (loan)
Encontrar los números de préstamo para cada préstamo para el
cual la cantidad es mayos que $1200.
loan-number (samount > 1200 (loan))
Example Queries
• Encontrar los nombres de todos los clientes que tienen un
préstamo, o una cuenta o ambos en el banco.
customer-name (borrower)  customer-name (depositor)
•Encontrar los nombres de todos los clientes que tienen un
préstamo y una cuenta en el banco.
customer-name (borrower)  customer-name (depositor)
Example Queries
• Encontrar los nombres de todos los clientes que tienen un préstamo en
la sucursal Perryridge
customer-name (sbranch-name=“Perryridge”
(sborrower.loan-number = loan.loan-number(borrower x loan)))
 Encontrar los nombres de todos los clientes que tienen un préstamo
en la sucursal Perryridge pero que no tienen cuenta en cualquier
sucursal del banco.
customer-name (sbranch-name = “Perryridge”
(sborrower.loan-number = loan.loan-number(borrower x loan))) –
customer-name(depositor)
•
Example
Queries
Encontrar los nombres de todos los clientes que tienen un préstamo en
la sucursal Perryridge
Query 1
customer-name(sbranch-name = “Perryridge” (
sborrower.loan-number = loan.loan-number(borrower x loan)))
 Query 2
customer-name(sloan.loan-number = borrower.loan-number(
(sbranch-name = “Perryridge”(loan)) x borrower))
Example Queries
Encontrar la cuenta con el saldo más alto. Renombre la relación
account como d
La consulta es
balance(account) - account.balance
(saccount.balance < d.balance (account x rd (account)))
Definiciones formales
• Una expresión básica del álgebra relacional consiste de
una de las siguientes:
– Una relación en la base de datos
– Una relación constante
• Sean E1 y E2 expresiones del álgebra relacional: las
siguientes son todas expresiones del álgebra relacional:
E1  E2
E1 – E2
E1  E2
sp(E1), p es un predicado en atributos en E1
Ps(E1), S es una lista consistiendo de algunos de los atributos
en E1
– r x (E1) x es un nuevo nombre para el resultado de E1.
–
–
–
–
–
Operaciones adicionales
Agregaremos nuevas operaciones que no
añaden poder al álgebra relacional, pero
que simplifican consultas comunes.
• Intersección de conjuntos
• Reunión natural
• División
• Asignación
Operación de intersección
•
•
Notación: r  s
Definido como:
r  s = {t | t  r y t  s}
•
Para que r  s sea válido
1. r y s deben tener la misma aridad (mismo número
de atributos)
2. Los atributos deben ser compatibles (los valores de
las columnas correspondientes debes ser del mismo
tipo)
•
Nota: r  s = r – ( r – s)
Operación de unión - ejemplo
Relaciones r y s
rs
A B
A B
a
a
b
a
b
1
2
1
A B
a
2
2
3
Operación unión natural
• Notación: r
s
• Sean r y s relaciones en los esquemas R y S respectivamente.
Entonces, r s es una relación en esquema R  S obtenida como
sigue:
– Considere un par de tuplas tr en r y ts en s.
– Si tr y ts tienen el mismo valor en cada uno de los atributos de R  S,
agregar t al resultado, donde
• t tiene el mismo valor que tr en r
• t tiene el mismo valor que ts en s
• Ejemplo
– R = (A, B, C, D)
– S = (E, B, D)
– Esquema resultante = (A, B, C, D, E)
– r s se define como:
Pr.A, r.B, r.C, r.D, s.E(s r.B = s.B ^ r.D = s.D(r  s))
Ejemplo de reunión natural
r
a
b
g
a
d
r
s
A B C D
s
1
2
4
1
2
a
g
b
g
b
a
a
b
a
b
B D E
A B C D E
a
a
a
a
d
1
1
1
1
2
a
a
g
g
b
a
a
b
a
b
a
g
a
g
d
1
3
1
2
3
a
a
a
b
b
a
b
g
d
e
Operación de división
rs
• Adecuada para las consultas que incluyen
la frase “para todos”
• Sean r y s relaciones en los esquemas R y
S respectivamente donde:
– R = (A1, …, Am, B1, …, Bn)
– S = (B1, …, Bn)
– El resultado de r  s es una relación en el
esquema R – S = (A1, …, Am)
• r  s = {t | t  PR-S(r) ^  u  s(tu  r) }
Ejemplo de división
B
A B
r
a
a
a
b
g
d
d
d
e
e
b
1
2
3
1
1
1
3
4
6
1
2
s
1
2
rs
A
a
b
Otro ejemplo de división
r
A B C D E
a
a
a
b
b
g
g
g
a
a
a
a
a
a
a
a
a
g
g
g
g
g
g
b
a
a
b
a
b
a
b
b
1
1
1
1
3
1
1
1
s
D E
a
b
rs
1
1
A B C
a
g
a
a
g
g
Operación de división cont.
• Propiedad
– Sea q – r  s
– Entonces q es la relación más grande que satisface q
rs
• Definición en términos de las operaciones
básicas del álgebra relacional. Sea r(R) y s(S)
relaciones, y sea S  R
r  s = PR–S(r) – PR–S((PR–S(r)  s) – PR–S,S(r))
• Para ver como
– PR–S,S(r) simplemente reordena los atributos de r
– PR–S((PR–S(r)  s) – PR–S,S(r)) da aquellas tuplas en
PR–S(r) tales que para alguna tupla u  s, ts  r.
Operación de asignación
• La operación de asignación ( ) provee una forma
conveniente de expresar consultas complejas.
– Escriba consultas como un programa secuencial consistiendo en
• Una seria de asignaciones
• Seguidas por una expresión cuyo valor es desplegado como
resultado de la consulta
– Las asignaciones deben ser hechas sobre variables de relación
temporales
• Ejemplo: escriba r  s como
temp1  PR–S(r)
temp2  PR–S((temp1  s) – PR–S,S(r))
result  temp1 – temp2
El resultado a la derecha de  es asignado a la variable
relación a la izquierda de  .
– Se puede usar la variable en las expresiones subsecuentes.
–
–
–
–
Ejemplos de Consultas
• Encontrar los clientes que tienen una cuenta en por lo
menos en la sucursal “Downtown” y “Uptows”
Consulta 1
CN(sBN=“Downtown”(depositor
account)) 
CN(sBN=“Uptown”(depositor
account))
Donde CN denota customer-name y BN denota
branch-name.
Consulta 2
customer-name, branch-name (depositor account)
 rtemp(branch-name) ({(“Downtown”), (“Uptown”)})
Ejemplos de Consultas
• Encontrar todos los clientes que tienen
una cuenta en alguna sucursal de
Brooklyn
customer-name, branch-name (depositor account)
 branch-name (sbranch-city = “Brooklyn” (branch))
Operaciones extendidas del
álgebra relacional
• Proyección Generalizada
• Unión externa
• Funciones de Agregación
Proyección generalizada
• Extiende la operación de proyección permitiendo que
funciones aritméticas sean usadas en la lista de
proyección.
 F1, F2, …, Fn(E)
• E es cualquier expresión del álgebra relacional
• Cada una de las F1, F2, …, Fn son expresiones
aritmeticas involucrando constantes and atributos en el
esquema de E.
• Dada la relación credit-info(customer-name, limit, creditbalance), encontrar cuanto más puede una persona
gastar:
customer-name, limit – credit-balance (credit-info)
Funciones de agregación y
operadores
• Las funciones de Agregación toma una colección de
valores y regresa un valor simple como resultado.
avg: valor promedio
min: valor mínimo
max: valor máximo
sum: suma de values
count: number of values
• Operación de agregación en álgebra relacional
G1, G2, …, Gn g F1( A1), F2( A2),…, Fn( An) (E)
– E es cualquier expresión de álgebra relacional
– G1, G2 …, Gn es una lista de atributos en los cuales agrupar
(puede estar vacío)
– Cada Fi es una función de agregación
– Cada Ai es un nombre de atributo
Ejemplo de funciones de
agregación
• Relación r:
g sum(c) (r)
A
B
C
a
a
b
b
a
b
b
b
7
sum-C
27
7
3
10
Ejemplo de funciones de
agregación
• Relación account agrupada por branch-name:
branch-name account-number
Perryridge
Perryridge
Brighton
Brighton
Redwood
branch-name
g
balance
A-102
A-201
A-217
A-215
A-222
sum(balance)
400
900
750
750
700
(account)
branch-name
Perryridge
Brighton
Redwood
balance
1300
1500
700
Funciones de agregación (cont.)
• Los resultados de las funciones de agregación no
tienen nombre
– Se puede usar la operación de renombrado
– Por conveniencia se permite el renombrado en las funciones
de agregación.
branch-name
g
sum(balance) as sum-balance (account)
Unión externa
• Una extensión de la operación de unión para
evitar pérdida de información
• Calcula la unión luego agrega tuples desde una
relación que no ajustan en la otra relación al
resultado de la unión.
• Usa valores nulos.
– null significa que el valor es desconocido o no existe
– Todas laqs comparaciones involucrando nulos son
(rigurosamente) falsos por definición
• Las comparaciones con nulos se verán más adelante
Ejemplo de unión externa
• Relation loan
loan-number
branch-name
L-170
L-230
L-260
Downtown
Redwood
Perryridge
amount
3000
4000
1700
 Relation borrower
customer-name loan-number
Jones
Smith
Hayes
L-170
L-230
L-155
Ejemplo de unión externa
• Inner Join reunión interna
loan
Borrower
loan-number
L-170
L-230
branch-name
Downtown
Redwood
amount
3000
4000
customer-name
Jones
Smith
 Left Outer Join (unión externa izquierda)
loan
Borrower
loan-number
L-170
L-230
L-260
branch-name
Downtown
Redwood
Perryridge
amount
3000
4000
1700
customer-name
Jones
Smith
null
Ejemplo de unión externa
• Right Outer Join (unión externa derecha)
loan
borrower
loan-number
L-170
L-230
L-155
branch-name
Downtown
Redwood
null
amount
3000
4000
null
customer-name
Jones
Smith
Hayes
 Full Outer Join (reunión externa total)
loan
borrower
loan-number
L-170
L-230
L-260
L-155
branch-name
Downtown
Redwood
Perryridge
null
amount
3000
4000
1700
null
customer-name
Jones
Smith
null
Hayes
Valores nulos
• Es posible que una tupla tenga valores nulos, denotados por null,
para algunos de sus atributos.
• Null significa valor desconocido o que el valor no existe
• El resultado de operaciones aritméticas involucrando null es null
– Ej. 5 + null es null
• Las funciones de agregación ignoran los valores nulos.
– Es una decisión arbitraria. Podría regresar nulo.
– Siguen la semántica de SQL en el manejo de nulos
• para eliminar duplicados y agrupación, los nulos son tratados como
cualquier otro valor, y dos nulos se suponen ser iguales.
– Alternativas: suponen que los nulos son diferentes
– Ambas decisiones arbitrarias, se sigue SQL
Valores nulos
• Cualquier comparación con null regrese desconocido
– Ej. 5<num o nul<>nul o nul=nul
• Lógica de tres valores usando el valor desconocido:
– OR: (desconocido or true) = true
(desconocido or falso) = desconocido
(desconocido or desconocido ) = desconocido
– AND: (desconocido and true) = desconocido
(desconocido or falso) = false
(desconocido or desconocido ) = desconocido
– NOT: desconocido = desconocido
– “P es desconocido” se evalua como true si el predicado P se
evalua como desconocido.
• El resultado de la cláusula select es tratado como false
si se evalua a desconocido.
Modificación de la base de datos
• El contenido de la base de datos puede
ser modificado por las siguientes
operaciones
– Borrado
– Inserción
– Actualización
• Todas las operaciones se expresan
mediante asignación
Borrado
• Una petición de borrado se expresa como una
consulta. Excepto que en lugar de desplega
tupla al usuario, las tuplas seleccionadas son
borradas de la base de datos
• Solo se pueden borrar tuplas completas, no se
pueden borrar atributos particulares
• El borrado se expresa en álgebra relacional
mediante
– r r–E
• Donde r es una relación y E es una consulta del
álgebra relacional
Ejemplo de borrado
• Borra todos los registros de cuentas en la sucursal
Perryridge
account  account – s branch-name = “Perryridge” (account)
• Borra todos los registros de préstamos con cantidades
entre 0 y 50
loan  loan – s amount  0 and amount  50 (loan)
• Borra todas las cuentas en todas las sucursales
localizadas en Needham.
•
•
•
r1  s branch-city = “Needham” (account
branch)
r2  branch-name, account-number, balance (r1)
r3   customer-name, account-number (r2
account  account – r2
depositor  depositor – r3
depositor)
Inserción
• Para insertar en una relación, nosotros o bien:
– Especificamos la tupla a ser insertada
– Escribir una consulta cuyo resultado sea un conjunto
de tuplas a insertar
• En álgebra relacional, una inserción se expresa
por:
– rrE
Donde r es una relación y E es una expresión del
álgebra relacional
La inserción de una sola tupla se expresa por E como
una relación constante conteniendo una tupla
Ejemplos de inserción
• Inserte información en la base de datos
especificando que Smith tiene $1200 en la
cuenta A-913 en la sucursal Perryridge
– account  account  {“A-913”, “Perryridge” ,1200}
– depositor  depostor {“Smith”,“A-913”}
• Como un regalo para todas las cuentas en
Perryridge, una cuenta de $200. El número del
préstamo sirve como número de cuenta para la
cuenta nueva.
– r1  (s branch-name = ‘Perryridge’(borrower loan))
– account  account  P loan-number,branch-name,200(r1)
– depositor  depositor  P customer-name, loan_number(r1)