Одновременное резкое увеличение объемов и разнообразия типов данных, доступных для массовой обработки, расширение класса решаемых задач и ужесточение требований по времени их выполнения, привели, наряду с использованием специализированных программных средств, к динамичному развитию высокоуровневых скриптовых языков для декларативного описания сценариев аналитической обработки и к необходимости пересмотра известных методов выполнения и оптимизации декларативных запросов.

В работе рассматриваются подходы к выполнению и оптимизации высокоуровневых точных и приближенных запросов; обсуждаются открытые проблемы и возможные направления их решения.

В обзорной части доклада рассматривается класс приближенных запросов, ставший широко распространенным в контексте новых типов обработки и поиска данных; приводится классификация подходов к оптимизации и выполнению приближенных запросов на основе сопоставления с методами, разработанными для точных декларативных запросов. Проведенный анализ подходов позволяет выделить основные направления развития классических методов выполнения и оптимизации сложных запросов к разнородным источникам информации.

В рамках доклада также представлен подход к оптимизации и приближенному выполнению нечетких запросов. Подход использует расширяемую алгебру, понятия качества и аддитивного ресурса, абстрактную модель стоимости и качества операций и понятие оптимальной стратегии приближенного выполнения при различных ограничениях на время вычислений и качество ответа.

Презентация доклада в формате pdf.

Видеозапись доклада.

Литература:

1. S. Agarwal, B. Mozafari, A. Panda, H. Milner, S. Madden, and I. Stoica. Blinkdb: queries with bounded errors and bounded response times on very large data. In Z. Hanzalek, H. Hartig, M. Castro, and M. F. Kaashoek, editors, EuroSys, pages 29–42. ACM, 2013.
2. S. Alsubaiee, Y. Altowim, H. Altwaijry, A. Behm, V. R. Borkar, Y. Bu, M. J. Carey, R. Grover, Z. Heilbron, Y.-S. Kim, C. Li, N. Onose, P. Pirzadeh, R. Vernica, and J. Wen. Asterix: An open source system for “big data“ management and analysis. PVLDB, 5(12):1898–1901, 2012.
3. B. Arai, G. Das, D. Gunopulos, and N. Koudas. Anytime measures for top-k algorithms. In C. Koch, J. Gehrke, M. N. Garofalakis, D. Srivastava, K. Aberer, A. Deshpande, D. Florescu, C. Y. Chan, V. Ganti, C.-C. Kanne, W. Klas, and E. J. Neuhold, editors, VLDB, pages 914–925. ACM, 2007.
4. P. Bizarro, N. Bruno, and D. J. DeWitt. Progressive parametric query optimization. Knowledge and Data Engineering, IEEE Transactions on, 21(4):582–594, 2009.
5. S. Chaudhuri, R. Ramakrishnan, and G. Weikum. Integrating DB and IR technologies: What is the sound of one hand clapping? In CIDR, pages 1–12, 2005.
6. U. Dayal, M. Castellanos, A. Simitsis, and K. Wilkinson. Data integration flows for business intelligence. In Kersten et al. [58], pages 1–11.
7. Deshpande, Z. G. Ives, and V. Raman. Adaptive query processing. Foundations and Trends in Databases, 1(1):1–140, 2007.
8. P. Fender and G. Moerkotte. Counter strike: generic top-down join enumeration for hypergraphs. Proceedings of the VLDB Endowment, 6(14):1822–1833, 2013.
9. Y. E. Ioannidis. Query optimization. ACM Comput. Surv., 28(1):121–123, 1996.
10. D. Kossmann and K. Stocker. Iterative dynamic programming: a new class of query optimization algorithms. ACM Trans. Database Syst., 25(1):43–82, 2000.
11. H. Lim, H. Herodotou, and S. Babu. Stubby: A transformation-based optimizer for mapreduce workflows. PVLDB, 5(11):1196–1207, 2012.
12. Trummer and C. Koch. Multi-objective parametric query optimization. Proceedings of the VLDB Endowment, 8(3), 2014.
13. A. Yarygina. Execution and optimization techniques for approximate queries in heterogeneous systems. Programming and Computer Software, 39(6):309–317, 2013.
14. B. Novikov, N. Vassilieva, and A. Yarygina. Querying big data. In Proceedings of the 13th International Conference on Computer Systems and Technologies, CompSysTech ’12, pages 1–10, New York, NY, USA, 2012.
15. A. Yarygina and B. Novikov. Optimizing resource allocation for approximate real-time query processing. Computer Science and Information Systems, 11:69–88, 2014.