Care este algoritmul pentru interogarea datelor din două tabele și care este complexitatea sa?

Interogarea datelor din două tabele se realizează de obicei folosind operația JOIN în SQL. Algoritmul depinde de tipul de join (INNER JOIN, LEFT JOIN etc.) și de metoda de execuție (buclă imbricată, hash join, merge join).

Exemplu de interogare:

SELECT a.*, b.*
FROM tableA a
JOIN tableB b ON a.key = b.key;

Algoritm:

1. Pentru fiecare înregistrare din prima tabelă, se caută în a doua înregistrările corespunzătoare conform condiției de join.
2. Rezultatele sunt combinate într-un singur rând.

Complexitatea depinde de implementare:

• Nested loops join — O(N*M), unde N și M sunt dimensiunile tabelelor.
• Hash join — O(N + M), dacă datele încap în memorie și hashing-ul este eficient.
• Merge join — O(N log N + M log M), dacă tabelele sunt sortate.

Optimizarea interogării și alegerea algoritmului depind de indecși, volumul de date și statisticile bazei de date.