Fundamentos de Bases de Datos - Notas de referencia

CAPÍTULO 1

[AH87] Abiteboul S., Hull R. IFO: A Formal Semantic Database Model. ACM Transaction on Database Systems (12)4: 525-565, 1987.

https://doi.org/10.1145/32204.32205

[Codd80] E. F. Codd. Data Models in Database Management. ACM SIGMOD Record (11)2:112-114, 1981.

https://doi.org/10.1145/960126.806891

[Codd82] The 1981 Turing Award Lecture: Relational database: A practical foundation for productivity. Communication of the ACM 25(2): 109-117, 1982.

https://doi.org/10.1145/358396.358400

[DBFTG86] Thomas Burns, Elizabeth N. Fong, David Jefferson, Richard Knox, Leo Mark, Christopher Reedy, Louis Reich, Nick Roussopoulos, Walter Truszkowski. Reference Model for DBMS Standarization, Database Architecture Framework Task Group (DAFTG). SIGMOD Record (15)1: 19-58, 1986.

https://doi.org/10.1145/16342.16343

[HMc78] Hammer M., McLeod D. The semantic data model: a modeling mechanism for database applications. Proceedings of the 1978 ACM SIGMOD International Conference on Management of Data Austin, Texas pp: 26 - 36, 1978.

[HMc81] Hammer M., McLeod D. Database Description with SDM: A Semantic Database Model. ACM Transaction on Database Systems (6)3: 351-386, 1981.

https://doi.org/10.1145/319587.319588

[HK88] Hull R., King R. Semantic Database Modeling: Survey, Applications and Research Issues. ACM Computing Surveys (19)3: 202-260, 1987.

[MS80] McLeod Dennis, Smith Miles John. Abstractions in Databases. SIGMOD Record 11(2): 19-25, 1981.

https://doi.org/10.1145/960126.806871

[SKS96] Silberschatz A., Korth H., Sudarshan S. Data Models. ACM Computing Surveys (28)1: 105-108, 1996.

https://doi.org/10.1145/234313.234360

Bibliografía básica anotada

[Codd80] E. F. Codd. Data Models in Database Management. ACM SIGMOD Record (11)2:112-114, 1981.

https://doi.org/10.1145/960126.806891

El autor define un modelo de datos en términos de tres componentes: estructuras, operadores y reglas de integridad. Propone, también, varios usos que se le puede dar a un modelo de datos y discute algunos de los conceptos que han generado, en alguna medida, malentendidos en la comunidad de bases de datos.

[Codd82] The 1981 Turing Award Lecture: Relational database: A practical foundation for productivity. Communication of the ACM 25(2): 109-117, 1981.

https://doi.org/10.1145/358396.358400

A partir de tres objetivos fundamentales: independencia de datos, comunicabilidad y procesamiento de conjuntos se define un sistema de gestión de bases de datos relacional. Se ofrecen argumentos para sustentar la afirmación de que los SGBD mejoran la productividad tanto de los usuarios como de los programadores. Se ilustran distintos tipos de sistemas relacionales.

[HMc81] Hammer M., McLeod D. Database Description with SDM: A Semantic Database Model. ACM Transaction on Database Systems (6)3: 351-386, 1981.

https://doi.org/10.1145/319587.319588

Los autores se proponen diseñar un modelo de base de datos de alto nivel que le permita al diseñador incorporar de manera natural y directa más semántica al esquema de base de datos. Se describe SDM, un formalismo para estructurar y describir una base de datos de manera que el esquema pueda "capturar más significado". Se pretende, principalmente, que SDM sirva como un mecanismo de especificación formal para describir el significado de la base de datos.

CAPÍTULO 2

[AHV95] Abiteboul S., Hull R., Vianu V. Foundations of Databases. Addison-Wesley Publishing Company, 1995.

[AU79] Aho A. V., Ullman J.D. Universality of Data Retrieval Languages. Proceedings of the 6th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages. pp: 110-119, 1979.

[AV92] Abiteboul S., Vianu V. Expressive Power of Query Languages. Reporte Técnico 1587, INRIA. Disponible en http://hal.inria.fr/docs/00/07/49/73/PDF/RR-1587.pdf.

[ChaHa80] Chandra A. K., Harel D. Computable Queries for Relational Data Bases. Journal of Computer and System Science (21): 156-178, 1980.

https://doi.org/10.1016/0022-0000(80)90032-X

[ChaMer77] A. K. Chandra and P. M. Merlin. Optimal implementation on conjunctive queries in relational data bases. In Proc. ACM SIGACT Symposium. on the Theory of Computing pp: 77-90, 1977.

[Codd70] Codd E. F. A Relational Model of data for Large shared data banks. Communication of the ACM, 13(6): 377-387, 1970.

https://doi.org/10.1145/362384.362685

[Codd72] Codd E. F. Relational Completeness of Data Base Sublanguages. In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California. Disponible en http://www.cs.berkeley.edu/~christos/classics/Codd72a.pdf.

[Codd79] Codd E. F. Extending the database relational model to capture more meaning. ACM Trans. on Database Systems 4(4):397-434, 1979.

https://doi.org/10.1145/320107.320109

[Date81] Date C. J. A Formal Definition of the Relational Model. ACM SIGMOD Record(13)1: 18 - 29 , 1982.

https://doi.org/10.1145/984514.984515

[SS75] Schmid H.A., Swenson J.R. On the Semantics of the Relational Data Model. Proceedings of the 1975 ACM SIGMOD International Conference on Management of Data, San Jose, California, pp:211-223, 1975 .

Bibliografía básica anotada

[Codd70] Codd E. F. A relational model of data for large shared data banks. Communications of the ACM, 13(6):377-387, 1970.

https://doi.org/10.1145/362384.362685

Este artículo introduce el modelo de datos relacional en el cual la relación es la estructura de datos y el álgebra relacional el lenguaje de consulta. Se introducen también conceptos de llave primaria, llave foránea y forma normal. El álgebracomo lenguaje de consulta se describe a partir de cuatro operaciones (permutación, proyección, join, composición y restricción) y su aplicación, de acuerdo con elautor, garantiza independencia entre los datos almacenados y los programas que acceden a éstos. Se introducen también conceptos de derivabilidad, redundancia y consistencia de relaciones. Por otra parte, se propone pero no se describe, el cálculo de predicados de primer orden como un lenguaje para recuperar datos a partir de relaciones normalizadas.

[Codd72] Codd E.F. Relational Completeness of Data Base Sublanguages. In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California. Disponible en http://www.cs.berkeley.edu/~christos/classics/Codd72a.pdf.

El artículo introduce el álgebra y el cálculo relacionales. Se define un sublenguaje de datos como la componente de un lenguaje encargada de recuperar y almacenar datos. Este sublenguaje puede estar inmerso en un lenguaje de programación de propósito general o estar aislado. En esta última forma es un lenguaje de consulta.

Uno de los resultados más importantes que se presentan en el articulo es un algoritmo para traducir una expresión escrita utilizando el sublenguaje de datos ALPHA en otra equivalente del álgebra relacional.

Se muestra, en el artículo, que el álgebra relacional definida es relacionalmente completa. Un álgebra es relacionalmente completa "si dada cualquier colección finita de relaciones R ,R ,...,RN 1 2 en forma normal simple, las expresiones del álgebra permiten definir cualquier relación definible a partir de N R ,R ,...,R 1 2 por medio de expresiones ALPHA".

[Codd79] Codd E. F. Extending the Database Relational Model to Capture More Meaning. ACM Transaction on Database Systems (4)4: 397-434, 1979.

https://doi.org/10.1145/320107.320109

Con el propósito de dotar de más significado el modelo relacional se introducen, en este artículo, los conceptos de semántica atómica y molecular. Un esquema de clasificación en entidades, propiedades y asociaciones se presenta. Se propone una definición de base de datos completamente relacional apoyada en el cumplimiento de ciertas características.

El autor define una base de datos relacional, relaciones básicas y derivadas, llaves primarias y dominios primarios. Cualquier inserción, actualización o eliminación aplicada a relaciones básicas debe satisface las reglas de integridad de entidad e integridad referencial.

Se revisa de manera detallada el álgebra relacional que excluye valores nulos y tratando, por supuesto, las relaciones como conjuntos. Los valores nulos se tratan después en el artículo significando "valor existente pero desconocido de momento".Para recuperación de datos, se adopta una lógica de tres valores.

Lo que el autor denomina Modelo Relacional de Tasmania (RM/T) se introduce a partir de tipos de entidades, asociaciones y conceptos de agregación, entre otros.

[Chandra88] Chandra A.K. Theory of database queries. In Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 1-9, 1988.

El autor analiza una consulta a una base de datos desde el álgebra y la lógica de primer orden haciendo un importante énfasis en el poder expresivo de los lenguajes de consulta. A partir del reconocimiento de las limitaciones de la lógica de primer orden, y por tanto del álgebra, para expresar consultas (i.e. cierre transitivo), se revisa el concepto de consulta computable. A partir de este concepto se analiza la forma de construir un lenguaje que pueda expresar cualquier consulta computable.

[Date81] Date C. J. A Formal Definition of the Relational Model. ACM SIGMOD Record(13)1: 18 - 29, 1982.

https://doi.org/10.1145/984514.984515

Mediante un conjunto de reglas de producción se define una base de datos relacional. Los constructores que se introducen se revisan de manera detallada (i.e. (relational-database), (domain),(relation),(attribute)). Se definen también, mediante reglas de producción operaciones relacionales. Finalmente, se introducen dos reglas de integridad: de entidad y referencial.

[SS75] Schmid H. A., Swenson J. R. On the Semantics of the Relational Data Model. Proceedings of the 1975 ACM SIGMOD International Conference on Management of data, San Jose, California, pp. 211-223, 1975.

Una de las fortalezas del modelo relacional es que las relaciones, atributos y operaciones están matemáticamente bien definidas. Sin embargo, no se ofrecen elementos sobre la forma de modelar mediante relaciones el mundo real. Este artículo presenta un modelo semántico que se aplica a la teoría relacional, solucionando algunos problemas asociados con la dificultad de expresar conocimiento sobre el mundo real mediante dependencias funcionales. El modelo propuesto está basado en tipos de objetos y sus relaciones y ofrece una forma de darle semántica a la normalización de relaciones.

