2011-gre-cs-practice-book.pdf/Q66 — различия между версиями
Материал из DISCOPAL
Ssergomol (обсуждение | вклад) |
Ssergomol (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== Вопрос: Q66-08c765 == | == Вопрос: Q66-08c765 == | ||
| − | + | Оптимизаторы запросов обычно используют сводки распределений данных для оценки размеров промежуточных таблиц, создаваемых в процессе выполнения запросов. Одной из популярных схем суммирования является гистограмма, где диапазон входных данных делится на бакеты, и для каждого бакета подсчитывается кумулятивное количество кортежей. Предполагается, что распределение внутри каждого бакета равномерное для целей оценки. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | Пример одной из таких гистограмм для отношения \(R\) по дискретному атрибуту \(a\) с доменом \([1..10]\): | |
| − | + | ||
| − | + | * Бакет 1: Диапазон = \([1..2]\), кумулятивное количество кортежей = 6 | |
| + | * Бакет 2: Диапазон = \([3..8]\), кумулятивное количество кортежей = 30 | ||
| + | * Бакет 3: Диапазон = \([9..10]\), кумулятивное количество кортежей = 10 | ||
| + | |||
| + | Какова оценка размера операции self-join <m>\(R \bowtie R\)</m>? | ||
=== Ответы === | === Ответы === | ||
| − | + | * 46 | |
| − | + | * Правильный ответ: 218 | |
| + | * 248 | ||
| + | * 1036 | ||
| + | * 5672 | ||
| − | + | === Объяснение === | |
| − | + | {{cstest-source|2011-gre-cs-practice-book.pdf|46|66}} | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | У нас есть три бакета с равномерными частотами: | |
| − | + | ||
| − | + | ||
| + | * Бакет 1: 2 значения, каждое с freq = 3 | ||
| + | * Бакет 2: 6 значений, каждое с freq = 5 | ||
| + | * Бакет 3: 2 значения, каждое с freq = 5 | ||
| − | == | + | Для self-join на a оценка размера равна <m>\(\sum \text{freq}(v)^2\)</m>. Следовательно: |
| − | < | + | |
| − | + | <m> | |
| + | \[ | ||
| + | 2\times 3^2 \;+\; 6\times 5^2 \;+\; 2\times 5^2 | ||
| + | = 18 \;+\; 150 \;+\; 50 | ||
| + | = 218. | ||
| + | \] | ||
| + | </m> | ||
| + | |||
| + | <code-python> | ||
| + | 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 | ||
| + | </code-python> | ||
{{question-ok|}} | {{question-ok|}} | ||
{{reserve-task|[[Участник:Ssergomol|Ssergomol]] 09:36, 12 января 2025 (UTC)}} | {{reserve-task|[[Участник:Ssergomol|Ssergomol]] 09:36, 12 января 2025 (UTC)}} | ||
Версия 09:44, 12 января 2025
Вопрос: Q66-08c765
Оптимизаторы запросов обычно используют сводки распределений данных для оценки размеров промежуточных таблиц, создаваемых в процессе выполнения запросов. Одной из популярных схем суммирования является гистограмма, где диапазон входных данных делится на бакеты, и для каждого бакета подсчитывается кумулятивное количество кортежей. Предполагается, что распределение внутри каждого бакета равномерное для целей оценки.
Пример одной из таких гистограмм для отношения \(R\) по дискретному атрибуту \(a\) с доменом \([1..10]\):
- Бакет 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 значения, каждое с freq = 3
- Бакет 2: 6 значений, каждое с freq = 5
- Бакет 3: 2 значения, каждое с freq = 5
Для 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
Задача зарезервирована: Ssergomol 09:36, 12 января 2025 (UTC)