2011-gre-cs-practice-book.pdf/Q66 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(→‎Объяснение)
 
(не показано 11 промежуточных версий 1 участника)
Строка 5: Строка 5:
 
Пример одной из таких гистограмм для отношения R по дискретному атрибуту a с доменом <m>\([1..10]\)</m>:
 
Пример одной из таких гистограмм для отношения R по дискретному атрибуту a с доменом <m>\([1..10]\)</m>:
  
−
* Бакет 1: Диапазон = <m>\([1..2]\)</m>, кумулятивное количество кортежей = 6   
+
* Бакет 1: Диапазон = [1..2], кумулятивное количество кортежей = 6   
−
* Бакет 2: Диапазон = <m>\([3..8]\)</m>, кумулятивное количество кортежей = 30   
+
* Бакет 2: Диапазон = [3..8], кумулятивное количество кортежей = 30   
−
* Бакет 3: Диапазон = <m>\([9..10]\)</m>, кумулятивное количество кортежей = 10   
+
* Бакет 3: Диапазон = [9..10], кумулятивное количество кортежей = 10   
  
 
Какова оценка размера операции self-join <m>\(R \bowtie R\)</m>?
 
Какова оценка размера операции self-join <m>\(R \bowtie R\)</m>?
Строка 23: Строка 23:
 
У нас есть три бакета с равномерными частотами:
 
У нас есть три бакета с равномерными частотами:
  
−
* Бакет 1: 2 значения, каждое с freq <m> = \frac{6}{2} = 3 </m>
+
* Бакет 1: 2 значения, каждое с <m>freq =\frac{6}{2}=3</m>
−
* Бакет 2: 6 значений, каждое с freq <m> = \frac{30}{6} = 5 </m>   
+
* Бакет 2: 6 значений, каждое с <m> freq =\frac{30}{6}=5 </m>   
−
* Бакет 3: 2 значения, каждое с freq <m> = \frac{10}{2} = 5 </m>   
+
* Бакет 3: 2 значения, каждое с <m> freq =\frac{10}{2}=5 </m>   
  
−
Для self-join на a оценка размера равна <m>\(\sum \text{freq}(v)^2\)</m>.  
+
Для 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)}}
−
{{reserve-task|[[Участник:Ssergomol|Ssergomol]] 09:36, 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
Источник — «https://discopal.ispras.ru/index.php?title=2011-gre-cs-practice-book.pdf/Q66&oldid=35707»