CAPÍTULO 3

[ABC+76] Astrahan M. M., Blasgen M. W., Chamberlin D. D., Eswaran K. P., Gray J. N., Griffiths P. P., King W. F., Lorie R. A., McJones P. R., Mehl J. W., Putzolu G. R., Traiger I. L., Wade B. W., Watson V. System R: relational approach to database management. ACM Transaction on Database Systems(1)2: 96-137, 1976.

https://doi.org/10.1145/320455.320457

[ASU79] Aho A. V., Sagiv Y., Ullman J. D. Efficient Optimization of a Class of Relational Expressions. ACM Transaction on Database Systems (4)4: 435-454, 197.

[CAE+85] Chamberlin D. D., Astrahan M. M., Eswaran K. P., Griffiths P. P., Lorie R. A., Mehl J. W., Reisner P., Wade B. W. SEQUEL2: A Unified Approach to Data Definition, Manipulation and Control. IBM J. RES. DEVELOP., 1985, Disponible en http://www.research.ibm.com/journal/rd/206/ibmrd2006E.pdf.

[CGM90] Chakravarthy U. S., Grant J., Minker J. Logic-Based Approach to Semantic Query Optimization. ACM Transaction on Database Systems (15)2: 162-207, 1990.

[ChaMer77] A. K. Chandra and P. M. Merlin. Optimal implementation on conjunctive queries in relational data bases. In Proceeding of ACM SIGACT Symposium on the Theory of Computing, pp. 77-90, 1977.

[Chaudhuri98] Chaudhuri S. An Overview of Query Optimization in Relational Systems. In Proceedings of PODS 98, pp. 34-43 Seattle USA, 1998.

[ChaudVar93] Chaudhuri S., Vardi M. Optimization of Real Conjunctive Queries. Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Washington, D.C. HPL-9326, 1993.

[Graefe93] Graefe G. Query Evaluation Techniques for Large Databases. ACM Computing Surveys (24)2: 73-169, June 1993. Disponible en http://infolab.stanford.edu/~widom/cs346/graefe.pdf.

[Ioannidis96] Ioannidis Yannis. Query Optimization. Disponible en http://infolab.stanford.edu/~widom/cs346/ioannidis.pdf.

[JK84] Jarke M., Koch J. Query Optimization in Database Systems. ACM Computing Surveys (16)2: 111-152, 1984.

https://doi.org/10.1145/356924.356928

[KS87] Kumar A., Stonebraker M. The Effect of Join Selectives on Optimal Nesting Order. Sigmod Record (16)1: 28-41, 1987.

https://doi.org/10.1145/24820.24822

[MCS88] Mannino M., Chu P., Sager T. Statistical Profile Estimation in Database Systems. ACM Computing Survey (20)3: 191-221, 1988.

https://doi.org/10.1145/62061.62063

[NPS91] Negri M., Pelagatti G., Sbatella L. Formal Semantics of SQL queries. ACM Transactions on Database Systems(16)3: 523-53, 1991.

[SACLP79] Selinger P. G., Astrahan M. M., Chamberlin D. D., Lorie R. A., Price T. G. Access Path Selection in a Relational Database Management System. Proceedings of ACM SIGMOD International Conference on Management of Data, pp. 23-34, 1979.

[Zloof75] Zloop Moshé. Query-by-Example: The Invocation and Definition of Tables and Forms. Proceedings of the 1st International Conference on Very Large Data Bases, Massachusetts, pp. 1-24, 1975.

Bibliografía básica anotada

[ASU79] Aho A.V., Sagiv Y., Ullman J.D. Efficient Optimization of a Class of Relational Expressions. ACM Transaction on Database Systems (4)4: 435-454, 1979.

Optimizar una consulta implica encontrar una expresión equivalente a esta que sea más barata de implementar computacionalmente. En este artículo se examina la dificultad computacional para determinar si dos consultas son equivalentes. El análisis se restringe a expresiones SPJ que generalmente cubre un conjunto amplio de consultas comunes.

Las transformaciones que se hacen a una expresión para convertirla en otra equivalente se basan en una matriz llamada por los autores un tableau. Un tableau es una matriz en la cual las columnas corresponden a los atributos del universo en un orden fijo.

[ChaudVar93] Chaudhuri S., Vardi M. Optimization of Real Conjunctive Queries. Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Washington, D.C., HPL-9326, 1993.

El artículo examina las técnicas de optimización de consultas conjuntivas bajo una semántica de multiconjunto (bag-theoretic setting). Se introduce la equivalencia de consultas bajo esta semántica como base para encontrar expresiones equivalentes a una consulta que sean menos costosas computacionalmente.

[Chaudhuri98] Chaudhuri S. An Overview of Query Optimization in Relational Systems. In Proceedings of PODS 98, pp. 34-43, Seattle USA, 1998.

Se presenta en enfoque de optimización de System-R. El proceso de optimización se analiza considerándolo como un problema de búsqueda en un espacio de estados. El estudio hace énfasis en consultas conjuntivas (SPJ). El espacio de búsqueda para el optimizador son árboles de operadores que representan secuencias lineales de joins y que son equivalentes por las propiedades conmutativas y asociativas del join. El operador join se puede implementar, por ejemplo, como un nested-loop o como un sort-merge. Para cada plan parcial o completo se asigna un costo estimado mediante un modelo de costo. El modelo se apoya en estadísticas sobre las relaciones y los índices (número de valores distintos por atributo, número de páginas de datos por relación, etc.), en fórmulas para estimar el poder de selectividad de los predicados y en fórmulas para estimar costos de CPU e I/O de la ejecución de la consulta.

[CGM90] Chakravarthy U.S., Grant J., Minker J. Logic-Based Approach to Semantic Query Optimization. ACM Transaction on Database Systems (15)2: 162-207, 1990.

La gran mayoría de las propuestas de optimización de consultas se ha basado en el uso de propiedades de los operadores y en diferentes implementaciones de éstos, llamado por el autor optimización sintáctica. El proceso de optimización se vería positivamente mejorado si se utilizara información semántica sobre el dominio de las aplicaciones produciendo optimización semántica de consultas. En este artículo se proponen técnicas de optimización que tienen en cuenta conocimiento semántico.

La optimización semántica que se propone se aplica a bases de datos deductivas que también se puede aplicar a bases de datos relacionales, de acuerdo con los autores.

Una base de datos deductiva consta de una base de hechos (EDB, extensional database), reglas deductivas o axiomas (IDB, intensional database), un conjunto de restricciones de integridad (IC, integrity constraint) y la regla de inferencia SLDNF (Linear resolution for definite Horn clauses with negation as failure). Todas

las cláusulas son de rango restringido. Una consulta es una cláusula objetivoo meta.

Una respuesta Q a una consulta ←Q(x1,..., xn ) es cualquier tupla a1, a2 ,..., an , tal que Q a1, a2 ,..., an se puede probar a partir de la base de datos.

El enfoque de optimización propuesto consta de dos fases: modificación de la consulta usando la base de datos intensional y optimización del resultado aplicando técnicas convencionales.

[Ioannidis96] Ioannidis Yannis. Query Optimization. Disponible en http://infolab.stanford.edu/~widom/cs346/ioannidis.pdf.

Se centra en optimización de consultas conjuntivas conocidas también como consultas Horn no recursivas o consultas select-project-join, SPJ, en un sistema de gestión de base de datos centralizado. El recorrido de una consulta incluye su paso por varios módulos del SGBD como en la Figura 3.9.

Una abstracción del proceso de optimización se presenta integrada por dos etapas, tal y como se muestra en la Figura 3.10: rewriting y planning. El rewriter transforma la consulta de entrada para producir otras equivalentes y más eficientes.

Algunas de las transformaciones que se aplican a la consulta son, entre otras, aplanar las consultas anidadas y reemplazar las vistas por su definición.

Por su parte, el planner analiza todos los planes de ejecución posibles y escoge el más barato. Para hacer esto necesita una estrategia de búsqueda que le permita examinar el espacio de planes. Junto con los módulos algebraic space y methodstructure space, se determina el plan de más bajo costo con base en el costo de los planes que el módulo de planner entrega. Estos costos los calculan los módulos Cost Model y Size-Distribution Estimator.

[JK84] Jarke M., Koch J. Query Optimization in Database Systems. ACM Computing Surveys (16)2: 111-152, 1984.

https://doi.org/10.1145/356924.356928

[SACLP79] Selinger P. G., Astrahan M. M., Chamberlin D. D., Lorie R. A., Price T. G. Access Path Selection in a Relational Database Management System. Proceedings of ACM SIGMOD Internacional Conference on Management of Data, pp. 23-34, 1979.

El artículo describe la forma como el optimizador de System R, SGBD relacional, referente en temas de optimización de consultas, escoge caminos de acceso para consultas simples y complejas.

Después de que una consulta SQL ha pasado por las etapas de parsing y el optimizador dispone de estadísticas sobre las relaciones referenciadas en la consulta y los caminos de acceso existentes, éste debe seleccionar uno de estos últimos.

El artículo detalla la estrategia utilizada por System R para calcular el costo de cada plan de acceso tanto para consultas simples como complejas. Se ofrecen también fórmulas para estimar costos de acceso a la o las relaciones referenciadas que dependen de si la relaciones tiene o no índices de acceso definidos o si está clusterizada. Se describe también la forma de seleccionar caminos de acceso para operaciones de join, cuyo costo depende del orden en el cual se tomen las relaciones que aparecen en la consulta.

CAPÍTULO 4

[ABU79] Aho A. V., Beeri C., Ullman J. D. The Theory of Joins in Relational Databases. ACM Transaction on Database Systems (4)3: 297-314, 1979.

https://doi.org/10.1145/320083.320091

[AH87] Abiteboul S., Hull R. IFO: A Formal Semantic Database Model. ACM Transaction on Database Systems (12)4: 525-565, 1987.

https://doi.org/10.1145/32204.32205

[Armstrong74] Armstrong W.W. Dependency Structures of Database Relationships. Proceedings of IFIP'74, pp. 580-583, 1974.

