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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: « == Вопрос: Q66-08c765 == <i>Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80…»)
 
 
(не показано 19 промежуточных версий 1 участника)
Строка 1: Строка 1:
−
 
 
== Вопрос: Q66-08c765 ==
 
== Вопрос: Q66-08c765 ==
  
−
<i>Тут вставьте перевод вопроса.
+
Оптимизаторы запросов обычно используют сводки распределений данных для оценки размеров промежуточных таблиц, создаваемых в процессе выполнения запросов. Одной из популярных схем суммирования является гистограмма, где диапазон входных данных делится на бакеты, и для каждого бакета подсчитывается кумулятивное количество кортежей. Предполагается, что распределение внутри каждого бакета равномерное для целей оценки.
−
Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 возможности разметки],  
+
−
включая формулы и т.п, если будут графы — посмотрите как задать их текстом https://wiki.4intra.net/Graphviz .  
+
−
Если код — теги «code-pascal», «code-c» или «code-python».
+
  
−
Старайтесь нетривиальные понятия, особенно незнакомые вам, найти ссылку на википедию и вставить (нейросети лажают!).  
+
Пример одной из таких гистограмм для отношения R по дискретному атрибуту a с доменом <m>\([1..10]\)</m>:
−
Это важно, чтобы найти корректный перевод (то, что в википедии, или на худой конец — точно массово гуглится).
+
  
−
Потом конечно сотрите инструкции, которые тут курсивом.</i>
+
* Бакет 1: Диапазон = [1..2], кумулятивное количество кортежей = 6 
 +
* Бакет 2: Диапазон = [3..8], кумулятивное количество кортежей = 30 
 +
* Бакет 3: Диапазон = [9..10], кумулятивное количество кортежей = 10 
 +
 
 +
Какова оценка размера операции self-join <m>\(R \bowtie R\)</m>?
  
 
=== Ответы ===
 
=== Ответы ===
−
<i>Если ответы простые, однострочные, используйте простой способ задания ответов списком, типа так
+
* 46
−
(префикс «Правильный ответ:» — это дословно, для правильного ответа, неважно, какой он будет в списке)</i>
+
* Правильный ответ: 218
 +
* 248
 +
* 1036
 +
* 5672
  
−
* Правильный ответ: тут реально правильный ответ
+
=== Объяснение ===
−
* неправильный ответ
+
{{cstest-source|2011-gre-cs-practice-book.pdf|46|66}}
−
* еще какой-то неправильный ответ
+
−
* еще какой-то неправильный ответ
+
−
* еще какой-то неправильный ответ
+
  
−
<i>Если ответы длинные, многострочные, или там графы, используйте
+
У нас есть три бакета с равномерными частотами:
−
[https://wiki.4intra.net/MediawikiQuizzer/ru#.D0.9E.D1.82.D0.B2.D0.B5.D1.82.D1.8B способ задания ответов разделами],
+
−
Но такое очень редко встречается. </i>
+
  
 +
* Бакет 1: 2 значения, каждое с <m>freq =\frac{6}{2}=3</m>
 +
* Бакет 2: 6 значений, каждое с <m> freq =\frac{30}{6}=5 </m> 
 +
* Бакет 3: 2 значения, каждое с <m> freq =\frac{10}{2}=5 </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>.
−
<i>Сначала заполните номер страницы с этим вопросом
+
 
−
{{cstest-source|2011-gre-cs-practice-book.pdf|тут-номер-страницы-с-вопросом-66|66}}
+
Следовательно:
 +
<m>
 +
\[
 +
2\times 3^2 \;+\; 6\times 5^2 \;+\; 2\times 5^2 = 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
  
−
Если все сделаете правильно, по ссылке выше будет открываться правильная страница в правильном PDFе.
+
values = {f1: 3, f2: 5, f3: 5, c1: 2, c2: 6, c3: 2}
  
−
Ну и наконец, вики-разметкой напишите ваше понимание, почему правильный ответ — правильный, а [[2004-gre-cs-practice-book.pdf/Q16|неправильные варианты — неправильны]].
+
res = expr.subs(values)
−
Тут тоже могут быть полезны [[2004-gre-cs-practice-book.pdf/Q03|ссылки на википедию]],  
+
print("Оценка размера self-join:", res)  # 218
−
решение вами [[2004-gre-cs-practice-book.pdf/Q12|рекуррентных уравнений в sympy]].
+
</code-python>
  
−
</i>
+
{{question-ok|[[Участник:StasFomin|StasFomin]] 16:29, 12 января 2025 (UTC)}}
  
−
{{question-ok|}}
+
[[Категория:Базы данных]]

Текущая версия на 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»