Диссертация (1149731), страница 25
Текст из файла (страница 25)
Базовая реализациябинарной операции читает объекты из входных потоков, вызывает функциюпредиката для каждой пары, и передает в выходной поток новые объекты соценками, которые возвращает функция предиката.Псевдокод 9 описывает взаимодействие базовой реализации бинарной операции с функцией предиката:Псевдокод 9 Бинарная операцияInput: Параметры вызова операции pars, потоки аргументов операции arg1,arg2.Output: Поток с результатом выполнения операции out.pred=InitilaizePredicate(pars)out=InitilaizeOutput()loopobj1 = arg1.get()loopobj2 = arg2.get()obj = pred.eval(obj1,obj2)if obj is not empty then out.put(obj)end ifend loopend loopТаким образом, расширяемость алгебры новыми бинарными операциями может быть основана на реализации новых функций предиката.
Важноотметить, что могут быть использованы базовые конфигурируемые реализации таких функций: например, функция предиката, сравнивающая объекты построковым атрибутам, принимает в качестве параметров названия атрибутов ифункции сравнения, например, точное совпадение, расстояние Левенштейна.Новые бинарные операции также могут быть построены без использованияфункции предиката, и просто реализовывать базовый интерфейс. Это особенноважно в случае реализации приближенных алгоритмов для бинарных операций.Ядро системы может быть расширено другими конфигурируемыми базовымиреализациями бинарных операций, например, для построения приближенныхалгоритмов на основе неполного перебора пар декартова произведения аргументов.1355.5.
Основные результатыВ главе определена архитектура расширяемой системы оптимизации и контролируемого приближенного выполнения декларативных сценариев обработкиданных. Статья [16] содержит описание представленной в главе архитектуры.136ЗаключениеОсновные результаты работы:∙ Подготовлен обзор, систематизирующий существующие методы оптимизации и приближенного выполнения декларативных сценариев нечеткойаналитической обработки данных;∙ Предложена система понятий, составляющих теоретическую модель, формализующую оптимизацию и контролируемое приближенное выполнениедекларативных запросов, на основе модели стоимости и качества операций;∙ Разработана математическая модель распределения ресурсов среди операций в плане выполнения запроса и решена задача выбора оптимальногораспределения;∙ Разработан приближенный алгоритм распределения ограниченного количества вычислительных ресурсов среди операций в плане выполнения запроса на основе моделей качества;∙ Разработаны алгоритмы бикритериальной оптимизации запросов, ориентированные на специфические в контексте приближенного выполнения,ограничения на количество вычислительных ресурсов и качество ответа;∙ Реализована экспериментальная среда для анализа разработанных алгоритмов распределения ресурсов и оптимизации запросов, допускающихприближенное выполнение.Разработанные теоретические модели, алгоритмы и экспериментальнуюсреду рекомендуется использовать для реализации прототипов прикладных систем анализа больших данных в таких предметных областях как финансовыймониторинг, социологический и экономический анализ.137В перспективах дальнейшей разработки темы целесообразно исследоватьприменимость предложенных моделей и методов для других классов моделейданных, например, для графов.138Библиография[1] Gray, J.
The next database revolution / Jim Gray // Proceedings of the 2004ACM SIGMOD international conference on Management of data / ACM. —2004. — P. 1–4.[2] Big data: The next frontier for innovation, competition, and productivity /James Manyika, Michael Chui, Brad Brown et al. — 2011.[3] Dean, J. Mapreduce: Simplified data processing on large clusters /Jeffrey Dean, Sanjay Ghemawat // OSDI. — USENIX Association, 2004.
—P. 137–150.[4] Asterix: an open source system for big data management and analysis /Sattam Alsubaiee, Yasser Altowim, Hotham Altwaijry et al. // Proceedingsof the VLDB Endowment. — 2012. — Vol. 5, no. 12. — P. 1898–1901.[5] Bruno, N. Continuous cloud-scale query optimization and processing /Nicolas Bruno, Sapna Jain, Jingren Zhou // PVLDB. — 2013.
— Vol. 6,no. 11. — P. 961–972.[6] Scope: parallel databases meet mapreduce / Jingren Zhou, Nicolas Bruno,Ming-Chuan Wu et al. // The VLDB Journal—The International Journal onVery Large Data Bases. — 2012. — Vol. 21, no. 5. — P. 611–636.[7] Chaudhuri, S. Integrating db and ir technologies: What is the soundof one hand clapping? / Surajit Chaudhuri, Raghu Ramakrishnan,Gerhard Weikum // CIDR. — 2005.
— P. 1–12.[8] A multi-similarity algebra / S. Adali, P. Bonatti, M. L. Sapino,V. S. Subrahmanian // SIGMOD Rec. — 1998. — Vol. 27. — P. 402–413.139[9] Montesi, D. A similarity based relational algebra for web and multimediadata / Danilo Montesi, Alberto Trombetta, Peter A. Dearnley // Inf. Process.Manage. — 2003. — Vol. 39, no.
2. — P. 307–322.[10] Imprecision and user preferences in multimedia queries: A genericalgebraic approach / Paolo Ciaccia, Danilo Montesi, Wilma Penzo,Alberto Trombetta // Foundations of Information and Knowledge Systems. —Springer, 2000. — P. 50–71.[11] Schmitt, I. Similarity relational calculus and its reduction to a similarityalgebra / Ingo Schmitt, Nadine Schulz // FoIKS / Ed. by Dietmar Seipel,Jose Maria Turull Torres. — Vol. 2942 of Lecture Notes in Computer Science.
—Springer, 2004. — P. 252–272.[12] Atnafu, S. Similarity-based algebra for multimedia database systems /Solomon Atnafu, Lionel Brunie, Harald Kosch // ADC. — 2001. — P. 115–122.[13] Budı́ková, P. Query language for complex similarity queries / Petra Budı́ková,Michal Batko, Pavel Zezula // ADBIS / Ed. by Tadeusz Morzy, Theo Härder,Robert Wrembel.
— Vol. 7503 of Lecture Notes in Computer Science. —Springer, 2012. — P. 85–98.[14] Blinkdb: queries with bounded errors and bounded response times on verylarge data / Sameer Agarwal, Barzan Mozafari, Aurojit Panda et al. //EuroSys / Ed. by Zdenek Hanzálek, Hermann Härtig, Miguel Castro,M.
Frans Kaashoek. — ACM, 2013. — P. 29–42.[15] Sidirourgos, L. Sciborq: Scientific data management with bounds on runtimeand quality / Lefteris Sidirourgos, Martin L. Kersten, Peter A. Boncz //CIDR. — 2011. — P. 296–301.[16] Yarygina, A. A prototype architecture for approximate real-time queryoptimization and processing / Anna Yarygina, Boris Novikov // The TenthSpring Researchers Colloquium on Databases and Information Systems2014. — 2014. — P. 24–31.140[17] Yarygina, A.
Optimizing resource allocation for approximate real-time queryprocessing / A. Yarygina, B. Novikov // Computer Science and InformationSystems. — 2014. — Vol. 11. — P. 69–88.[18] Novikov, B. Querying big data / Boris Novikov, Natalia Vassilieva,Anna Yarygina // Proceedings of the 13th International Conference onComputer Systems and Technologies. — CompSysTech ’12. — New York, NY,USA: ACM, 2012. — P. 1–10.[19] Yarygina, A.
Optimizing the resource allocation for approximate queryprocessing / Anna Yarygina, Boris Novikov // Advances in Databasesand Information Systems / Ed. by Tadeusz Morzy, Theo Harder,Robert Wrembel. — Vol. 186 of Advances in Databases and InformationSystems. — Poznan, Poland: Springer Berlin Heidelberg, 2012. — P.
297–308.[20] Dolmatova, O. Cost models for approximate query evaluation algorithms /Oxana Dolmatova, Anna Yarygina, Boris Novikov // Databases andInformation Systems. Tenth International Baltic Conference on Databases andInformation Systems. Local Proceedings, Materials of Doctoral Consortium. /Ed. by A. Caplinskas, G. Dzemyda, A. Lupeikiene, O. Vasilecas. — Vilnius:Zara, 2012.
— P. 20–28.[21] Новиков, Б. А. Задачи оптимизации запросов в распределенной среденеоднородных информационных ресурсов / Борис Асенович Новиков, Анна Сергеена Ярыгина // Математика, экономика, менеджмент: 100 лет содня рождения Л.В. Канторовича / Ed. by Иосиф Владимирович Романовский. — Санкт-Петербургский гос. университет, 2012. — 7–9 февраля. —P.
57–59.[22] Ярыгина, А. Методы выполнения и оптимизации приближенных запросовв неоднородных системах / А. Ярыгина // Программирование. — 2013. —Vol. 39. — P. 33–44.[23] Yarygina, A. Bi-objective optimization for approximate query evaluation /Anna Yarygina, Boris Novikov // 19th East European Conference on Advancesin Databases and Information Systems and Associated Satellite Events(ADBIS 2015) / Ed.
by Tadeusz Morzy, Patrick Valduriez, Ladjel Bellatreche141et al. — Communications in Computer and Information Science (CCIS). —Springer Berlin Heidelberg, 2015. — P. 153–161.[24] Yarygina, A. Processing complex similarity queries: A systematic approach /Anna Yarygina, Boris Novikov, Natalia Vassilieva // ABDIS 2011 ResearchCommunications: Proceedings II of the 5th East-European Conference onAdvances in Databases and Information Systems 20 - 23 September 2011,Vienna / Ed. by Maria Bielikova, Johann Eder, A Min Tjoa. — AustrianComputer Society, 2011. — September.
— P. 212–221.[25] Yarygina, A. Execution and optimization techniques for approximate queriesin heterogeneous systems / A. Yarygina // Programming and ComputerSoftware. — 2013. — Vol. 39, no. 6. — P. 309–317.[26] Graefe, G. Query evaluation techniques for large databases / Goetz Graefe //ACM Comput. Surv. — 1993. — Vol. 25, no. 2. — P.
73–170.[27] Codd, E. F. A relational model of data for large shared data banks /E. F. Codd // Commun. ACM. — 1970. — Vol. 13, no. 6. — P. 377–387.[28] Darwen, H. The third manifesto / Hugh Darwen, C. J. Date // SIGMODRecord. — 1995. — Vol. 24, no. 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