[Bernstein76] Bernstein P. A. Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Transaction on Database Systems (1)4: 277-298, 1976.

[BB79] Beeri C., Bernstein P. Computational Problems related to the design of Normal Form Relational Schemas. ACM Transaction on Database Systems (4)1: 30-59, 1979.

[BFH77] Beeri C., Fagin R., Howard J.H. A Complete Axiomatization for Functional and Multivalued Dependencias in Database Relations. Proceedings on 1977 ACM SIGMOD International Conference on Management of Data: 47-61, 1977.

[BST75] Bernstein P. A., Swenson J. R., Tsichritzis D. C. A Unified Approach to Functional Dependencies and Relations. Proceedings on 1975 ACM SIGMOD International Conference on Management of Data, pp. 237-245, 1975.

[CFP82] Casanova M. A., Fagin R., Papadimitriou C. H. Inclusion Dependencies and their interaction with functional dependencies. Proceedings of the 1st ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, pp. 171-176, 1982.

[Chen76] Chen P. P. The Entity-Relationship Model- Towards a Unified View of Data. ACM Transactions on Database Systems (TODS) (1)1: 9-36, 1976.

[Codd70] Codd E. F. A relational model of data for large shared data banks. Communications of the ACM, 13(6):377-387, 1970.

https://doi.org/10.1145/362384.362685

[Codd71] Codd E. F. Further Normalization of the Data Base Relational Model. IBM Research Report, San Jose, California RJ909: (1971). In ACM SIGMOD Anthology Volume 5, Issue 1, 1971.

[Codd75] Codd E. F. Recent Investigation in Relational Database Systems. ACM Pacific 1975, pp. 15-20. In ACM SIGMOD Anthology Volume 5, Issue 1.

[Codd79] Codd E. F. Extending the database relational model to capture more meaning. ACM Trans. on Database Systems 4(4):397-434, 1979.

https://doi.org/10.1145/320107.320109

[Codd87] Codd E. F. More Commentary on Missing Information in Relational Databases (Applicable and Inapplicable information). SIGMOD Record (16)1:42-50, 1987.

https://doi.org/10.1145/24820.24823

[Codd90] Codd E. F. The Relational Model for Database Management: Version 2. Addison-Wesley Longman Publishing Co, Inc., 1990.

[Delobel78] Delobel C. Normalization and Hierarchical Dependencies in the Relational Data Model. ACM Transaction on Database Systems (3)3: 201-222, 1978.

https://doi.org/10.1145/320263.320271

[DF92] Date C. J., Fagin R. Simple Conditions for Guaranteeing Higher Normal Forms in Relational Databases. ACM Transaction on Database Systems (17)3:465-476, 1992.

[Fagin77] Fagin R. Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Transaction on Database Systems (2)3: 262-278, 1977.

https://doi.org/10.1145/320557.320571

[Fagin77a] The decomposition versus synthetic approach to relational database design. Proceedings of VLDB77, pp. 441-446, 1977.

[Fagin79] Fagin R. Normal Forms and relational database operators. SIGMOD' 79, Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, Boston Massachusetts, pp. 153-160, 1979.

[Kent79] Kent W.. Limitations of Record-Based Information Models. ACM Transaction on Database Systems (4)1: 107-131, 1979.

https://doi.org/10.1145/320064.320070

[HMc78] Hammer M., McLeod D. The semantic data model: a modelling mechanism for database applications. Proceedings of the 1978 ACM SIGMOD International Conference on Management of Data Austin, Texas pp. 26-36, 1978.

[HMc81] Hammer M., McLeod D. Database Description with SDM: A Semantic Database Model. ACM Transaction on Database Systems (6)3: 351-386, 1981.

https://doi.org/10.1145/319587.319588

[HK88] Hull R., King R. Semantic Database Modeling: Survey, Applications and Research Issues. ACM Computing Surveys (19)3: 202-260, 1987.

[Maier88] Maier David. The Theory of Relational Databases. Computer Science Press, 1988. Disponible en http://web.cecs.pdx.edu/~maier/TheoryBook/TRD.html.

[MMS79] Maier D., Mendelzon A., Sagiv Y. Testing Implications of Data Dependencies. ACM Transaction on Database Systems (4)4: 455-469, 1979.

https://doi.org/10.1145/320107.320115

[Mitchell83] Mitchell John C. Inference Rules for Functional and Inclusion Dependencies. Proceedings of the 2nd ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, pp. 58-69, 1983.

[PM88] Peckhan J., Maryanski F. Semantic Data Models. ACM Computing Surveys (20)3: 153-189, 1988.

https://doi.org/10.1145/62061.62062

[Rubinson2007] Rubinson C. Nulls, three-valued Logic, and ambiguity in SQL:critiquing date's critique. ACM SIGMOD Record (36)4: 13-18, 2007.

https://doi.org/10.1145/1361348.1361350

[SKS96] Silberschatz A., Korth H., Sudarshan S. Data Models. ACM Computing Surveys (28)1: 105-108, 1996.

https://doi.org/10.1145/234313.234360

[Shen78] Shen Stewart N. T. A Semantic Approach in designing relational data bases. Proceedings of the ACM 1978 Annual Conference, pp. 596-601, 1978.

[SS75] Schmid H. A., Swenson J. R. On the semantic of relational data model. Proceedings of the 1975 ACM SIGMOD International Conference on Management of Data, San Jose, California, pp. 211-223, 1975.

[TYF86] Teorey T. J., Yang D. Fry J. A Logical Design Methodology for Relational Databases Using the Extended Entity-Relationship Model. Computing Surveys (18)2:197-222, 1986.

[TZ84] Tsur S. Zaniolo C. An implementation of GEM: supporting a semantic data model on a relational back-end. ACM SIGMOD Record (14)2: 286-295, 1984.

https://doi.org/10.1145/971697.602297

[Vassiliou79] Vassiliou Y. Null Values in Data Base Management: A Denotational Semantics Approach. Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, Boston, Mass., pp. 162-169, 1979.

[Zaniolo82] Zaniolo C. A New Normal Form for the Design of Relational Database Schema. ACM Transaction on Database Systems (7)3: 489-499, 1982.

https://doi.org/10.1145/319732.319749

Bibliografía básica anotada

[Armstrong74] Armstrong W.W. Dependency Structures of Database Relationships. Proceedings of IFIP'74, pp. 580-583, 1974.

Se propone un conjunto de reglas de inferencia o axiomas para derivar dependencias funcionales (restricciones) a partir de un conjunto de dependencias funcionales inicial. Se prueba que este conjunto de reglas es completo.

[BB79] Beeri C., Bernstein P. Computational Problems related to the design of Normal Form Relational Schemas. ACM Transaction on Database Systems (4)1: 30-59, 1979.

El artículo analiza varios problemas relacionados con dependencias funcionales y diseño de esquemas.

En relación con la derivación de dependencias funcionales a partir de un conjunto de dependencias, se analiza el inconveniente de ser lineal, es decir, que pueden existir varias derivaciones de una df que solo difieran en el orden de aplicación de las reglas. Adicionalmente, en una derivación se pueden, por una parte, aplicar reglas que son redundantes y por otra, aplicar reglas necesarias formalmente (reflexividad y aumentatividad), pero que intuitivamente no agregan información nueva. Para facilitar la manipulación de dependencias funcionales se introduce, en el artículo, un árbol de derivación que, de acuerdo con los autores, elimina estos inconvenientes.

Con respecto al diseño de esquemas en 3FN, a pesar de que es posible construirlos algorítmicamente con base en dependencias funcionales, no es posible extenderlos para alcanzar esquema en FNBC. Varias razones se presentan:

No todo conjunto de dependencias funcionales se puede representar mediante un esquema relacional en FNBC.

Es computacionalmente difícil (NP-hard) determinar si un esquema relacional representando un conjunto de dependencias funcionales está en FNBC.

Es computacionalmente muy difícil determinar si un conjunto de dependencias funcionales dado se puede representar mediante un esquema FNBC.

Se muestra que los problemas de determinar si una relación en 3FN está en FNBC y el de encontrar llaves, asociados con diseño de esquemas, son NP-completos. Se proponen además algoritmos para el problema de pertenencia de una Dependencia funcional a un conjunto de dependencias (membership problem) y

para obtener esquemas relacionales a partir de un conjunto de dependencias.

[BFH77] Beeri C., Fagin R., Howard J.H. A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations. Proceedings on 1977 ACM SIGMOD International Conference on Management of Data, pp. 47-61, 1977.

En este articulo se presentan conjuntos de reglas de inferencia aplicables a conjuntos de dependencias funcionales, multivaluadas y combinadas. Los autores prueban que los conjuntos de reglas son completas para la familia de dependencias funcionales y multivaluadas.

[CFP82] Casanova M. A., Fagin R., Papadimitriou C. H. Inclusion dependencies and their interaction with functional dependencies. Proceedings of the 1st ACM SIGACT-SIGMOD Symposium on Principles of Database Systems: 171-176, 1982.

Se estudian las dependencias de inclusión (Ind) y su interacción con dependencias funcionales. En una dependencia de inclusión la proyección sobre m columnas de la relación R es un subconjunto de la proyección de m columnas de la relación S . Desde un punto de vista de diseño de bases de datos, las dependencias de inclusión permiten decidir selectivamente cuales datos deben estar duplicados y en cuales relaciones.

Una axiomatización y un procedimiento de decisión para Ind se presentan. Adicionalmente, se demuestra también que para un conjunto de dependencias Ind y fd no existe una axiomatización completa.

[DF92] Date C. J., Fagin R. Simple Conditions for Guaranteeing Higher Normal Forms in Relational Databases. ACM Transaction on Database Systems (17)3: 465-476, 1992.

Se introduce la forma normal DK/NF, domain-key normal form, basada en los conceptos de dominio y llave.

[Delobel78] Delobel Claude. Normalization and Hierarchical Dependencies in the Relational Data Model. ACM Transaction on Database Systems (3)3: 201-222, 1978.

Haciendo uso de las dependencias funcionales y multivaluadas se introduce un modelo de diseño lógico de bases de datos relacionales. Adicionalmente, se define una nueva dependencia denominada por el autor de descomposición jerárquica de primer orden (first-order hierarchical decomposition-FOHD) que se relaciona con una organización jerárquica de los datos.

