2011-gre-cs-practice-book.pdf/Q66 — различия между версиями
Ssergomol (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показано 8 промежуточных версий 1 участника) | |||
| Строка 5: | Строка 5: | ||
Пример одной из таких гистограмм для отношения R по дискретному атрибуту a с доменом <m>\([1..10]\)</m>: | Пример одной из таких гистограмм для отношения R по дискретному атрибуту a с доменом <m>\([1..10]\)</m>: | ||
| − | * Бакет 1: Диапазон = | + | * Бакет 1: Диапазон = [1..2], кумулятивное количество кортежей = 6 |
| − | * Бакет 2: Диапазон = | + | * Бакет 2: Диапазон = [3..8], кумулятивное количество кортежей = 30 |
| − | * Бакет 3: Диапазон = | + | * Бакет 3: Диапазон = [9..10], кумулятивное количество кортежей = 10 |
Какова оценка размера операции self-join <m>\(R \bowtie R\)</m>? | Какова оценка размера операции self-join <m>\(R \bowtie R\)</m>? | ||
| Строка 23: | Строка 23: | ||
У нас есть три бакета с равномерными частотами: | У нас есть три бакета с равномерными частотами: | ||
| − | * Бакет 1: 2 значения, каждое с <m> freq = \frac{6}{2} = | + | * Бакет 1: 2 значения, каждое с <m>freq =\frac{6}{2}=3</m> |
| − | * Бакет 2: 6 значений, каждое с <m> freq = \frac{30}{6} = | + | * Бакет 2: 6 значений, каждое с <m> freq =\frac{30}{6}=5 </m> |
| − | * Бакет 3: 2 значения, каждое с <m> freq = \frac{10}{2} = | + | * Бакет 3: 2 значения, каждое с <m> freq =\frac{10}{2}=5 </m> |
| − | Для self-join | + | Для self-join по атрибуту a оценка размера равна <m>\(\sum_{v \in \text{Domain}} \bigl(\text{freq}(v)\bigr)^2\)</m>, где <m>\text{freq}(v)</m> — это количество кортежей, имеющих значение <m>v</m> по атрибуту <m>a</m>. |
Следовательно: | Следовательно: | ||
| Строка 50: | Строка 50: | ||
</code-python> | </code-python> | ||
| − | {{question-ok | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 16:29, 12 января 2025 (UTC)}} |
| − | + | ||
| + | [[Категория:Базы данных]] | ||
Текущая версия на 16:29, 12 января 2025
Вопрос: Q66-08c765
Оптимизаторы запросов обычно используют сводки распределений данных для оценки размеров промежуточных таблиц, создаваемых в процессе выполнения запросов. Одной из популярных схем суммирования является гистограмма, где диапазон входных данных делится на бакеты, и для каждого бакета подсчитывается кумулятивное количество кортежей. Предполагается, что распределение внутри каждого бакета равномерное для целей оценки.
Пример одной из таких гистограмм для отношения R по дискретному атрибуту a с доменом :
- Бакет 1: Диапазон = [1..2], кумулятивное количество кортежей = 6
- Бакет 2: Диапазон = [3..8], кумулятивное количество кортежей = 30
- Бакет 3: Диапазон = [9..10], кумулятивное количество кортежей = 10
Какова оценка размера операции self-join ?
Ответы
- 46
- Правильный ответ: 218
- 248
- 1036
- 5672
Объяснение
Исходники — вопрос 66 на 46 странице книги «2011-gre-cs-practice-book.pdf»
У нас есть три бакета с равномерными частотами:
- Бакет 1: 2 значения, каждое с
- Бакет 2: 6 значений, каждое с
- Бакет 3: 2 значения, каждое с
Для self-join по атрибуту a оценка размера равна , где — это количество кортежей, имеющих значение по атрибуту .
Следовательно:
import sympy f1, f2, f3 = sympy.symbols('f1 f2 f3', positive=True) c1, c2, c3 = sympy.symbols('c1 c2 c3', positive=True) expr = c1*f1**2 + c2*f2**2 + c3*f3**2 values = {f1: 3, f2: 5, f3: 5, c1: 2, c2: 6, c3: 2} res = expr.subs(values) print("Оценка размера self-join:", res) # 218