BASES DE DATOS IN.CO. 92 SOLUCION PRACTICO 3 Ejercicio 1. i) Ya que el numero de estaciones y el numero de vagones es conocido podemos usar arrays para representar el problema. ESTACIONES | | | | | | | | ------------------------------------- 1 2 3 ........ i ........... e tipo sig ____________________ VAGONES 1 |___________|________| 2 |___________|________| 3 |___________|________| 4 |___________|________| . | | | . | | | . | | | . |___________|________| v |___________|________| TYPE ident_estacion = 1..e; ident_vagon = 1..v; estaciones = ARRAY [ident_estacion] OF ident_vagon; reg_vagon = RECORD tipo : 1..t; /* para simplificar el problema */ sig : ident_vagon; END; vagones = ARRAY [ident_vagon] OF reg_vagon; VAR tab_estac : estaciones; tab_vag : vagones; p : ident_vagon; Un algoritmo para expresar dicha consulta podria ser: read (estacion); p := tab_estac [estacion]; WHILE p <> 0 DO BEGIN print (p); p := tab_reg [p].sig; END En el caso promedio (suponiendo que cualquier estacion puede ser requerida con igual probabilidad) y calculando el orden con respecto a la asignacion tenemos: 1 + v/e . ii) Para resolver esta consulta podemos: a) Utilizar la estructrura de la parte i). b) Modificar la estructura para obtener un algoritmo con mejor orden. _s a) read (t); FOR i := 1 to DO BEGIN IF t = tab_vag [i].tipo THEN print (i); END En este caso el numero de asignaciones esta dado por el for que es 1 + v. b) Como existen t tipos de vagones con t conocido podriamos definir: TIPOS_VAG |__|__|__|______________|__| 1 2 3 ............... t ______________ VAGONES 1 |_________|____| 2 |_________|____| 3 |_________|____| . | | | . | | | . | | | . | | | . |_________|____| v |_________|____| TYPE ident_tipo = 1..t; tipos_vag = ARRAY [ident_tipo] OF ident_vagon; reg_vagon = RECORD estacion : ident_estacion; sig : ident_vagon; END; vagones = ARRAY [ident_vagon] OF reg_vagon; VAR tab_tipos_vag : tipos_vag; tab_vag : vagones; p : ident_vagon; Un algoritmo podria ser: read(t); p := tab_tipos_vag [t]; WHILE p <> 0 DO BEGIN print (p); p := tab_vag [p].sig; END En el caso promedio (suponiendo que cualquier tipo de vagon puede ser requerido con igual probabilidad) : 1 + v/t . _s iii) Vamos a resolver esta consulta con los dos estructuras anteriores. 1) read(t); read(estacion); p := tab_estac [estacion]; c := 0; WHILE p <> 0 DO BEGIN IF t = tab_vag[p].tipo THEN c := c + 1; p := tab_vag[p].sig; END print (c); 2) read(t); read(estacion); p := tab_tipos_vag [t]; c := 0; WHILE p <> 0 DO BEGIN IF estacion = tab_vag [p].estacion THEN c := c + 1; p := tab_vag[p].sig; END print (c); b) Segun como interpretemos que cada vagon esta asignado a un estacion sera mejor representarlo con un esquema relacion o con 2. 1) Si suponemos que toda estacion tiene vagones => ASIGNACION ( estacion, vagon, tipo) 2) Si suponemos que existen estaciones sin vagones => ASIGNACION ( estacion, vagon, tipo) ESTACIONES ( estacion ) ã S1estacionT (ASIGNACION) C_ ESTACIONES Resolvemos los requerimientos anteriores: i) supongamos dada la estacion: e ã S1vagonT ( åS1estacion = "e"T (ASIGNACION)) ii) supongamos dado el tipo de vagon : tv ã S1vagonT ( åS1tipo = "tv"T (ASIGNACION)) iii) Dado que necesitamos realizar una operacion aritmetica y que en el algebra relacional "puro" no tenemos operadores aritmeticos, esta consulta no la podemos expresar en algebra relacional. Mas adelante en el curso veremos lenguajes de consulta comerciales que incorporan lo que se llaman "operadores agregados". Por ej. en SQL esta consulta se resolveria: SELECT count(vagon) FROM asignacion WHERE estacion = "e" AND tipo = "tv" _s El objetivo de este ejercicio fue principalemente mostrar la forma diferente de expresar y pensar el problema en lenguajes como Pascal y en DBMS basados en el modelo relacional. Si bien a esta altura del curso no tenemos elementos para hablar de eficiencia al resolver consultas en lenguajes basados en algebra o calculo relacional podemos notar que, en principio, los DBMSs realizan una optimizacion de consultas que es "transparente" para el programador. Para cada consulta el optimizador de consultas decide un "plan" para ejecutar la consulta definiendo indices adecuados, etc. Ejercicio 2. a) ãS1aulaT (HORARIOS |><| ãS1codigoT (åS1insc > 100T CURSOS)) b) Consideremos que los instructores con nro. de telefono y oficina desconocidos son aquellos que no figuran en INSTRUCTORES. A = ãS1instrucT (ASIGNADOS) - ãS1nombreT (INSTRUCTORES) S = ãS1nombreT (CURSOS |><| ãS1codigoT ( A |><| ASIGNADOS)) c) ãS1nombreT (CURSOS |><| ãS1codigoT (ASIGNADOS |><| INSTRUCTORES)) inst = nombre d) åS1$1 < $2T (ãS1$1, $2T (PRERREQ |><| PRERREQ) $2 = $4 Por $n representamos el atributo que ocupa el n_esimo lugar en el esquema. e) f) y g) No son resolubles en Alg. Relacional, ya que en este lenguaje no se cuenta con funciones de conteo. h) A = ãS1aulaT (åS1cod = "CSC434"T HORARIOS ) S = ãS1codigoT (HORARIOS|><|A) - ãS1codigoT (åS1cod = "CSC434"T HORARIOS) || \/ Esto es para que no aparezca CSC434. i) ãS1instructorT (åS1$2 = $5 and $3 =$6T (ASIGNADOS x ASIGNADOS)) j) ãS1instructorT(ASIGNADOS) - ãS1instructorT(åS1$2<>$5 and $3=$6T(ASIGNADOS x ASIGNADOS)) k) ãS1prerT (åS1cod = "CSC444"T PRERREQS) En este caso se consideran las materias previas inmediatas. l) No resoluble en lenguajes relacionales pues es una clausura transitiva de PRERREQS. m) Idem e) f) y g). Ejercicio 3. i) A = ãS1nom_eqT(PARTICIPA|><|ãS1ano,serieT (åS1ano = "1986"T PARTICIPA)) || \/ Nombres de equipos de la misma serie que Alemania en 1986. S = ãS1nom_eqT ((åS1nom_eq=AlemaniaT PARTIDO) U (åS1nom_eq=AlemaniaT PARTIDO))|><|A S1and ano=1986T S1and ano=1986T S1and goles2 > goles1T S1and goles2 > goles1T _s ii) A = ãS1nom_eq1T(åS1goles1 > goles2T) U ãS1nom_eq2T(åS1goles2 > goles1T PARTIDO) || S1and fecha = "040686"T S1and fecha = "040686" \/ Nombres de equipos que ganaron el 4/6/86. S = ãS1direc_tecT(A |><| åS1ano = 1986T(PARTICIPA)) iii) A = ãS1nom_eqT(ãS1serieT(å PARTICIPA) |><| ãS1serie,nom_eqT(å PARTICIPA)) || S1nom_eq = UruguayT S1posicion = 1T || S1and ano = 1986T S1and ano=1986T \/ Primero de la serie de Uruguay en 1986. B = ãS1nom_eq2T(åS1goles1 > goles2T (A |><| PARTIDO)) || S1and ano = 1986T S1nom_eq = nom-eq1T || || U || || ãS1nom_eq1T(åS1goles1 < goles2T (A |><| PARTIDO)) || S1and ano = 1986T S1nom_eq = nom_eq2T \/ Equipos que perdieron con el primero de la serie de Uruguay en 1986. S = ãS1cant_camp_ganadosT(EQUIPO |><| B) Ejercicio 4. FRECUENTA(BEBEDOR,BAR) SIRVE(BAR,CERVEZA) LE_GUSTA(BEBEDOR,CERVEZA) a) ãS1barT(SIRVE |><| (åS1bebedor = "J. Fernandez"T (LE_GUSTA))) b) ãS1bebedorT (FRECUENTA |><| ãS1bebedor,barT(SIRVE |><| LE_GUSTA)) c) S=ãS1bebedorT(FRECUENTA)-ãS1bebedorT(FRECUENTA-ãS1bebedor,barT(SIRVE|><|LE_GUSTA)) || || \/ \/ El resultado esta compuesto por los A bebedores que solo frecuentan bares que \___________________________________ sirven alguna cerveza que les guste. B \_______________________________________________ C A = Devuelve las parejas (bebedor,bar) tal que el bar sirve una cerveza que al bebedor le gusta. B = Devuelve las parejas (bebedor,bar) tal que el bebedor frecuenta el bar y en dicho bar no sirven cerveza que le gusta al bebedor (ninguna). C = Devuelve los bebedores que frecuentan bares que no sirven ninguna cerveza que les guste. Observar que tambien podrian frecuentar otros bares donde si sirven cerveza que les guste. _s d) ãS1bebedorT(FRECUENTA)-ãS1bebedorT(FRECUENTA|><|ãS1bebedor,barT(SIRVE|><|LE_GUSTA)) \_______________________________________________ Bebedores que frecuentan algun bar que sirve alguna cerveza que les guste. (parte b). Esta consulta devuelve los bebedores que no frecuentan bares que sirven cervezas que les gusta. Ejercicio 5. a). ã ( LOCALES|><|MAQUINAS|><|JUEGOS ) % ã ( å JUEGOS ) #L,prom_f,#juego #juego origen = "japones" b). A = ã ( å JUEGOS ) ; tipos de los juegos de origen tipos origen = coreano "coreano" B = ã ( MAQUINAS|><|JUEGOS ) #L,tipo S = B % A c). A = ã ( LOCALES ) #L,cant_maq B = ã A cant_maq S = ã ( ( ã ( A |><| A ) ) % B ) $1 $1,$2,$3 $2 ò $4 d). A = ã ( å MAQUINAS ) ; juegos del local 28 $2 $3=28 B = ã ( MAQUINAS ) $3,$2 C = B % A; locales que tienen todos los juegos que estan en el 28 y posiblemente otros. D = ã ( ( å MAQUINAS ) |><| MAQUINAS ) $6 $3=28 $2 <> $5 E = C - D ; locales que tienen exactamente los mismos juegos que el local 28 F = ã ( ã ( å LOCALES ) |><| LOCALES ) $2 $4 $1=28 $1 <> $4 locales con distinto promedio que el 28 S = E ï F _s Ejericio 6. S11T) A = S1$1,$6T(PRT |><| PRT) ; pares de partes tales que la 1a. tiene S1$4 <= $9T peso <= que la 2a. S = A % ãS1$1T PRT S12T) S = ãS1$1T(åS1$3 = 1T PPC ) ï ãS1$1T(åS1$3 = 2T PPC) S13T) A = ãS1$1T(åS1$3 = rojoT PRT) S = ãS1#provT (PPC |><| A) S1#par = #parT S1and #proy = 1T S14T) A = ãS1$1T(åS1$3 = rojoT PRT) B = ãS1$1T(åS1$3 = Londres or $3 = ParisT PRY) S = ãS1$1T((A |><| PPC) |><| B) S1$1=$3T S1$4=$6T S15T) S = ãS1$1,$11T((PRV |><| PPC) |><| PRY) S1$1 = $5T S1$7 = $9T S16T) S = ãS1$1,$6,$11T(åS1$1 <> $11T((PRV |><| PPC) |><| PRY) S1$1 = $5T S1$7 = $9T S17T) S = ãS1$1T((ãS1$1,$2,$3TPPC) % (ãS1$1T PRY)) S18T) S = ãS1$3T(åS1$1 = 9T (PPC)) - ãS1$3T(åS1 <> 9T (PPC))