Abstract
The sheer volume as well as the schema complexity of today’s graph databases impede the users in formulating queries against these databases and often cause queries to “fail” by delivering empty answers. To support users in such situations, the concept of differential queries can be used to bridge the gap between an unexpected result (e.g. an empty result set) and the query intention of users. These queries deliver missing parts of a query graph and, therefore, work with such scenarios that require users to specify a query graph. Based on the discovered information about a missing query subgraph, users may understand which vertices and edges are the reasons for queries that unexpectedly return empty answers, and thus can reformulate the queries if needed. A study showed that the result sets of differential queries are often too large to be manually introspected by users and thus a reduction of the number of results and their ranking is required. To address these issues, we extend the concept of differential queries and introduce top-k differential queries that calculate the ranking based on users’ preferences and therefore significantly support the users’ understanding of query database management systems. The idea consists of assigning relevance weights to vertices or edges of a query graph by users that steer the graph search and are used in the scoring function for top-k differential results. Along with the novel concept of the top-k differential queries, we further propose a strategy for propagating relevance weights and we model the search along the most relevant paths.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Amer-Yahia, S., Koudas, N., Marian, A., Srivastava, D., Toman, D.: Structure and Content Scoring for XML. Proc. of VLDB Endow., 361–372 (2005)
Bornhövd, C., Kubis, R., Lehner, W., Voigt, H., Werner, H.: Flexible Information Management, Exploration and Analysis in SAP HANA. In: DATA, pp. 15–28 (2012)
Chapman, A., Jagadish, H.V.: Why not? In: Proc. of ACM SIGMOD, pp. 523–534. ACM, New York (2009)
Fan, W., Wang, X., Wu, Y.: Diversified top-k graph pattern matching. Proc. of VLDB Endow. 6, 1510–1521 (2013)
Gupta, M., Gao, J., Yan, X., Cam, H., Han, J.: Top-k interesting subgraph discovery in information networks. In: Proc. of ICDE, pp. 820–831. IEEE (2014)
Huang, J., Chen, T., Doan, A., Naughton, J.F.: On the provenance of non-answers to queries over extracted data. Proc. of VLDB Endow. 1, 736–747 (2008)
Kasneci, G., Suchanek, F., Ifrim, G., Ramanath, M., Weikum, G.: Naga: Searching and ranking knowledge. In: Proc. of ICDE, pp. 953–962. IEEE (2008)
McGregor, J.J.: Backtrack search algorithms and the maximal common subgraph problem. Software: Practice and Experience 12(1), 23–34 (1982)
Melnik, S., Garcia-Molina, H., Rahm, E.: Similarity flooding: A versatile graph matching algorithm and its application to schema matching. In: Proc. of ICDE, pp. 117–128. IEEE (2002)
Mottin, D., Marascu, A., Roy, S.B., Das, G., Palpanas, T., Velegrakis, Y.: A probabilistic optimization framework for the empty-answer problem. Proc. of VLDB Endow. 6, 1762–1773 (2013)
Prud’hommeaux, E., Seaborne, A.: SPARQL Query Language for RDF. W3C Recommendation (2008)
Rodriguez, M.A., Neubauer, P.: Constructions from dots and lines. Bulletin of the American Society for Inf. Science and Technology 36(6), 35–41 (2010)
Rudolf, M., Paradies, M., Bornhövd, C., Lehner, W.: The Graph Story of the SAP HANA Database. In: BTW, pp. 403–420 (2013)
Tran, Q.T., Chan, C.Y.: How to conquer why-not questions. In: Proc of ACM SIGMOD, pp. 15–26. ACM, New York (2010)
Vasilyeva, E., Thiele, M., Bornhövd, C., Lehner, W.: GraphMCS: Discover the Unknown in Large Data Graphs. In: EDBT/ICDT Workshops, pp. 200–207 (2014)
Zhu, Y., Qin, L., Yu, J.X., Cheng, H.: Finding top-k similar graphs in graph databases. In: Proc. of EDBT, pp. 456–467. ACM (2012)
Zou, L., Chen, L., Lu, Y.: Top-k subgraph matching query in a large graph. In: Proc. of the ACM First Ph.D. Workshop in CIKM, pp. 139–146. ACM (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Vasilyeva, E., Thiele, M., Bornhövd, C., Lehner, W. (2014). Top-k Differential Queries in Graph Databases. In: Manolopoulos, Y., Trajcevski, G., Kon-Popovska, M. (eds) Advances in Databases and Information Systems. ADBIS 2014. Lecture Notes in Computer Science, vol 8716. Springer, Cham. https://doi.org/10.1007/978-3-319-10933-6_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-10933-6_9
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-10932-9
Online ISBN: 978-3-319-10933-6
eBook Packages: Computer ScienceComputer Science (R0)