Abd procesamiento consultas (parte1)

  • CategoryEducation

  • View672

Report
  • 1. Administración de Base de Datos Procesamiento y Optimización de Consultas Prof Mercy Ospina Torres mercy.ospinat@gmail.com Prof Renny A. Hernandez renny.hernandez@ciens.ucv.ve
2. Contenido El DBA El SMBD Manejo de MemoriaRestauraciónConcurrencia Concurrencia Diccionario Datos Proc. Consultas Integridad SeguridadMarzo 2012• Cómo se procesa una consulta • Traducir una consulta de SQL a AR – Repaso Algebra Relacional• Árbol de ejecución – – – –Árbol de ejecución lógico Árbol de ejecución lineal izquierdo Árbol canónico Axiomas del Algebra relacional• Técnicas para optimizar consultas – Basada en heurísticas – Basada en costos. Administración de Base de Datos2 3. Contenido El DBA El SMBD Manejo de MemoriaRestauraciónConcurrencia Concurrencia Diccionario Datos Proc. Consultas Integridad• Modelo de costos – Factor de selectividad – Costo de los operadores del Algebra Relacional • • • • •Select Project. Join Order Árbol de ejecución físico– Evaluar el árbol de ejecución físico. • Materialización • EncausamientoSeguridadMarzo 2012Administración de Base de Datos3 4. Introducción El DBA El SMBD Manejo de MemoriaRestauración Concurrencia Diccionario Datos Proc. Consultas Consultas• Una de las funciones más importantes de los sistemas de Base de datos en la consulta. • Los SMBD relacionales usan como lenguaje de consulta SQL • Para tener mayor control de la respuesta de una consulta del DBA debe conocer que hay detrás de esa instrucción en SQLIntegridad SeguridadMarzo 2012Administración de Base de Datos4 5. Conocimientos previos El DBA El SMBD Manejo de MemoriaRestauración Concurrencia Diccionario Datos• Para el manejo conocimientos de este tema el estudiante debe tener conocimientos de: – – – – –Lenguajes de consulta SQL y Algebra Relacional Manejo de memoria en los SMBD Diccionario de datos Complejidad algorítmica ProbabilidadProc. Consultas Consultas Integridad SeguridadMarzo 2012Administración de Base de Datos5 6. Objetivos o competencias El DBA El SMBD Manejo de MemoriaRestauración Concurrencia Diccionario Datos Proc. Consultas Consultas Integridad SeguridadMarzo 2012• Al finalizar el tema el estudiante debe ser capaz de: – Traducir una consulta en SQL a una expresión del Algebra Relacional – Conocer que factores influyen en el rendimiento de una consulta – Conocer la importancia del diccionario de datos en el procesamiento de consultas – Optimizar una consulta usando técnicas heurísticas – Calcular el costo de una consulta – Conocer las utilidades del sistema manejador para consultas Administración de Base de Datos6 7. Cómo procesar una consulta El DBA El SMBD Manejo de MemoriaRestauraciónSELECT Cuenta, Saldo FROM Cuenta WHERE Saldo >40.000Procesamiento Procesamiento de consulta de consultaConcurrencia Diccionario Datos Proc. Consultas Consultas Integridad SeguridadMarzo 2012Administración de Base de Datos7 8. Cómo procesar una consulta El DBAConsulta Consulta de alto de alto nivel nivelEl SMBDAnalizador Analizador yy traductor traductorExpresión Expresión en Algebra en Algebra Relacional RelacionalρCond (R1) ρCond (R1)Manejo de MemoriaRestauración ConcurrenciaSelect * Select * From R1 From R1 Where Cond Where CondDiccionario de datosOptimiOptimizador zador Estadísticas de los datosDiccionario DatosResultado Resultado de la de la consulta consultaProc. Consultas Consultas IntegridadMarzo 2012A1A2xxyyzzyyxzPlan de Plan de ejecución ejecución Búsqueda Búsqueda binaria binariaA3xySeguridadMotor de Motor de evaluación evaluaciónBase de datosSilberschatz, Korth, & Sudarshan, 2006Administración de Base de Datos8 9. Análisis El DBAConsulta Consulta de alto de alto nivel nivelEl SMBDAnalizador Analizador yy traductor traductorManejo de MemoriaRestauración ConcurrenciaDiccionario de datos•Análisis léxico: Identifica los elementos del lenguaje como por ejemplo, las palabras reservadas de SQL, si están bien formados los nombres de los atributos y relaciones en el texto de la consulta.•Análisis sintáctico: Comprueba la sintaxis de la consulta de acuerdo a las reglas sintácticas del lenguaje de consulta.•Validación: Comprueba que los nombres de las relaciones, atributos sean válidos semánticamente dentro del esquema de la base de datos sobre la cual se realiza la consulta y si los tipos de datos se están usando correctamente.Diccionario Datos Proc. Consultas Consultas Integridad SeguridadMarzo 2012Administración de Base de Datos9 10. Procesamiento de consulta El DBAConsulta Consulta de alto de alto nivel nivelEl SMBDAnalizador Analizador yy traductor traductorExpresión Expresión en Algebra en Algebra Relacional RelacionalManejo de MemoriaRestauración Diccionario de datosConcurrencia Diccionario Datos Proc. Consultas Consultas Integridad•Traductor: Crea una representación interna de la consulta, mediante una estructura de árbol llamado árbol de consulta, el cual está basado en el álgebra relacional extendidoSeguridadMarzo 2012Administración de Base de Datos10 11. Procesamiento de consulta Expresión Expresión en Algebra en Algebra Relacional RelacionalEl DBA El SMBDOptimiOptimizador zador Estadísticas de los datosManejo de MemoriaResultado Resultado de la de la consulta consultaRestauraciónMotor de Motor de evaluación evaluaciónPlan de Plan de ejecución ejecuciónConcurrencia Base de datosDiccionario Datos Proc. Consultas Consultas Integridad SeguridadMarzo 2012•Optimización: desarrolla una estrategia de ejecución para obtener el resultado de la consulta, evaluando cientos de estrategias distintas basadas en el álgebra relacional, y sus operadores físicos, escogiendo alguna de las estrategias menos costosa (plan de ejecución) Administración de Base de Datos11 12. Procesamiento de consulta Expresión Expresión en Algebra en Algebra Relacional RelacionalEl DBA El SMBDOptimiOptimizador zador Estadísticas de los datosManejo de MemoriaResultado Resultado de la de la consulta consultaRestauraciónMotor de Motor de evaluación evaluaciónPlan de Plan de ejecución ejecuciónConcurrencia Base de datosDiccionario Datos Proc. Consultas Consultas Integridad SeguridadMarzo 2012•Motor de ejecución: recibe el plan de evaluación, lo ejecuta y devuelve la respuesta de la consulta. Administración de Base de Datos12 13. Algebra Relacional El DBA El SMBDSelect <lista de atributos> From <lista de tablas>Lenguaje de consulta de alto nivelWhere <condiciones>Manejo de MemoriaRestauraciónOperadores del Algebra RelacionalConcurrencia Diccionario DatosUnariosProc. Consultas Consultas Integridad SeguridadMarzo 2012Binarios• Proyección • Selección • Ordenación • • • • • •Lenguaje de consulta de bajo nivelUnión Intersección Producto cartesiano Reunión Natural Resta DivisiónAdministración de Base de Datos13 14. Algebra Relacional El DBA El SMBD Manejo de Memoria•PROYECCION – Define una vista que contiene un subconjunto vertical de R, extrayendo los valores de los atributos especificados y eliminando los duplicados. – Ejm:T 1 ← Π CI ,Sueldo ( Empleado)Restauración Concurrencia Diccionario Datos Proc. Consultas Consultas Integridad SeguridadMarzo 2012Administración de Base de Datos14 15. Algebra Relacional El DBA El SMBD Manejo de Memoria•PROYECCION – Define una vista que contiene un subconjunto vertical de R, extrayendo los valores de los atributos especificados y eliminando los duplicados. – Ejm:T 1 ← Π CI ,Sueldo ( Empleado)Restauración Concurrencia Diccionario Datos Proc. Consultas Consultas IntegridadSelect <lista de atributos>CINombreSueldoFrom <lista de tablas>123Andrea Rojas1500234Humberto Perez2400254Camilo Diaz1600Where <condiciones>SeguridadMarzo 2012Administración de Base de Datos15 16. Algebra Relacional El DBA El SMBD Manejo de MemoriaRestauración Concurrencia Diccionario Datos Proc. Consultas Consultas Integridad•SELECCIÓN – Define una vista que contiene todas las tuplas de R que satisfacen la condición especificada. – Ejm:T 1 ← σ Sueldo>1500 ( Empleado)Select <lista de atributos> Where <condiciones>CINombreSueldo123Andrea Rojas1500234Humberto Perez2400254From <lista de tablas>Camilo Diaz1600SeguridadMarzo 2012Administración de Base de Datos16 17. Algebra Relacional El DBA El SMBD Manejo de MemoriaRestauración Concurrencia Diccionario Datos•PRODUCTO CARTESIANO – Define una relación que es la concatenación de cada tupla de la relación R con cada tupla de la relación S. – RXSCI Select <lista de atributos> From <lista de tablas>CodBCodBDesc12311Malta234127 up2542Where <condiciones>Proc. Consultas Consultas Integridad SeguridadMarzo 2012Administración de Base de Datos17 18. Algebra Relacional El DBA El SMBD Manejo de MemoriaRestauración Concurrencia Diccionario Datos•PRODUCTO CARTESIANO – Define una relación que es la concatenación de cada tupla de la relación R con cada tupla de la relación S. – RXSCI Select <lista de atributos> From <lista de tablas> Where <condiciones>CodBCodBDesc12311Malta234127 up254 2R.CodB R.CIS.CodBDesc12311Malta23411MaltaIntegridad25421MaltaSeguridad123127 up234127 up254227 upProc. Consultas ConsultasMarzo 2012Administración de Base de Datos18 19. Algebra Relacional El DBA El SMBD Manejo de Memoria•REUNION NATURAL (JOIN) – Es una combinación entre dos relaciones donde se verifica la condición de igualdad sobre los atributos comunes entre ambas relaciones. Del resultado se elimina una de las dos apariciones de cada atributoCIProc. Consultas Consultas Integridad SeguridadMarzo 2012Where <condiciones> and T1.a1=t2.a1 and ….11Malta2341 R.CodB2 S.CodB254 1232 17 up Desc1Malta23411Malta25421Malta123From <lista de tablas>Desc127 up127 up254Diccionario DatosSelect <lista de atributos>CodB234ConcurrenciaCodB123Restauración227 upR.CIAdministración de Base de Datos19 20. Algebra Relacional El DBA El SMBD Manejo de Memoria•REUNION NATURAL (JOIN) – Es una combinación entre dos relaciones donde se verifica la condición de igualdad sobre los atributos comunes entre ambas relaciones. Del resultado se elimina una de las dos apariciones de cada atributoCICodBCodBDesc12311MaltaSelect <lista de atributos>234127 upFrom <lista de tablas>2542Restauración Concurrencia Diccionario Datos Proc. Consultas ConsultasWhere <condiciones> and T1.a1=t2.a1 and ….SeguridadMarzo 2012CodBDesc1231Malta2341Malta254IntegridadCI27 upAdministración de Base de Datos20 21. Árbol de ejecución El DBA El SMBD Manejo de MemoriaRestauración• •Representa una consulta en algebra relacional Es un árbol de orden 2 – Cada nodo interno representa una tabla vista o resultado intermedio producido por una operación – Cada hoja representa una tabla baseConcurrencia Diccionario Datos Proc. Consultas ConsultasCase BaseCase InductivoTOpIntegridad SeguridadP1 y P2 sub arbolesP1, , , X ÷, P2Opπ ρ OP1Op operador AR Marzo 2012Administración de Base de Datos21 22. Árbol de ejecución • El DBAEjemplo Π Apellido1, Nombre, Sueldo (σSueldo > c(Empleado Departamento))El SMBD Manejo de MemoriaRestauraciónT1 <-(EmpleadoDepartamento)Ejecutamos de adentro hacia afueraConcurrencia Diccionario Datos Proc. Consultas Consultas Integridad SeguridadMarzo 2012EmpleadoAdministración de Base de DatosDeparta mento22 23. Árbol de ejecución • El DBAEjemplo Π Apellido1, Nombre, Sueldo (σSueldo > c(Empleado Departamento))El SMBD Manejo de MemoriaRestauraciónT1 <-(Empleado Concurrencia Diccionario DatosT2 <- σSueldo > cDepartamento)(T1)σSueldo > cProc. Consultas Consultas Integridad SeguridadMarzo 2012EmpleadoAdministración de Base de DatosDeparta mento23 24. Árbol de ejecución • El DBAEjemplo Π Apellido1, Nombre, Sueldo (σSueldo > c(Empleado Departamento))El SMBDΠManejo de MemoriaApellido1, Nombre, SueldoRestauraciónT1 <-(Empleado ConcurrenciaT2 <- σDiccionario Datos Proc. Consultas ConsultasTr <- ΠSueldo > cDepartamento)(T1)Apellido1, Nombre, SueldoσSueldo > c(T2)Integridad SeguridadMarzo 2012EmpleadoAdministración de Base de DatosDeparta mento24 25. Árbol lineal izquierdo El DBA•Es un árbol de ejecución donde en cada nodo binario el hijo derecho es una tabla•Arbol canónico: Es un árbol lineal izquierdo donde cada nodo binario corresponde a un producto cartesiano, la selección es sobre toda la condición y la proyección sobre todos los atributosEl SMBD Manejo de MemoriaRestauración Concurrencia Diccionario Datos Proc. Consultas Consultas Integridad SeguridadMarzo 2012Nota: es el mas rápido de construir pero el más costoso Administración de Base de Datos 26. Árbol lineal izquierdo El DBA•Es un árbol de ejecución donde en cada nodo binario el hijo derecho es una tabla•Arbol canónico: Es un árbol lineal izquierdo donde cada nodo binario corresponde a un producto cartesiano, la selección es sobre toda la condición y la proyección sobre todos los atributosEl SMBD Manejo de MemoriaRestauración Concurrencia Diccionario Datos Proc. Consultas ConsultasSELECT <Lista Atributos> FROM T1, T2, … Tn WHERE <Condición>Integridad SeguridadMarzo 2012Nota: es el mas rápido de construir pero el más costoso Administración de Base de Datos 27. Árbol lineal izquierdo El DBA•Es un árbol de ejecución donde en cada nodo binario el hijo derecho es una tabla•Arbol canónico: Es un árbol lineal izquierdo donde cada nodo binario corresponde a un producto cartesiano, la selección es sobre toda la condición y la proyección sobre todos los atributosEl SMBD Manejo de MemoriaRestauración Concurrencia Diccionario Datos Proc. Consultas ConsultasSELECT <Lista Atributos> FROM T1, T2, … Tn WHERE <Condición>Integridad SeguridadMarzo 2012Nota: es el mas rápido de construir pero el más costoso Administración de Base de Datos 28. Árbol lineal izquierdo El DBA•Es un árbol de ejecución donde en cada nodo binario el hijo derecho es una tabla•Arbol canónico: Es un árbol lineal izquierdo donde cada nodo binario corresponde a un producto cartesiano, la selección es sobre toda la condición y la proyección sobre todos los atributosEl SMBD Manejo de MemoriaRestauración Concurrencia Diccionario Datos Proc. Consultas ConsultasSELECT <Lista Atributos> FROM T1, T2, … Tn WHERE <Condición>Integridad SeguridadMarzo 2012Nota: es el mas rápido de construir pero el más costoso Administración de Base de Datos 29. Árbol lineal izquierdo El DBA El SMBD Manejo de MemoriaRestauración Concurrencia Diccionario Datos Proc. Consultas ConsultasEjercicios Construya el árbol canónico de las sig. consultas SELECT CI, Nombre, CodMateria FROM Estudiante E, inscripcion I WHERE I.CodM = ‘6311’ and semestre=‘2-2011’ and E.CI = I.CI SELECT E.CI, E.Nombre, M.Nombre, I.semestre FROM Estudiante E, Inscripcion I, Materia M WHERE I.CodM = ‘6311’ and I.semestre=‘2-2011’ and E.CI = I.CI and M.CodM = I.CodMIntegridad SeguridadMarzo 2012Administración de Base de Datos 30. Ejercicio 1 El DBA El SMBDSELECT CI, Nombre, CodMateria FROM Estudiante E, inscripcion I WHERE I.CodM = ‘6311’ and semestre=‘2-2011’ and E.CI = I.CIManejo de MemoriaRestauración Concurrencia Diccionario Datos Proc. Consultas Consultas Integridad SeguridadMarzo 2012Administración de Base de Datos30 31. Ejercicio 2 El DBA• Tarea, envíenla por correoEl SMBD Manejo de MemoriaRestauración Concurrencia Diccionario Datos Proc. Consultas Consultas Integridad SeguridadMarzo 2012Administración de Base de Datos31 32. Expresiones equivalente El DBA El SMBD Manejo de MemoriaRestauración Concurrencia Diccionario Datos Proc. Consultas Consultas• Una expresión del AR es equivalente a otra, si el resultado es el mismo. • Sin embargo una expresión equivalente puede ser mas eficiente que otra en tiempo de respuesta. • Para hallar expresiones equivalentes se usan reglas o axiomas, los cuales vienen de la teoría de conjuntosIntegridad SeguridadMarzo 2012Administración de Base de Datos 33. Axiomas del Algebra Relacional El DBA El SMBD Manejo de MemoriaRestauración Concurrencia Diccionario Datos Proc. Consultas Consultas Integridad SeguridadMarzo 20121. Cascada de selecciones 2. Conmutatividad de la selección 3. Cascada de proyecciones 4. Distributividad de la proyección y la selección 5. Conmutatividad del Join y el Producto Cartesiano 6. Distributividad de la selección con respecto al Join y al producto cartesiano 7. Distributividad de la proyección con respecto al Join y al producto cartesiano Administración de Base de Datos 34. Axiomas del Algebra Relacional El DBA El SMBD Manejo de MemoriaRestauración Concurrencia Diccionario Datos Proc. Consultas Consultas8. Conmutatividad de la unión y la intersección 9. Asociatividad de la union, la intersección, y el producto cartesiano 10. Distributividad de la selección con respecto a la Unión y la Intersección 11. Distributividad de la proyección con respecto a la Unión y la Intersección 12. Conversión del Producto Cartesiano en JoinIntegridad SeguridadMarzo 2012Administración de Base de Datos 35. Axiomas del Algebra Relacional El DBA El SMBD1. Cascada de seleccionesσ c1 and c 2 and...and cn ( R ) ≡ σ c1 (σ c 2 (...σ cn ( R )...))Manejo de MemoriaRestauraciónDonde c1, c2, … cn son condiciones booleanasConcurrencia Diccionario Datos Proc. Consultas Consultas Integridad SeguridadMarzo 2012Administración de Base de Datos 36. Axiomas del Algebra Relacional El DBA El SMBD1. Cascada de seleccionesσ c1 and c 2 and...and cn ( R ) ≡ σ c1 (σ c 2 (...σ cn ( R )...))Manejo de MemoriaRestauraciónDonde c1, c2, … cn son condiciones booleanasConcurrencia Diccionario Datosσc1 and c2σc3and c3Proc. Consultas Consultasσc2σc1Integridad SeguridadMarzo 2012Administración de Base de Datos 37. Axiomas del Algebra Relacionalσ c1 (σ c 2 ( R )) ≡ σ c 2 (σ c1 ( R))El DBA El SMBDσ codB =1Manejo de MemoriaRestauración Concurrencia Diccionario Datosσ CI =123CICodBCICodBCICodB123112311231234123411232Integridad SeguridadMarzo 2012σ CI =123σ codB =1CICodBCICodB12311231123Proc. Consultas Consultas2Administración de Base de Datos 38. Axiomas del Algebra Relacional El DBA El SMBD Manejo de Memoria2. Conmutatividad de la selecciónσ c1 (σ c 2 ( R )) ≡ σ c 2 (σ c1 ( R))Restauración Concurrencia Diccionario Datos Proc. Consultas Consultasσ σc2c1σ σc1c2Integridad SeguridadMarzo 2012Administración de Base de Datos 39. Axiomas del Algebra Relacional El DBA3. Cascada de proyeccionesEl SMBD Manejo de Memoria∏ CI ,CodBRestauración Concurrencia Diccionario Datos Proc. Consultas ConsultasCICodBDescCICodBCI1231Malta12311232341Malta234123425427 up2542254Integridad SeguridadMarzo 2012∏ CIAdministración de Base de Datos 40. Axiomas del Algebra Relacional El DBA3. Cascada de proyeccionesEl SMBD Manejo de MemoriaRestauración Concurrencia Diccionario Datos Proc. Consultas Consultas Integridad∏A1 ∏A1..An -1∏A1∏A1..AnSeguridadMarzo 2012Administración de Base de Datos 41. Axiomas del Algebra Relacional El DBA4. Distributividad de la proyección y la selecciónEl SMBD Manejo de MemoriaRestauración ConcurrenciaCICodBDiccionario Datos1231Proc. Consultas Consultas2341Integridad1232SeguridadMarzo 2012Administración de Base de Datos 42. Axiomas del Algebra Relacional El DBA4. Distributividad de la proyección y la selecciónEl SMBD Manejo de Memoriaσ codB =1Restauración ConcurrenciaCICodBDiccionario Datos1231Proc. Consultas Consultas234 123CodB123123411IntegridadCI2SeguridadMarzo 2012Administración de Base de Datos∏ CodBCodB 1 1 43. Axiomas del Algebra Relacional El DBA4. Distributividad de la proyección y la selecciónEl SMBD Manejo de Memoriaσ codB =1Restauración ConcurrenciaCIDiccionario Datos1231Proc. Consultas Consultas2341Integridad1232Seguridad∏ CodBCodB1231234CodBCI1CodBCodB 1 1σ codB =1CodB11112 Marzo 2012∏ CodBAdministración de Base de Datos 44. Axiomas del Algebra Relacional El DBA4. Distributividad de la proyección y la selecciónEl SMBD Manejo de MemoriaRestauración Concurrencia Diccionario Datos Proc. Consultas Consultas∏A1..An σcσ∏A1..AnIntegridad SeguridadMarzo 2012cAdministración de Base de Datos 45. Próxima clase El DBAPróxima clase •Transformación del árbol canónico (Axiomas del Algebra Relacional) Continuación•Técnicas de optimizaciónRestauración•Factor de SelectividadConcurrencia•Costos de los operadoresEl SMBD Manejo de MemoriaDiccionario Datos Proc. Consultas Consultas Integridad SeguridadMarzo 2012Administración de Base de Datos
Description
Presentacion de la clase de procesamiento de consultas de la materia Administracion de Base de datos - Computacion - UCV