A partir del concepto de descomposición de una relación se estudian las condiciones bajo las cuales una relación se puede descomponer y la relación que existe entre descomposición y dependencias (funcionales, multivaluadas y FOHD).

Una FOHD es una expresión denotada como X :Y_1 |Y_2 | ... |Yk , donde X,〖Y 〗_1,Y_2 ,...,Y_k son conjuntos disjuntos. Una relación R (X, Y_1,…, Y_2, Y_k W), donde X, Y_(1,) Y_2,….,Y_(k,) W son conjuntos disjuntos de atributos satisface la FOHD si para cada X -valor se tiene que: R [X, Y_1, Y_2,…., Y_K, W]= R[x, Y_1] ×R[x, Y_2] × ... ×R[x,Y_K].

En una FOHD X :Y_1 |Y_2 | ... |Y_K , X se denomina segmento raíz, Y_1 , Y_2 ,..., Y_K segmentos y el par (X, Y_I ) se denomina rama.

Algunas propiedades entre las dependencias funcionales, multivaluadas y FOHD también se estudian. Finalmente, se ilustran descomposiciones que se derivan de una relación original.

[Fagin77] Fagin Ronald. Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Transaction on Database Systems (2)3: 262-278, 1977.

Se estudian reglas de inferencia para dependencias funcionales y multivaluadas existentes en una relación. Se analizan conjuntos de reglas para los df, los mvd y para combinaciones de éstas. Se muestra además que el conjunto de reglas es completo para una familia de dependencias funcionales y multivaluadas.

[Fagin81] Fagin R. A Normal Form for Relational Databases That is based on Domains and Keys. ACM Transaction on Database Systems (6)3: 387-415, 1981.

https://doi.org/10.1145/319587.319592

Se define la forma normal Proyección-Unión (Projection-Join Normal Form PJ/NF), una forma normal en la cual sólo se permiten los operadores proyección y unión, y que es más restrictiva que la 4FN y que se corresponde con la 5FN.

[Maier88] Maier David. The Theory of Relational Databases. Computer Science Press, 1988. Disponible en http://web.cecs.pdx.edu/~maier/TheoryBook/TRD.html.

En relación con el razonamiento sobre dependencias se dedica, en este libro, el Capítulo 8 a la revisión del tableau como base para el chase, un mecanismo para razonar sobre dependencias. Un tableau se define como una tabla conteniendo variables tomadas de un conjunto V y cuyo esquema está conformado por nombres de atributos asignados a cada una de sus columnas. V está compuesto de variables distinguibles y no-distinguibles. El esquema R de un tableau se convierte en una plantilla del esquema R.

Mediante el chase es posible encontrar para un tableau y un conjunto de dependencias dado, otro tableau equivalente al tableau inicial que satisface el conjunto de dependencias.

[Zaniolo82] Zaniolo C. A New Normal Form for the Design of Relational Database Schema. ACM Transaction on Database Systems (7)3: 489-499, 1982.

https://doi.org/10.1145/319732.319749

Se aborda el problema de diseño de bases de datos en el marco del modelo relacional y de dependencias funcionales. Teniendo en cuenta algunos problemas y limitaciones de la 3FN y FNBC, el autor introduce una definición de la 3FN.

Mediante ejemplos se ilustran las limitaciones de la FNBC en relación con la 3FN. En particular, una de ellas es la existencia de algoritmo eficiente para obtener esquemas de relaciones en 3FN y no para el caso de la FNBC.

CAPÍTULO 5

[AB95] Abiteboul S., Beeri C. On the Power of Languages for the Manipulation of Complex Values. VLDB Journal (4)4:727-794,1995.

https://doi.org/10.1007/BF01354881

[ADMB+89] Atkinson M., DeWitt D., Maier D., Bancilhon F., Dittrich K., Zdonik S. The Object-Oriented Database System Manifesto. Proceeding First International Conference on Deductive and Object-Oriented Databases, Kyoto, Japan 1989. Morgan Kaufmann Series In Data Management Systems Building an object-oriented database system: the story of 02, pp.1-20.1989. Disponible en http://citeseer.ist.psu.edu/atkinson89objectoriented.html.

[AK90] Abiteboul S., Kanellakis P. Database Theory Column: Query Languages for Complex Object Databases. ACM SIGACT News (21)3: 9-18, 1990.

https://doi.org/10.1145/101368.101370

[Bancilhon88] Bancilhon F. Object-Oriented Database System. Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS'88, pp. 152-162, Austin, Texas, 1988.

[BAS04] Bahloul S. N., Amghar Y., Sayah M. A*: Álgebra for an Extended Object/ Relational Model. International Journal of Computer Science & Applications (I)II:76-95, 2004.

[BF94] Bancilhon F., Ferran G. ODMG-93: The Object Database Standard. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering (17):3-14, 1994.

[BOS91] Butterworth P., Otis A., Stein J. The Gemstone Object Database Management System. Communication of the ACM (34)10:64-77, 1991.

https://doi.org/10.1145/125223.125254

[CD86] Carey M.J., DeWitt D.J. The Architecture of the EXODUS extensible DBMS. Proceedings of 1986 International Workshop on Object-Oriented Data-base Systems, Pacific Grove,California, USA, pp. 52-65, 1986. ACM SIGMOD Anthology, Vol. 2, Issue 3.

[CD92] Cluet S., Delobel C. A General Framework for the Optimization of Object-Oriented Queries. ACM SIGMOD Record (21)2:383-392 , 1992.

https://doi.org/10.1145/141484.130341

[CDGH+88] Carey M. J., DeWitt D. J., Graefe G., Haight D. M., Richardson J. E., Schuh D. T., Shekita J. E., Vandenberg S. The EXODUS extensible DBMS Project: An Overview. Disponible en: http://pages.cs.wisc.edu/~dewitt/includes/oodbms/exodus88.pdf.

