Questão 2947048

• Banca: IADES
• Órgão: AL-GO
• Ano: 2019
• Provas: IADES - 2019 - AL-GO - Segurança da Informação
• Disciplina: Banco de Dados
• Assuntos: SQL

A operação join é uma das mais utilizadas em bancos de dados relacionais. Considere duas tabelas, uma de tamanho M e outra de tamanho N. Imagine que ambas estão indexadas (usando B-Tree index) em um campo id com valores únicos. Acerca do exposto, assinale a alternativa que melhor corresponde à complexidade temporal da seguinte operação de merge join nessas tabelas: SELECT * FROM M, N WHERE M.id=N.id.

• A. O(min(log(M), log(N)))
• B. O(min(M, N))
• C. O(M * N)
• D. O(M + N)
• E. O(log(M) + log(N))

Gabarito: D

Comentários

• cricri cricri

• Queria muito entender essa questão! Kkkk Alguém?

• Sort Merge Join

  Ordena relação R pelo atributo de junção

  Ordena relação S pelo atributo de junção

  Carrega página de R e página de S na memória.

  Varre ambas as páginas simultaneamente para encontrar as tuplas que casam.

  À medida que se encontram as tuplas que casam vai-se construindo páginas da relação de output.

  Relação interna é varrida uma única vez !

  Portanto o custo da junção é M + N

  Contrapartida: custo da ordenação das 2 tabelas !

  Fonte: https://slideplayer.com.br/slide/5704771/