Truth space method for caching database queries

S. V. Mosin ; S. V. Zykin

Modelirovanie i analiz informacionnyh sistem, Tome 22 (2015) no. 2, pp. 248-258.

Résumé

We propose a new method of client-side data caching for relational databases with a central server and distant clients. Data are loaded into the client cache based on queries executed on the server. Every query has the corresponding DB table — the result of the query execution. These queries have a special form called “universal relational query” based on three fundamental Relational Algebra operations: \linebreak selection, projection and natural join. We have to mention that such a form is the closest one to the natural language and the majority of database search queries can be expressed in this way. Besides, this form allows us to analyze query correctness by checking lossless join property. A subsequent query may be executed in a client's local cache if we can determine that the query result is entirely contained in the cache. For this we compare truth spaces of the logical restrictions in a new user's query and the results of the queries execution in the cache. Such a comparison can be performed analytically , without need in additional Database queries. This method may be used to define lacking data in the cache and execute the query on the server only for these data. To do this the analytical approach is also used, what distinguishes our paper from the existing technologies. We propose four theorems for testing the required conditions. The first and the third theorems conditions allow us to define the existence of required data in cache. The second and the fourth theorems state conditions to execute queries with cache only. The problem of cache data actualizations is not discussed in this paper. However, it can be solved by cataloging queries on the server and their serving by triggers in background mode. The article is published in the author's wording.

Détail

Keywords: relational databases, caching, truth space.

Bibliographie

[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:1 (2007), 80–113 http://www.blackwell-synergy.com/doi/pdf/10.1111/j.1467-8659.2007.01012.x | DOI

[3] Bakkum P., Skadron K., “Accelerating SQL Database Operations on a GPU with CUDA”, Proceedings of the Third Workshop on General-Purpose Computation on Graphics Processing Units, GPGPU'2010, ACM International Conference Proceeding Series, 425, eds. D. R. Kaeli, M. Leeser, ACM, 2010, 94–103 http://dblp.uni-trier.de/db/conf/asplos/gpgpu2010.html

[4] Govindaraju N. K. et al., “Fast computation of database operations using graphics processors”, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, SIGMOD'2004, 215–226 http://dblp.uni-trier.de/db/conf/sigmod/sigmod2004.html

[5] He B. et al., “Relational joins on graphics processors”, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, SIGMOD'2008, 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 | DOI

[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 (San Francisco, CA, USA, 1997), Morgan Kaufmann Publishers Inc., 156–165 http://dl.acm.org/citation.cfm?id=645923.671019

[8] Kalnis P., Papadias D., “Proxy-server architectures for olap”, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, SIGMOD'2001, 2001, 367–378 | DOI

[9] 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 | DOI | MR | Zbl

[10] Watanabe Y., Kitagawa H., “Query result caching for multiple event-driven continuous queries”, Inf. Syst., 35:1 (2010), 94–110 http://dblp.uni-trier.de/db/journals/is/is35.html#WatanabeK10 | DOI

[11] Yates D. J. et al., “Data quality and query cost in pervasive sensing systems”, IEEE International Conference on Pervasive Computing and Communications (PerCom) (2008), 195–205 http://dblp.uni-trier.de/db/conf/percom/percom2008.html#YatesNKS08

[12] 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 http://dblp.uni-trier.de/db/journals/pc/pc33.html#AndradeKSS07 | DOI

[13] 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 | DOI | Zbl

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

[15] Tansel Dokeroglu A. C., Ali Bayir Murat, “Robust heuristic algorithms for exploiting the common tasks of relational cloud database queries”, Applied Soft Computing, 30 (2015), 72–82 | DOI

[16] Beran P. P. et al., “A multi-staged blackboard query optimization framework for world-spanning distributed database resources”, Proceedings of the International Conference on Computational Science, ICCS 2011, Procedia Computer Science, 4, 2011, 156–165 http://dblp.uni-trier.de/db/journals/procedia/procedia4.html#BeranMSV11 | DOI

[17] 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.uni-trier.de/db/journals/ws/ws9.html#MeijBHHR11

[18] 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.uni-trier.de/db/journals/ws/ws18.html#ArandaACP13

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

[20] Shim J., Scheuermann P., Vingralek R., “Dynamic caching of query results for decision support systems”, Proc. of the SSDBM Conference (1999), 254–263