[CDLR89] Cluet S., Delobel C., Lécluse C., Richard P. Reloop, an Algebra Based Query Language for an Object-Oriented Database System. Proceedings of the First International Conference on Deductive and Object-Oriented Databases (DOOD'89), Kyoto Research Park, Kyoto, Japan, 1989, pp. 313-332.

[CH90] Carey M., Haas L. Extensible Database Management Systems. SIGMOD Record (19)4:54-60, 1990.

https://doi.org/10.1145/122058.122064

[CMCD94] Cheng J., Mattos N., Chamberlin D. G., DeMichiel L. Extending Relational Database technology for new applications. IBM System Journal(33)2:264-279, 1994. Disponible en http://www.research.ibm.com/journal/sj/332/ibmsj3302E.pdf.

[CDV88] Carey M, DeWitt D., Vandenberg S. A Data Model and Query Language for EXODUS. Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, pp. 413-423, Chicago, Illinois, 1988.

[CR86] Cattell R. G. G., Rogers T. R. Combining Object-oriented and Relational Model of Data. Proceedings on the 1986 international workshop on Object-oriented database systems Pacific Grove, pp. 212-213, California, United States, 1986.

[DD95] Darwen H., Date C.J. The Third Manifesto. ACM SIGMOD Record (24)1:39-49, 1995.

[Deux91] Deux O. et al. The O2 System. Communication of the ACM (34)10:34-48, 1991.

https://doi.org/10.1145/125223.125238

[DS89] Derrett N, Shan M. Rule-Based Query Optimization in IRIS. Proceedings of the 17th Conference on ACM Annual Computer Science Conference, CSC'89, pp. 78-86, 1989.

[EM99] Eisenberg A., Melton J. SQL:1999, formerly known as SQL3. SIGMOD Record(28)1, 1999. Disponible en http://www.sigmod.org/record/issues/9903/.

https://doi.org/10.1145/309844.310075

[EMK+04] Eisenberg A., Melton J, Kulkarni K., Michels J., Zemke F. SQL: 2003 has been published. SIGMOD Record (33)1:119-126, 2004.

https://doi.org/10.1145/974121.974142

[FeMa2001] Fegaras L., Maier D. Optimizing Object Queries Using and Effective Calculus. ACM Transaction on Database Systems (25)4: 457-516, 2000.

https://doi.org/10.1145/377674.377676

[Fong97] Fong J. Converting relational to object-oriented databases. ACM SIGMOD Record (26)1: 1997.

[Fong95] Fong Z. The Design and Implementation of the POSTGRES Query Optimizer. M.S. Report. University of California, Berkeley. Disponible en http://db.cs.berkeley.edu/papers/UCB-MS-zfong.pdf.

[Freytag87] Freytag J. C. A Rule-Based View of Query Optimization. ACM SIGMOD Record (16)3:173-180, 1987.

https://doi.org/10.1145/38714.38735

[GGT96] Gardarin G., Gruser J. R.,Tang Z. H. Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases. Proceedings of the 22nd VLDB Conference, Bombay, India, pp. 390-401, 1996.

[GD87] Graefe G., DeWitt D. The EXODUS Optimizer Generator. Department of Computer Science, University of Wisconsin. Disponible en http://www.seas.upenn.edu/~zives/03s/cis650/P160.PDF.

[GGMR00] Grant J., Gryz J., Minker J. Raschid L. Logic-Based Query Optimization for Object Databases. IEEE Transactions on Knowledge and Data Engineering (12)4:529-547, 2000.

[Grigoriev07] Grigoriev E. Why the formal relational data model can be considered as a basis of object-oriented systems. Disponible en http://arxiv.org/vc/arxiv/papers/0708/0708.0361v1.pdf.

[GS05] Sassi M., Grissa-Touzi A. Contribution to the Query Optimization in the Object-Oriented Databases. Proceedings of World Academy of Science, Engineering and Technology (6): 267-270, 2005. Disponible en http://www.waset.org/pwaset/v6/v6-64.pdf.

[HS91] Heuer A., Scholl M.H. Principles of Object-Oriented Query Languages. Disponible en http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.9060.

[IBMDB2] DB2. Disponible en http://www-306.ibm.com/software/data/db2/9/

[InformixDS] Informix Dynamic Server, IBM. Disponible en http://www-306.ibm.com/software/data/informix/ids/.

[JS82] Jaeschke G., Schek H.J. Remarks on the Algebra of Non First Normal Form Relations. Proceedings of the 1st ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, pp. 124-138, Los Angeles, California, 1982.

[Kabra99] Kabra N. Query Optimization for Object-Relational Database Systems. PhD Thesis, University of Wisconsin, Madison 1999. Disponible en http://pages.cs.wisc.edu/~navin/research/thesis.pdf.

[Kent79] Kent William. Limitations of Record-Based Information Models. ACM Transactions on Database Systems (4)1: 107-131, 1979.

https://doi.org/10.1145/320064.320070

[LG02] Lord C., Gupta S. The Evolution of Object-Relational Databases. Carnegie Mellon 45-872 Information Resources Management, 2002. Disponible en http://www.chrisandtrudi.com/Chris/Portfolio/ObjectOriented%20Database%20Survey.pdf

[LLPS91] Lohman G. M., Lindsay B., Pirahesh H., Schiefer K. B. Extensions to Starburst: Objects, types, functions, and rules. Communication of the ACM (34)10:94-109, 1991.

[LMSV+93] Leung T. W., Mitchell G., Subramanian B., Vance B., Vandenberg S. L., Zdonik S. B. The AQUA Data Model and Algebra. Technical Report CS-93-09, March 1993, Brown University. Disponible en http://www.cs.brown.edu/research/pubs/techreports/reports/CS-93-09.html.

[McClure97] McClure S. Object Database vs. Object-Relational Databases. International Data Corporation IDC Bulletin #14821E - August 1997. Disponible en http://www.geog.ubc.ca/courses/geog516/notes/ordbms.htm.

[MZD91] Mitchell G., Zdonik S., Dayal U. Object-Oriented Query Optimization: What's the problem? Technical Report CS91-41, Brown University. Disponible en http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.6094

[PBRV90] Premerlani W., Blaha M., Rumbaugh J.E., Varwig T. An Objectoriented Relational Database. Communications of the ACM (33)11: 99-109, 1990.

https://doi.org/10.1145/92755.92772

[Petrini07] Petrini J. Object-relational query processing. Disponible en http://user.it.uu.se/~torer/kurser/mdb/2007/TermPapers/JohanPetrini.pdf.

[RKS88] Roth M.A., Korth H.F., Silberschatz A. Extended Álgebra and Calculus for Nested Relational Databases. ACM Transaction on Database Systems (13)4: 389-417, 1988.

[RS93] Rich C., Scholl M. H. Query Optimization in an OODBMS. Computer Science Department, University of Ulm. Disponible en www.inf.uni-konstanz.de/dbis/publications/download/RS:BTW93.ps.gz

[SAC+79] Selinger P. G., Astrahan M. M., Chamberlin D. D., Lorie R. A., Price T.G. Access Path Selection in Relational Database Management System. Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, pp.:23-34 Boston, Massachusetts, 1979.

[SAH87] Stonebraker M., Anton J., Hanson E. Extending a Database Systems with Procedures, ACM Transaction on Database Systems (12)3:350-376, 1987. Disponible en http://citeseer.ist.psu.edu/11110.html.

https://doi.org/10.1145/27629.27631

[Scholl92] Scholl M. Extensions to the relational data model. In P. Loucopoulos and R. Zicari, editors, Conceptual Modeling, Databases and CASE: An Integrated View of Information Systems Development. Jhon Wiley & Sons, New York, 1992.

Disponible en http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.224

[SKLY95] Subieta K., Kambayashi Y., Leszczylowski J., Yokota K. A Critique of Object Algebras, 1995. Disponible en http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.9613.

[SKL95] Subieta K., Kambayashi Y., Leszczylowski J. Procedures in Object-Oriented Query Languages. Proceedings of 21th International Conference on Very Large Databases, pp. 182-193, 1995. Disponible en http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.2906.

[SKL95a] Subieta K., Kambayashi Y., Leszczylowski J. Towards an Integrated Query/Programming Language for Object Bases: a Broad Outlook. Disponible en http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.3888.

[SLR+] Scholl M.H., Laasch C., Rich C., Schek H.J., Tresch M. The COCOON Object Model. Technical Report No. 192, Department of Computer Science, ETH Zurich, 1992. Disponible en http://citeseer.ist.psu.edu/219515.html.

[SQL99] ANSI/ISO/IEC International Standard (IS). Database Language SQLPart 2: Foundation (SQL/Foundation), September 1999. Disponible en http://www.

ncb.ernet.in/education/modules/dbms/SQL99/ansi-iso-9075-2-1999.pdf.

[Stonebraker86] Stonebraker M. Inclusion of New Types in Relational Database Systems, Proceedings of the Second International Conference on Data Engineering, pp. 262-269, IEEE Computer Society 1986. Disponible en http://citeseer.ist.psu.edu/stonebraker86inclusion.html.

[SR86] Stonebraker M., Rowe L. The Design of POSTGRES. Proceedings of the 1986 ACM SIGMOD International Conference on Management of Data, pp.340 - 355, Washington, D.C., United States ,1986. Disponible en http://citeseer.ist.psu.edu/stonebraker86design.html.

[SRLG+94] Stonebraker M., Rowe L., Lindsay B., Gray J., Carey M., Brodie M., Bernstein P., Beech D. Third-Generation Database System Manifesto. Morgan Kaufmann Series In Data Management Systems Readings in database systems (2nd ed.):932-945, 1994. Disponible en http://www.cl.cam.ac.uk/teaching/2003/ DBaseThy/or-manifesto.pdf.

[SO90] Straube D. D., Ozsu M. T. Queries and Query Processing in Object-Oriented Database Systems. ACM Transaction on Database Systems(8)4: 387-430, 1990.

Disponible en http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.717.

https://doi.org/10.1145/102675.102678

[SZ89] Shaw G. M., Zdonik S. B. A Query Algebra for Object-Oriented Databases. Disponible en http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.7725.

[SZ89a] Shaw G.M., Zdonik S.B. Object-Oriented Queries: Equivalence and Optimization. Proceedings of the First International Conference on Deductive and Object-Oriented Databases (DOOD'89), Kyoto Research Park, Kyoto, Japan, 1989, pp. 281-295, 1989. Disponible en http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.5439.

[ZM91] Zdonik S. B., Mitchell G. ENCORE: An Object-Oriented Approach to Database Modelling and Querying. Data Engineering (14)2:53-57, 1991. Disponible en http://sites.computer.org/debull/91JUN-CD.pdf.

[Wang00] Wang Q. Cost-Based Object Query Optimization. Disponible en http://www.edbt2000.uni-konstanz.de/phd-workshop/papers/Wang.pdf.

Bibliografía básica anotada

[AAC+94] Annevelink J., Ahad R., Carlson A., Fishman D., Heytens M., Kent W. Object SQL- A Language for the Design and Implementation of Object Databases. In Modern database systems: the object model, interoperability, and beyond: 42-68, 1995, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA. Disponible en http://www.hpl.hp.com/techreports/94/HPL-94-02.pdf.

Se describe OSQL, Object SQL, un lenguaje de bases de datos que combina características de SQL y lenguajes de programación OO. OSQL se desarrolló como parte del proyecto IRIS de los laboratorios de Hewlett-Packard. Algunas de las características que ofrece OSQL son, identidad de objetos, sistema de tipos con herencia múltiple, agregación de objetos (listas y conjuntos), entre otras.

El modelo de OSQL se apoya en los conceptos de objetos, tipos y funciones. Este lenguaje está disponible en HP OpenODB un sistema de gestión de bases de datos OO.

[ADMB+89] Atkinson M., DeWitt D., Maier D., Bancilhon F., Dittrich K., Zdonik S. The Object-Oriented Database System Manifesto. Proceeding First International Conference on Deductive and Object-Oriented Databases, Kyoto, Japan 1989. Morgan Kaufmann Series In Data Management Systems Building an object-oriented database system: the story of 02, pp. 1-20. 1989. Disponible en http://citeseer.ist.psu.edu/atkinson89objectoriented.html.

En el artículo se define un sistema de gestión de bases de datos OO. Tres tipos de características de los sistemas se proponen: Obligatorias, opcionales y abiertas.

Entre las características obligatorias están el ser un SGBD, lo que implica ofrecer persistencia, gestión de almacenamiento secundario, concurrencia, recuperación y consultas ad-hoc. Adicionalmente, se espera que sea orientado a objetos, lo que significa que ofrezca soporte a objetos complejos, identidad de objeto, encapsulación, herencia, clases, entre otras.

Las características opcionales, que mejoran el sistema son, entre otras, soporte a herencia múltiple, chequeo de tipos y gestión de transacciones. Las características abiertas les ofrecen a los diseñadores más opciones. Entre estas se proponen, los constructores adicionales y un sistema de tipos.

[AK90] Abiteboul S., Kanellakis P. Database Theory Column: Query Languages for Complex Object Databases. ACM SIGACT News (21)3: 9-18, 1990.

https://doi.org/10.1145/101368.101370

Las bases de datos de objetos complejos se proponen como una extensión de una base de datos relacional. En este artículo se presentan lenguajes para manipular estas bases de datos: álgebra y cálculo multi-tipo.

[Bancilhon88] Bancilhon F. Object-Oriented Database System. Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems,PODS'88, pp. 152-162, Austin, Texas, 1988.

El artículo presenta una revisión sobre el estado de la investigación en el tema de las bases de datos orientadas a objetos. Se caracteriza un SGBD orientado a objetos. Entre las características que el autor propone debe ofrecer un SGBDOO están la encapsulación, la identidad de objeto, los tipos y las clases, la herencia y overriding and late binding.

A pesar de que los SGBD relacional unidos con un lenguaje de programación de propósito general, de acuerdo con el autor, son capaces de hacer "...casi todas las cosas… puesto que aseguran persistencia, son confiable, comparten datos, pueden modelar datos y ejecutar cualquier cálculo", aún existen aplicaciones difíciles de modelar con el relacional y que podrían ser lentas. En este sentido el autor compara los dos tipos de sistemas desde el punto de vista de la facilidad de programación y de la velocidad de cómputo.

Algunas de las ventajas de los SGBDOO sobre los SGBDR son el poder trabajar con objetos complejos, la identidad de objeto, la extendibilidad, la posibilidad de almacenar datos y programas bajo en mismo formalismo y sistema y la herencia, entre otros. Por otra parte, el cambio de modelo hace las cosas más difíciles puesto que la simplicidad del modelo relacional es una de sus ventajas. Adicionalmente, el modo de consulta ad-hoc sobre bases de datos relacionales cuentan con buenos lenguajes e interfaces de consulta. En los SGBDOO la manipulación de datos es más navegacional.

[BK90] Bancilhon F., Kim W. Object-Oriented Database Systems: In transition. SIGMOD Record (19)4:49-53, 1990.

https://doi.org/10.1145/122058.122063

En este artículo se discuten cinco tópicos que se consideraban relevantes en el desarrollo e investigación en sistemas de gestión de bases de datos OO: modelos y optimización de consulta, interfaces de usuario, metodologías de diseño, mecanismo de vistas y pruebas de desempeño.

Se proponen retos y líneas de trabajo investigativo en cada uno de estos tópicos. Algunos de estos retos se relacionan son:

• Contar con lenguajes de consultas que accedan a datos encapsulados en los objetos mediante la invocación de métodos.

• Extender la propiedad de cierre de los lenguajes de consulta relacionales a los lenguajes OO

• Optimización de consultas OO, debido a que este proceso es mas complejo en SGBDOO puesto que los datos tienen estructuras son más complejas y una consulta incluye la invocación a métodos.

• Desarrollo de metodologías OO específicamente para el diseño de bases de datos OO.

[Cattell91] Cattell R.G.G. ( Guest Editor) What are next-Generation Database System. Communication of the ACM (34)10:31-33, 1991.

En este artículo se presentan los principales enfoques de los sistemas de gestión de bases de datos de tercera generación llamados orientados a objetos o relacionales extendidos. Las características que deben ofrecer estos nuevos modelos incluyen los objetos, OIDs, procedimientos encapsulados, objetos compuestos y relaciones entre objetos. Se espera que estas nuevas características se añadan a las características más importantes de los sistemas de gestión tradicionales. En relación con aspectos de modelamiento de datos, la nueva generación de sistemas de gestión debería combinar las mejores características de los sistemas de gestión de bases de datos relacionales y las de los lenguajes de programación orientados a objetos.

Desde este punto de vista los sistemas se agrupan en dos grandes categorías, dependiendo de su origen: lenguajes de programación o sistemas de bases de datos. Esto significa que algunos surgen como extensiones de los lenguajes de programación ofreciendo persistencia, concurrencia, control y consultas, entre otras características. Otros, por su parte extienden las funcionalidades de un RDBMS con características de la programación OO (i.e. referencias a objetos, procedimientos).

[Chaudhri93] Chaudhri A. Object Oriented Management System: An Overview. Disponible en http://citeseer.ist.psu.edu/158152.html.

Se discuten las limitaciones del modelo de datos relacional y relacional extendido (poder expresivo limitado, tipos de datos disponibles muy simples, problemas de impedancia debido a la combinación de lenguajes anfitriones y SQL, problemas de desempeño).

Los requerimientos de un sistema de gestión de bases de datos objeto se relacionan y discuten: persistencia, transacciones, concurrencia, recuperación, consulta y seguridad.

Con base en estos requerimientos se clasifican los modelos de sistemas de gestión de bases de datos orientados a objetos en las siguientes categorías:

• Basados en Modelos de datos, que incluyen propuestas de modelos anidados (no en 1FN), modelos funcionales y modelos semánticos.

• Basados en Arquitecturas se incluyen propuestas de gestores de objetos, sistemas de bases de datos extendidos, lenguajes de programación de bases de datos, generadores de sistemas de bases de datos, entre otros.

• Modelos de servidores de almacenamiento

• Modelos basados en lenguajes para modelos de datos.

[CDV88] Carey M, DeWitt D., Vandenberg S. A Data Model and Query Language for EXODUS. Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, pp. 413-423, Chicago, Illinois, 1988.

Se presenta el modelo de datos EXTRA y el lenguaje de consulta EXCESS para el sistema de bases de datos extensible EXODUS.

Hay consenso por parte de los investigadores en que los sistemas de gestión de bases de datos OO son el futuro, sin embargo no lo hay en lo que el sistema debería ser. Las propuestas varían desde los lenguajes de programación OO con persistencia hasta sistemas de bases de datos completos basados en modelos semánticos de datos. El primer enfoque, de acuerdo con los autores, es retroceder a los lenguajes de manipulación de datos navegacionales lo que haría difícil pensar en consultas ad-hoc y el la optimización de accesos.

Otra de las orientaciones es la de extender el modelo relacional para ofrecer soporte a objetos complejos, nuevos tipos de datos manteniendo características asociadas al lenguaje de manipulación de datos amigable al usuario y potente.

En el modelo de datos propuesto EXTRA la base de datos es una colección de objetos nombrados y persistentes que pueden ser simples o complejos. En este modelo se separa la declaración de los tipos de sus instancias. EXTRA cuenta con tipos básicos y constructores para definir tipos esquema. Además de los tipos básicos enteros, punto flotante, booleanos y cadenas también da soporte a ADTs. Los constructores de tipos son tupla, conjunto y arreglos de longitud fija y variable y referencias.

Los objetos complejos, objetos compuestos de otros objetos, cada uno de los cuales a su vez puede estar compuesto de otros, se pueden construir mediante cuatros tipos de constructores de objetos, adicionales al constructor tipo tupla: ref, own, set y array. EXCESS, el lenguaje de consulta, permite formular consultas sobre conjuntos de objetos, conjuntos de referencias y conjuntos de valores propios (own) mediante una sintaxis uniforme. Las consultas especifican el dominio en el cual las variables toman valores mediante la expresión range of variable variable is (range _ specification). Se presentan detalles y ejemplos del lenguaje de consulta.

[GGT96] Gardarin G., Gruser JR.,Tang ZH. Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases. Proceedings of the 22nd VLDB Conference, Bombay, India, pp. 390-401, 1996.

En lenguajes de consulta objeto, las expresiones de camino representan navegación a través de los objetos, puesto que un objeto puede referenciar otros objetos mediante apuntadores. La navegación se puede restringir utilizando predicados y los objetos seleccionados en una consulta se pueden representar mediante variables.Estas expresiones se denominan expresiones de camino cualificadas.

En este artículo se evalúan estrategias en las cuales se combinan operaciones de join tradicionales con navegación basada en apuntadores. Se propone para esto un modelo para estimar los costos de los algoritmos de recorrido de colecciones. Para evaluar una expresión de camino se analizan tres algoritmos: Depth-First- Fetch (DFF), Breadth- First-Fetch (BFF) y Reverse- Breadth- First-Fetch (RBFF).

[GGMR00] Grant J., Gryz J., Minker J. Raschid L. Logic-Based Query Optimization for Object Databases. IEEE Transactions on Knowledge and Data Engineering (12)4:529-547, 2000.

Técnicas de optimización semántica se aplican en el proceso de optimización de consultas objeto. Usando restricciones de integridad, las consultas se transforman en otra consulta equivalente pero más eficiente. Información sobre jerarquías de clase, relaciones entre los objetos, entre otros, se expresa como restricciones de integridad.

Una consulta en OQL (no anidada) se expresa como una consulta lógica (Datalog), que se optimiza. Los constructores (e.g. set, array, list) no se tienen en cuenta en el proceso de optimización.

A partir del esquema de la base de datos, especificada en ODL, en una primera fase de pre-optimización, éste se transforma en expresiones lógicas. Se asume que las restricciones de integridad están expresadas en términos de la lógica.

En la fase de optimización, se construye una expresión lógica para la consulta OQL. A partir de aquí se obtienen las consultas equivalentes a la original, que se evalúan convencionalmente mediante métodos basados en costo para encontrar la consulta optimizada OQL. Se aplican heurísticas para guiar el proceso de generación de consultas equivalentes.

[Kabra99] Kabra N. Query Optimization for Object-Relational Database Systems. PhD Thesis, University of Wisconsin, Madison 1999. Disponible en http://pages.cs.wisc.edu/~navin/research/thesis.pdf.

En el caso de los SGBD objeto-relacional (SGBDOR), el problema de optimización es una tarea muy difícil y que toma mucho tiempo, puesto que los usuarios pueden definir funciones, tipos de datos, operadores y métodos. Son problemas abiertos de investigación la forma de recoger estadísticas y la estimación de la selectividad de los predicados cuando se trata con funciones definidas por el usuario.

Por lo tanto, es difícil estimar el costo de ejecución de una consulta en SGBDOR.

En esta tesis el autor ofrece una solución a estos problemas mediante una arquitectura de optimización de consultas extensible que denomina OPT++. OPT++ es una herramienta para construir optimizadores de consulta, que, de acuerdo con elautor, es flexible, extensible y fácil de usar.

Se describe también el algoritmo Dynamic Re-Optimization, para detectar planes sub-óptimos en tiempo de ejecución, mejorando el desempeño y re-optimizando la consulta dinámicamente. El algoritmo asume que se cuenta con un plan de ejecución anotado, con anotaciones de tamaño de relaciones intermedias y costo de ejecuciónde cada operador en la consulta. Durante la ejecución de la consulta y en ciertos puntos específicos se toman estadísticas que se usan para mejorar las estimaciones iniciales. Las estimaciones nuevas se comparan con las iniciales para detectar planes sub-óptimos. Cuando las nuevas estimaciones mejoran lo que falta por ejecutar del plan de ejecución, éste se cambia. El algoritmo se evalúa en el sistema Paradise.

[Kent79] Kent William. Limitations of Record-Based Information Models. ACM Transactions on Database Systems (4)1: 107-131, 1979.

https://doi.org/10.1145/320064.320070

Entre las limitaciones del modelo relacional referenciadas por Kent [Kent79]

están, entre otras, la homogeneidad de los registros, dado que en el mundo real, a pesar de que grupos de individuos pueden formar un "tipo" de cosas, existen variaciones relevantes entre los individuos de ese conjunto. Otra limitación se refiere a que la estructura de registros no siempre corresponde a las características que intuitivamente cualquiera asocia con una entidad, sobre todo si se tiene en cuenta la normalización. Los sistemas normalizados reducen el número de opciones para tratar relaciones uno-a-muchos y muchos-a-muchos. La descripción de los registros no ofrecen evidencia clara ni explicita no implícitamente de la existencia de relaciones. No es fácil distinguir atributos de relaciones.

[McClure97] McClure S. Object Database vs.Object-Relational Databases. International Data Corporation IDC Bulletin #14821E - 1997. Disponible en http://www.geog.ubc.ca/courses/geog516/notes/ordbms.htm.

Se analizan y comparan los sistemas de gestión de bases de datos OO y relacionales. Los dos modelos se comparan con respecto al modelo de datos subyacente, el lenguaje de consulta y el modelo computacional que utiliza. Adicionalmente se analizan los sistemas denominados post-relacionales o relacionales extendidos. Finalmente, se comparan los tres sistemas utilizando como criterios el estándar referente, soporte a programación orientada a objetos, simplicidad de uso, simplicidad para hacer desarrollos, extensibilidad, relaciones de datos complejos, desempeño y madurez del producto, entre otros.

[PBRV90] Premerlani W., Blaha M., Rumbaugh J.E., Varwig T. An Objectoriented Relational Database. Communications of the ACM (33)11: 99-109, 1990.

https://doi.org/10.1145/92755.92772

Se presenta una técnica para construir un sistema de gestión de bases de datos orientado a objetos a partir de un sistema de gestión de base de datos relacional y un lenguaje de programación orientado a objetos (LPOO). Un SGBDOO se define como la intersección de bases de datos y tecnología de programación orientadas a objetos.

La posibilidades son entonces extender un SGBDR con nuevos tipos de datos, operadores y métodos de acceso o extender los LPOO con funcionalidades de bases de datos como la persistencia, autorización y concurrencia y tendría que ser confiable administrando grandes volúmenes de datos.

La propuesta de los autores coincide con la segunda opción, extender el LPOO.

El mecanismo para gestionar datos usa y bloquea una porción de la base de datos que copia en RAM. Sobre esta copia se llevan a cabo todas las tareas de lectura y escritura. Cuando se termina la tarea los datos se llevan a la base de datos para hacerlos disponibles. El SGBDR es un recurso de bajo nivel oculto al usuario final.

Las clases definidas en el LPOO se convierten en tablas y las instancias de objeto en filas de la tabla. Para cada objeto se genera un identificador ID que sirve de llave primaria de cada objeto. Algunas relaciones se convierten en tablas y otras se almacenan como tablas objeto con apuntadores.

[Stonebraker86] Stonebraker M. Inclusion of New Types in Relational Database Systems, Proceedings of the Second International Conference on Data Engineering, pp. 262-269, IEEE Computer Society 1986. Disponible en http://citeseer.ist.psu.edu/stonebraker86inclusion.html.

En este artículo se propone un mecanismo para construir tipos de datos definidos por el usuario. La especificación de un tipo de dato nuevo incluye un registro de la existencia del nuevo tipo, la longitud de su representación interna y rutinas de conversión de entrada y salida, puesto que los nuevos valores son la entrada a un programa o una salida para el usuario. Se detalla también la sintaxis para definir nuevos tipos.

CAPÍTULO 6

[AS94] Agrawal R., Srikant R. Fast Algorithms for Mining Association Rules. Proceeding of the 20th Int'l Conference on Very Large Databases, Santiago, Chile, 1994. Expanded version available as IBM Research Report RJ9839, June 1994. Disponible en http://rakesh.agrawal-family.com/papers/vldb94apriori.pdf.

[AIS93] Agrawal R., Imielinski T., Swami A. Mining Association Rules between Sets of Items in Large Databases. Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., United States, pp. 207-216, 1993.

[Bodon03] Bodon F. A Fast Apriori Implementation. Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations Melbourne, USA, 2003. Disponible en http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-90/bodon.pdf.

[Borgelt05] Borgelt C. An Implementation of FP-Growth Algorithm. Proceedings of the 1st International Workshop on Open Source Data Mining OSDM '05, Chicago, Illinois pp. 1-5, 2005. Disponible en http://www.borgelt.net/papers/fpgrowth.pdf.

[BC04] Baralis E., Chiusano S. Essential Classification Rule Sets. ACM Transaction on Database Systems (29)4:635-674, 2004.

https://doi.org/10.1145/1042046.1042048

[BMUT97] Brin S. , Motwani R., Ullman J.D., Tsur S., Dynamic Itemset Counting and Implication Rules for Market Basket Data. ACM SIGMOD Record(6), 2:255-264, 1997. Disponible en http://w3.umh.ac.be/~ssi/tpdm/brin97.pdf.

[BS02] Blockeel H., Struyf J. Efficient Algorithm for Decision Tree Cross-Validation. Journal of Machine Learning Research (3):621-650, 2002.

[Chapman00] Chapman, P., Clinton, J., Kerber, R., Khabaza, T., Reinartz, T., Shearer, C., Wirth, R. CRISP-DM 1.0: Step-by-step data mining guide, CRISP-DM consortium, 2000. Disponible en http://www.crisp-dm.org.

[CK02] Cios K., Kurgan L. Trends in Data Mining and Knowledge Discovery. En: Pal N. R., Jain, L. C. and Teoderesku, N. (Eds.), Knowledge Discovery in Advanced Information Systems, 2002. Disponible en http:// citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.5317.

[CLNP06] Calders T., Lakshmanan L., Ng R., Paredaens J. Expressive Power of an Algebra for Data Mining. ACM Transaction on Database Systems (31)4:1169-1214, 2006.

[Dzeroski03] Dzeroski S. Multi-Relational Data Mining: An Introduction. ACM SIGKDD Exploration Newsletter (5)1:1-16, 2003. Disponible en www.sigkdd.org/explorations/issue5-1/Dzeroski.pdf.

https://doi.org/10.1145/959242.959245

[EZ04] El-Hajj M., Zaiane O. COFI Approach for Mining Frequent Itemsets Revisited. Proceedings of the 9th ACM SIGMOD workshop on Research Issues in Data Mining and Knowledge Discovery DMKD '04, pp. 70-75, Paris, France, 2004.

[EM07] Esmeir S., Markovitch S. Anytime Learning of Decision Trees. Journal of Machine Learning Research (8):891-933, 2007.

[EZ03] El-Hajj M., Zaiane O. COFI-Tree Mining: A New Approach to Pattern Growth with Reduced Candidacy Generation. Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations Melbourne, USA, 2003. Disponible en http://sunsite.informatik.rwth-aachen. de/Publications/CEUR-WS/Vol-90/elhajj.pdf.

[FPS96] Fayyad, U., Piatestky-Shapiro, G., Smyth, P. From Data Mining to Knowledge Discovery: An Overview. In (Fayyad, U., Piatestky-Shapiro, G., Smyth, P., Uthurusamy, R. (eds.)) Advances in Knowledge Discovery and Data Mining, AAAI Press, The MIT Press, Menlo Park, CA, 1996, pp. 1-34.

[GH06] Geng L., Hamilton H.J. Interestingness Measures for Data Mining: A Survey. ACM Computing Surveys (38)3, Article 9, 2006.

https://doi.org/10.1145/1132960.1132963

[Goethals03] Goethals B. Survey on Frequent Pattern Mining, Technical Report (2003), University of Helsinki, Finland. Disponible en http://www. adrem.ua.ac.be/~goethals/software/survey.pdf.

[GZ03] Goethals B, Zaki M. Advances in Frequent Itemset Mining Implementation: Introduction to FIMI03. Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations Melbourne, USA,

Disponible en http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-90/intro.pdf.

[HF08] Hall M., Frank E. Combining Naïve Bayes and Decision Tables. Disponible en www.cs.waikato.ac.nz/~ml/publications/2008/HallAndFrankFLAIRS08.pdf.

[HFWKZ96] Han J., Fu Y., Wang W., Koperski K., Zaiane O. DMQL: A Data Mining Query Language for Relational Databases. 1996 SIGMOD'96 Workshop on Research Issues on Data Mining and Knowledge Discovery KMKD'96, pp.27-33, Montreal, Canadá, 1996. Disponible en http://citeseerx. ist.psu.edu/viewdoc/summary?doi=10.1.1.30.4217.

[HK2006] Han J., Kamber M. Data mining: Concepts and Techniques. Morgan Kaufmann Publishers, ELSEVIER 2006 http://www.cs.sfu.ca/~han/dmbook. Data mining: practical machine learning tools w/ java implementations.

[HPYM04] Han J., Pei J., Yin Y., Mao R. Mining frequent patterns without candidate generation: A Frequent-Pattern Tree Approach. Data Mining and Knowledge Discovery (8): 53-87, 2004. Disponible en http://www-faculty.

https://doi.org/10.1023/B:DAMI.0000005258.31418.83cs.uiuc.edu/~hanj/pdf/dami04_fptree.pdf.

[HPY00] Han J., Pei J., Yin Y. Mining frequent patterns without candidate generation. ACM SIGMOD Record (29)2:1-12, 2000. Disponible en www.cs.uiuc.edu/~hanj/pdf/dami04_fptree.pdf. https://doi.org/10.1145/335191.335372

[HPYM04] Han J., Pei J., Yin Y. Mining frequent patterns without candidate generation. Data Mining and Knowledge Discovery (8):53-87, 2004.

https://doi.org/10.1023/B:DAMI.0000005258.31418.83

[HCC92] Han J., Cai Y., Cercone N. Knowledge Discovery in Databases: An Attribute-Oriented Approach. ACM SIGMOD Record (29)2:1-12, 2000.

https://doi.org/10.1145/335191.335372

[HL05] Hu H., Li J. Using Association Rules to Make Rule-based Classifiers Robust. Proceedings of the 16th Australasian Database Conference ADC '05, pp. 47-54, Newcastle, Australia, 2005.

[JFA08] Jin R., Fuhry D., Alali A. Cost-Based Query Optimization for Complex Pattern Mining on Multiple Databases. Proceedings of the 11th International Conference on Extending Database Technology, EDBT '08,

pp. 380-391, Nantes, France, 2008.

[JG06] Jiang N., Gruenwald L. Research Issues in Data Stream Association Rule Mining. SIGMOD Record (35)1:14-19, 2006.

https://doi.org/10.1145/1121995.1121998

[JLS08] Jen T., Laurent D., Spyratos N. Mining All Frequent Projection-Selection Queries from a Relational Table. Proceedings of the 11th International Conference on Extending Database Technology, EDBT '08, pp. 368-379, Nantes, France, 2008.

[KJC04] Kantarcioglu M., Jin J., Clifton C. When Do Data Mining Results Violate Privacy?. Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '04, pp. 599-604, Seattle, WA, USA, 2004.

[LCH+07] Liu Y., Cai J., Huang Z., Yu J., Yin J. Fast Detection of Database System Abuse Behaviors Based on Data Mining Approach. Proceedings of the 2nd International Conference on Scalable Information Systems InfoScale '07, pp. 1-7, Suzhou, China 2007.

https://doi.org/10.4108/infoscale.2007.916

[LPWH02] Liu J., Pan Y., Wang K., Han J. Mining frequent item sets by opportunistic projection. Proceedings of the eighth ACM SIGKDD international conference on Knowledge Discovery and Data Mining, KDD 02,pp. 229-237, Edmonton, Alberta, Canada, 2002. Disponible en http://www.cs.sfu.ca/~wangk/pub/KDD-Junqaing-Arial.pdf.

[Quinlan96] Quinlan J.R. Learning Decision Tree Classifiers. ACM Computing Surveys (28)1:71-71 , 1996.

https://doi.org/10.1145/234313.234346

[SL91] Safavian S.R., Landgrebe D. A Survey of Decision Tree Classifier Methodology. IEEETransaction on Systems, Man and Cybernetics (21)3:660-674, 1991. Disponible en http://cobweb.ecn.purdue.edu/~landgreb/SMC91.pdf.

[SS05] Shang X., Sattler K.U. Depth-First Frequent Itemset Mining in Relational Databases. Proceedings of the 2005 ACM Symposium on Applied Computing SAC '05, pp. 1112-1117, Santa Fe, New Mexico, 2005.

[SSG04] Shang X., Sattler K.U., Geist I. SQL Based Frequent Pattern Mining Without Candidate Generation. Proceedings of the 2004 ACM Symposiumon Applied Computing, SAC '04, pp 618-619, Nicosia, Cyprus, 2004.

[STA98] Sarawagi S., Thomas S., Agrawal R. Integrating association rule mining with relational database systems: alternatives and implications.Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data, SIGMOD'98, pp. 343-354. Disponible en http://rakesh.agrawal-family.com/papers/sigmod98dbi.pdf.

[YPK00] Yoshizawa T., Pramudiono I., Kitsuregawa M. SQL Based Association Rule Mining using commercial RDBMS (IMB DB2 UDB EEE). In Proceedings of the Second International Conference on Data Warehousing and Knowledge Discovery, pp. 301-306, 2000. Disponible en http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.9604.

[YWY07] Yuan J., Wu Y., Yang M. From Frequent Itemsets to Semantically Meaningful Visual Patterns. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '07, pp. 864-873, San José, California, USA, 2007.

Bibliografía básica anotada

[FPS96] Fayyad, U., Piatetstky-Shapiro, G., Smyth, P. From Data Mining to Knowledge Discovery: An Overview. In (Fayyad, U., Piatetstky-Shapiro, G., Smyth, P., Uthurusamy, R. (eds.)) Advances in Knowledge Discovery and Data Mining, AAAI Press, The MIT Press, Menlo Park, CA, 1996, pp. 1-34.

En este artículo se describe el proceso de descubrimiento de conocimiento en bases de datos (KDD- Knowledge Discovery in Databases) como un "proceso no trivial de identificación de patrones válidos, novedosos, potencialmente útiles y entendibles a partir de los datos". El proceso propuesto, interactivo e iterativo, está integrado por nueve etapas. Las etapas que se propones son: entendimiento del dominio, creación de un conjunto de datos objetivo, limpieza y pre-procesamiento de datos, reducción y proyección de datos, selección de tareas de data mining, selección de los algoritmos de data mining, data mining o búsqueda de patrones interesantes, interpretación de patrones obtenidos y incorporación del conocimiento descubierto a la organización.

[Chapman00] Chapman, P., Clinton, J., Kerber, R.,Khabaza, T., Reinartz, T., Shearer, C., Wirth, R. CRISP-DM 1.0: Step-by-step data mining guide, CRISP-DM consortium, 2000. Disponible en http://www.crisp-dm.org.

Se describe de manera detallada el estándar para proyectos de minería de datos, CRISP-DM. Cada una de las tareas asociadas con cada una de las etapas que integran el proceso: entendimiento del negocio, entendimiento de los datos, preparación de datos, evaluación, utilización y aplicación, se describe. Un conjunto de entregables de cada una de las tareas que forman parte de una etapa se presentan también en el estándar.

[HPY00] Han J., Pei J., Yin Y. Mining frequent patterns without candidate generation. ACM SIGMOD Record (29)2:1-12, 2000. Disponible en www.cs.uiuc.edu/~hanj/pdf/dami04_fptree.pdf. https://doi.org/10.1145/335191.335372

En este artículo se presenta un algoritmo para generación de itemsets frecuentes que no requiere de la etapa de generación de candidatos propia del algoritmo Apriori.

Una estructura compacta denominada FP-tree se construye para almacenar conjuntos de ítems. El nodo raíz del árbol se etiqueta con "null". Cada una de las transacciones se procesa inicialmente para calcular el soporte de los conjuntos de ítems de tamaño 1. A partir de este cálculo se almacenan en el árbol prefijo, las transacciones. Los nodos hoja del árbol son conjuntos de ítems frecuentes de tamaño 1. Las transacciones que comparten un prefijo común de conjuntos de ítems frecuentes (en un orden de frecuencia), se combinan en la estructura de árbol. Después de que el árbol de patrones frecuentes (FP) se ha construido no se requiere volver a acceder a la base de datos de transacciones.

El algoritmo para construir el FP-Tree se presenta en el artículo para el cual se analizan varias propiedades. La estructura se explora para obtener todos los patrones frecuentes.

Resultados experimentales de desempeño se presentan con respecto a los algoritmos Apriori [AS94] y TreeProjection [LPWH02].

BIBLIOGRAFÍA GENERAL

[AA93] Atzeni P., De Antonellis V. Relational Database Theory. The Benjamin/Cummings Publishing Company, Inc., 1993.

[AHV95] Abiteboul S., Hull R., Vianu V. Foundations of Databases. Addison-Wesley Publishing Company, 1995.

[Cattell94] Cattell R. G. G. Object Data Management. Object-oriented and extended relational database systems. Addison-Wesley Publishing Company 1994.

[CBB+97] Cattell R. G. G., Barry D. K., Bartels D., Eastman J., Gamerman S., Jordan D., Springer A., Strickland H., Wade D. The Object Data Standard: ODMG 2.0. Morgan Kuffmann, San Francisco, California, 1997.

[CBB+00] CattellR.G.G., Barry D.K., Berler M., Eastman J., Jordan D., Russell C., Schadow O., Stanienda T., Velez F. The Object Data Standard:ODMG 3.0. Morgan Kuffmann, San Francisco, California, 2000.

[CHS+98] Cabena P., Hadjinian P., Stadler R., Verhees J., Zanasi A. . Discovering Data Mining from concept to implementation. Prentice Hall. 1998.

[CBS98] Connolly T., Begg C., Strachan A. Database Systems. A practical Approach to design, Implementation and Management. Second Edition, Addison-Wesley, 1998.

[Codd90] Codd Edgard. The Relational Model for Database Management, Version 2. Addison-Wesley Publishing Company, 1990.

[Date98] Date C. J. Relational DATABASE. Writings 1994-1997. Addison-Wesley, 1998.

[Date2005] Date C. J. Database in depth. Relational Theory for Practitioners. O'Reilly, 2005.

[Fayyad96] Fayyad, U., Grinstein, G. G., Wierse, A. (eds.) Information Visualization in Data Mining and Knowledge Discovery, Morgan Kaufmann 2001.

[FPSU96] Fayyad, U., Piatetstky-Shapiro, G., Smyth, P., Uthurusamy, R. (eds.)) Advances in Knowledge Discovery and Data Mining, AAAI Press, The MIT Press, Menlo Park, CA, 1996.

[GUW00] Garcia-Molina H., Ullman J., Widom J. Database System Implementation. Prentice Hall, 2000.

[HMS2001] Hand D., Mannila H., Smyth P. Principles of Data Mining. The MIT Press, 2001.

[Inmon96] Inmon W.H. Building the DataWarehouse. Second Edition. John Willey and Sons Inc. 1996.

[IWG97] Inmon H., Welch J., Glassey K. Managing the Data Warehouse. John Willey and Sons Inc., 1997.

[Maier83] Maier David. The Theory of Relational Databases. Disponible en http://web.cecs.pdx.edu/~maier/TheoryBook/TRD.html.

[Mattison97] Mattison R. Data Warehouse Strategies Technologies and Techniques. McGraw Hill, 1997.

[ML+2003] Data Mining and Decision Support. Integration and Collaboration. Edited by Dunja Mladenic, Nada Lavrac, Marko Bohanec, Steve Moyl. Kluwer Academic Publishers, 2003.

[Pyle99] Pyle Dorian. Data Preparation for Data Mining. Morgan Kaufmann, 1999.

[SM96] Stonebraker M., Moore D. Object-relational DBMSs. The Next Great Wave. Morgan Kaufmann Publishers, Inc, 1996.

[SW2005] Simsion G. C., Witt G. C. Data Modeling Essentials. Morgan Kaufmann Publishers, Third Edition, 2005.

[Ullman89] Ullman, J. D. Principles of Database and Knowledge Base Systems, vol. II: The New Technologies. Computer Science Press, Rockville, MD, 1989.

[WF05] Witten I., Frank E. Data Mining: Practical Machine Learning Tools and Techniques (Second Edition). Morgan Kaufmann, 2005. Documentación de WEKA (Waikato Environment for Knowledge Analisis) Data Mining Software in Java. Disponible en http://www.cs.waikato.ac.nz/~ml/weka/index.html.