Кэширование запросов к реляционной базе данных с использованием областей истинности

В данной статье предлагается новый метод кэширования запросов к реляционной базе данных для систем с центральным сервером и распределенными клиентами. Данные загружаются в клиентский кэш, основываясь на запросах, выполненных на сервере БД. Каждому запросу ставится в соответствие таблица – результат выполнения запроса. Эти запросы имеют специальный вид, называемый "универсальный реляционный запрос", основанный на трех базисных операциях реляционной алгеб- ры: селекции, проекции, естественном соединении (natural join). Следует отметить, что такая форма запроса наиболее близка к естественному языку и большинство запросов может быть записано в этом виде. Кроме того, эта форма записи позволяет анализировать корректность запроса, проверяя свойство соединения без потери информации (СБПИ). Последовательные запросы могут исполняться на клиенте, используя кэш, если удастся определить, что результаты искомого запроса полностью содержатся в кэше. Для осуществления такой проверки анализируются области истинности логических ограничений искомого запроса и запросов, результаты которых уже содержатся в кэше. Требуемые операции могут быть проведены аналитически, без необходимости дополнительных запросов к базе банных. Предложенный метод может быть использован для определения недостающих в кэше данных и последующего запроса только на эти данные. Для этого также используются аналитические вычисления, что является принципиальным отличием данной статьи от существующих технологий. Для этой цели в статье представлено четыре теоремы. В первой и третьей теореме получены условия, позволяющие определить наличие необходимых данных, а во второй и четвертой получены условия вычисления данных только с использованием кэша. Проблема актуализации данных не затрагивается в этой статье. Однако она может быть решена путем учета запросов на сервере и обновлении данных при помощи триггеров. Статья публикуется в авторской редакции.

реляционная база данных, кэш, область истинности

1. Zykin S., Poluyanov A., “Multidimensional data building using intermediate representations”, Administration problems, 5 (2013), 54–59.

2. Owens J. D. et al., “A survey of general-purpose computation on graphics hardware”, Computer Graphics Forum, 26, 2007, 80–113, http://www.blackwellsynergy.com/doi/pdf/10.1111/j.1467-8659.2007.01012.x.

3. Bakkum P., Skadron K., “Accelerating sql database operations on a gpu with cuda”, GPGPU, ACM, 425 (2010), 94–103, http://dblp.unitrier.de/db/conf/asplos/gpgpu2010.html.

4. Govindaraju N. K. et al., “Fast computation of database operations using graphics processors”, SIGMOD Conference, ACM, 2004, 215–226, http://dblp.unitrier.de/db/conf/sigmod/sigmod2004.html.

5. He B. et al., “Relational joins on graphics processors”, ACM, 2008, 511–524, http://dblp.uni-trier.de/db/conf/sigmod/sigmod2008.html.

6. Park C.-S., Kim M.-H., Lee Y.-J., “Usability-based caching of query results in olap systems”, Journal of Systems and Software, 68:2 (2003), 103–119.

7. Baralis E., Paraboschi S., Teniente E., “Materialized views selection in a multidimensional database”, Proceedings of the 23rd International Conference on Very Large Data Bases, VLDB ’97, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1997, 156–165,

8. http://dl.acm.org/citation.cfm?id=645923.671019.

9. Kalnis P., Papadias D., “Proxy-server architectures for olap.”, ACM, 2001, 367–378.

10. Afrati F. N., Li C., Mitra P., “Rewriting queries using views in the presence of arithmetic comparisons”, Theor. Comput. Sci., 368:1–2 (2006), 88–123.

11. Watanabe Y., Kitagawa H., “Query result caching for multiple eventdriven continuous queries”, Inf. Syst., 35:1 (2010), 94–110, http://dblp.unitrier.de/db/journals/is/is35.html#WatanabeK10.

12. Yates D. J. et al., “Data quality and query cost in pervasive sensing systems”, IEEE Computer Society, 2008, 195–205, http://dblp.unitrier.de/db/conf/percom/percom2008.html#YatesNKS08.

13. Andrade H. et al., “Active semantic caching to optimize multidimensional data analysis in parallel and distributed environments”, Parallel Computing, 33:7–8 (2007), 497–520,

14. http://dblp.uni-trier.de/db/journals/pc/pc33.html#AndradeKSS07.

15. Mershad K.W., Artail H., “Codisc: Collaborative and distributed semantic caching for maximizing cache effectiveness in wireless networks”, J. Parallel Distrib. Comput., 71:3 (2011), 495–511, http://dblp.uni-trier.de/db/journals/jpdc/jpdc71.html#MershadA11.

16. Noor Abbani H. A., “Protecting data flow anonymity in mobile ad hoc networks that employ cooperative caching”, Ad Hoc Networks, 26 (2015), 69–87.

17. Tansel Dokeroglu A. C., Ali Bayir Murat, “Robust heuristic algorithms for exploiting the common tasks of relational cloud database queries”, Applied Soft Computing.

18. Beran P. P. et al., “A multi-staged blackboard query optimization framework for worldspanning distributed database resources”, ICCS, 4, Procedia Computer Science (2011), 156–165, http://dblp.uni-trier.de/db/journals/procedia/procedia4.html#BeranMSV11.

19. Meij E. et al., “Mapping queries to the linking open data cloud: A case study using dbpedia”, J. Web Sem., 9:4 (2011), 418–433, http://dblp.unitrier.de/db/journals/ws/ws9.html#MeijBHHR11.

20. Aranda C. B. et al., “Federating queries in sparql 1.1: Syntax, semantics and evaluation”, J. Web Sem., 18:1 (2013), 1–17, http://dblp.unitrier.de/db/journals/ws/ws18.html#ArandaACP13.

21. Keller A. M., Basu J., “A predicate-based caching scheme for client-server database architectures”, VLDB J., 5:1 (1996), 35–47.

22. Shim J., Scheuermann P., Vingralek R., “Dynamic caching of query results for decision support systems”, SSDBM, 1999, 254–263.