Una ilustración de las propiedades de los algoritmos de unión. Al realizar una unión entre más de dos relaciones en más de dos atributos, los algoritmos de unión binarios, como la unión hash , operan sobre dos relaciones a la vez y las unen en todos los atributos en la condición de unión; los algoritmos óptimos en el peor de los casos, como la unión genérica, operan sobre un solo atributo a la vez, pero unen todas las relaciones en este atributo. [1]
Un algoritmo de unión óptima en el peor de los casos es un algoritmo para calcular uniones relacionales con un tiempo de ejecución limitado por el tamaño de salida de la unión en el peor de los casos . Los algoritmos de unión binaria tradicionales, como la unión hash , funcionan sobre dos relaciones a la vez; las uniones entre más de dos relaciones se implementan aplicando uniones binarias repetidamente. Los algoritmos de unión óptima en el peor de los casos son asintóticamente más rápidos en el peor de los casos que cualquier algoritmo de unión basado en dichas uniones binarias iteradas.
El primer algoritmo de unión óptima en el peor de los casos, la unión genérica , se publicó en 2012. [2] Los algoritmos de unión óptima en el peor de los casos se han implementado en sistemas de bases de datos comerciales, incluido el sistema LogicBlox . [3] [4] Las uniones óptimas en el peor de los casos se han aplicado para construir un algoritmo óptimo en el peor de los casos para la correspondencia electrónica . [5]
Referencias
Notas
^ Wang, Yisu Remy; Willsey, Max; Suciu, Dan (27 de enero de 2023). "Unión libre: unificación de uniones óptimas y tradicionales en el peor de los casos". arXiv : 2301.10841 [cs.DB].
^ Ngo, Hung Q.; Porat, Ely; Ré, Christopher; Rudra, Atri (8 de marzo de 2012). "Algoritmos de unión óptima en el peor de los casos". arXiv : 1203.1952 [cs.DB].
^ Veldhuizen, Todd L. (2013-12-20). "Leapfrog Triejoin: un algoritmo de unión óptimo en el peor de los casos". arXiv : 1210.0481 [cs.DB].
^ Freitag, Michael; Bandle, Maximilian; Schmidt, Tobias; Kemper, Alfons; Neumann, Thomas (1 de julio de 2020). "Adopción de uniones óptimas en el peor de los casos en sistemas de bases de datos relacionales". Actas de la Fundación VLDB . 13 (12): 1891–1904. doi :10.14778/3407790.3407797. ISSN 2150-8097. S2CID 221115321.
^ Zhang, Yihong; Wang, Yisu Remy; Willsey, Max; Tatlock, Zachary (12 de enero de 2022). "Correspondencia electrónica relacional". Actas de la ACM sobre lenguajes de programación . 6 (POPL): 35:1–35:22. doi : 10.1145/3498696 . S2CID 236924583.
Fuentes
Ngo, Hung Q.; Porat, Ely; Ré, Christopher; Rudra, Atri (13 de marzo de 2018). "Algoritmos de unión óptimos en el peor de los casos". Revista de la ACM . 65 (3): 16:1–16:40. arXiv : 1203.1952 . doi :10.1145/3180143. ISSN 0004-5411.
Ngo, Hung Q; Ré, Christopher; Rudra, Atri (28 de febrero de 2014). "El sesgo contraataca: nuevos desarrollos en la teoría de algoritmos de unión". ACM SIGMOD Record . 42 (4): 5–16. doi :10.1145/2590989.2590991. ISSN 0163-5808. S2CID 6384477.
Enlaces externos
Una introducción suave a las uniones óptimas en el peor de los casos
