research-article

Public Access

Answering Why-questions by Exemplars in Attributed Graphs

Authors:

Mohammad Hossein Namaki,

Shengqi YangAuthors Info & Claims

SIGMOD '19: Proceedings of the 2019 International Conference on Management of Data

Pages 1481 - 1498

https://doi.org/10.1145/3299869.3319890

Published: 25 June 2019 Publication History

Abstract

This paper studies the problem of \em answering Why-questions for graph pattern queries. Given a query Q, its answers $Q(G)$ in a graph G, and an exemplar $\E$ that describes desired answers, it aims to compute a query rewrite $Q'$, such that $Q'(G)$ incorporates relevant entities and excludes irrelevant ones wrt $\E$ under a closeness measure. (1) We characterize the problem by \em Q-Chase. It rewrites Q by applying a sequence of applicable operators guided by $\E$, and backtracks to derive optimal query rewrite. (2) We develop feasible Q-Chase-based algorithms, from anytime solutions to fixed-parameter approximations to compute query rewrites. These algorithms implement Q-Chase by detecting picky operators at run time, which discriminately enforce $\E$ to retain answers that are closer to exemplars, and effectively prune both operators and irrelevant matches, by consulting a cache of star patterns (called \em star views ). Using real-world graphs, we experimentally verify the efficiency and effectiveness of \qchase techniques and their applications.

References

[1]

Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases .Addison-Wesley.

Digital Library

[2]

Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. 2013. Fast exact shortest-path distance queries on large networks. In SIGMOD .

Digital Library

[3]

Günecs Alucc, Olaf Hartig, M Tamer Özsu, and Khuzaima Daudjee. 2014. Diversified stress testing of RDF data management systems. In ISWC .

Digital Library

[4]

Peter Buneman, Sanjeev Khanna, and Tan Wang-Chiew. 2001. Why and where: A characterization of data provenance. In ICDT .

Digital Library

[5]

Wenfei Fan, Jianzhong Li, Shuai Ma, Hongzhi Wang, and Yinghui Wu. 2010. Graph homomorphism revisited for graph matching. VLDB (2010), 1161--1172.

[6]

Wenfei Fan, Xin Wang, and Yinghui Wu. 2013. Diversified top-k graph pattern matching. VLDB (2013), 1510--1521.

Digital Library

[7]

Wenfei Fan, Yinghui Wu, and Jingbo Xu. 2016. Functional dependencies for graphs. In SIGMOD. 1843--1857.

Digital Library

[8]

Mario Arias Gallego, Javier D Fernández, Miguel A Mart'inez-Prieto, and Pablo de la Fuente. 2011. An empirical study of real-world SPARQL queries. USEWOD workshop .

[9]

Xinbo Gao, Bing Xiao, Dacheng Tao, and Xuelong Li. 2010. A survey of graph edit distance. Pattern Analysis and applications (2010), 113--129.

[10]

Michael Garey and David Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness .

Digital Library

[11]

Md Saiful Islam, Chengfei Liu, and Jianxin Li. 2015. Efficient answering of why-not questions in similar graph matching. TKDE (2015).

[12]

Md Saiful Islam, Chengfei Liu, and Rui Zhou. 2012. User feedback based query refinement by exploiting skyline operator. In ER .

[13]

Nandish Jayaram, Sidharth Goyal, and Chengkai Li. 2015a. VIIQ: auto-suggestion enabled visual interface for interactive graph query formulation. VLDB (2015), 1940--1943.

Digital Library

[14]

Nandish Jayaram, Arijit Khan, Chengkai Li, Xifeng Yan, and Ramez Elmasri. 2015b. Querying knowledge graphs by example entity tuples. TKDE (2015), 2797--2811.

Digital Library

[15]

Gjergji Kasneci, Fabian M Suchanek, Georgiana Ifrim, Maya Ramanath, and Gerhard Weikum. 2008. Naga: Searching and ranking knowledge. In ICDE .

Digital Library

[16]

Samir Khuller, Anna Moss, and Joseph Seffi Naor. 1999. The budgeted maximum coverage problem. Inform. Process. Lett., Vol. 70, 1 (1999), 39--45.

Digital Library

[17]

Phokion G Kolaitis and Madhukar N Thakur. 1994. Logical definability of NP optimization problems. Information and Computation (1994).

Digital Library

[18]

Dániel Marx. 2008. Parameterized complexity and approximation algorithms. Comput. J., Vol. 51, 1 (2008), 60--78.

Digital Library

[19]

Alexandra Meliou, Wolfgang Gatterbauer, Katherine F Moore, and Dan Suciu. 2009. Why so? or why no? functional causality for explaining query answers. arXiv preprint arXiv:0912.5340 (2009).

[20]

Mohamed Morsey, Jens Lehmann, Sören Auer, and Axel-Cyrille Ngonga Ngomo. 2011. DBpedia SPARQL benchmark--performance assessment with real queries on real data. In ISWC .

Digital Library

[21]

Davide Mottin, Francesco Bonchi, and Francesco Gullo. 2015. Graph query reformulation with diversity. In KDD .

[22]

Davide Mottin, Matteo Lissandrini, Yannis Velegrakis, and Themis Palpanas. 2014. Exemplar queries: Give me an example of what you need. VLDB (2014), 365--376.

Digital Library

[23]

Davide Mottin, Matteo Lissandrini, Yannis Velegrakis, and Themis Palpanas. 2016. Exemplar queries: a new way of searching. VLDB (2016), 741--765.

[24]

Mohammad Hossein Namaki, Yinghui Wu, Qi Song, Peng Lin, and Tingjian Ge. 2017. Discovering Graph Temporal Association Rules. In CIKM. 1697--1706.

Digital Library

[25]

Mohammad Hossein Namaki, Yinghui Wu, and Xin Zhang. 2018. GExp: Cost-aware Graph Exploration with Keywords. SIGMOD .

[26]

Alexandra Poulovassilis. 2018. Applications of Flexible Querying to Graph Data. Graph Data Management . 97--142.

[27]

L Rocach and O Maimon. 2005. Clustering methods Data mining and knowledge discovery handbook. Springer US (2005), 321.

[28]

Qi Song, Mohammad Hossein Namaki, and Yinghui Wu. 2019. Answering Why-Questions for Subgraph Queries in Multi-Attributed Graphs. In ICDE .

[29]

Yinglong Song, Huey Eng Chua, Sourav S Bhowmick, Byron Choi, and Shuigeng Zhou. 2018. BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks. In SIGMOD .

Digital Library

[30]

Wen Sun, Achille Fokoue, Kavitha Srinivas, Anastasios Kementsietsidis, Gang Hu, and Guotong Xie. 2015. Sqlgraph: An efficient relational-based property graph store. In SIGMOD .

Digital Library

[31]

Quoc Trung Tran and Chee-Yong Chan. 2010. How to conquer why-not questions. In SIGMOD .

Digital Library

[32]

Elena Vasilyeva, Maik Thiele, Christof Bornhövd, and Wolfgang Lehner. 2016. Answering “why empty” and “why so many?” queries in graph databases. J. Comput. System Sci., Vol. 82, 1 (2016).

Digital Library

[33]

Elena Vasilyeva, Maik Thiele, Adrian Mocan, and Wolfgang Lehner. 2015. Relaxation of subgraph queries delivering empty results. In SSDBM .

Digital Library

[34]

Meng Wang, Jun Liu, Bifan Wei, Siyu Yao, Hongwei Zeng, and Lei Shi. 2018. Answering why-not questions on SPARQL queries. KAIS (2018).

Digital Library

[35]

Mohamed Yahya, Klaus Berberich, Maya Ramanath, and Gerhard Weikum. 2016. Exploratory querying of extended knowledge graphs. VLDB (2016), 1521--1524.

Digital Library

[36]

Shengqi Yang, Fangqiu Han, Yinghui Wu, and Xifeng Yan. 2016. Fast top-k search in knowledge graphs. In ICDE .

[37]

Shengqi Yang, Yinghui Wu, Huan Sun, and Xifeng Yan. 2014. Schemaless and structureless graph querying. VLDB (2014), 565--576.

Digital Library

[38]

Lei Zou, M Tamer Özsu, Lei Chen, Xuchuan Shen, Ruizhe Huang, and Dongyan Zhao. 2014. gStore: a graph-based SPARQL query engine. VLDBJ, Vol. 23, 4 (2014), 565--590.

Digital Library

Cited By

Zong CDong ZYang XWang BZhu HQiu TZhu R(2024)Exploring Optimal Parameters for Expected Results on Radius-Bounded k-Core Queries2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00183(2312-2324)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00183
Ye SXu XWang YFu T(2023)Efficient Complex Aggregate Queries with Accuracy Guarantee Based on Execution Cost Model over Knowledge GraphsMathematics10.3390/math1118390811:18(3908)Online publication date: 14-Sep-2023
https://doi.org/10.3390/math11183908
B. BRani KNeog A(2022)Finding Multidimensional Constraint Reachable Paths for Attributed GraphsICST Transactions on Scalable Information Systems10.4108/eetsis.v9i4.2581(e2)Online publication date: 22-Aug-2022
https://doi.org/10.4108/eetsis.v9i4.2581
Show More Cited By

Recommendations

NAVIGATE: Explainable Visual Graph Exploration by Examples
SIGMOD '19: Proceedings of the 2019 International Conference on Management of Data

We demonstrate NAVIGATE, an explai\underlineNA ble query engine for \underlineVI sual \underlineG r\underlineA ph explora\underlineT ion by \underlineE xamples. NAVIGATE interleavesquery rewriting and query answering to help users (1) search graphs \...
Answering why-not and why questions on reverse top-k queries

Why-not and why questions can be posed by database users to seek clarifications on unexpected query results. Specifically, why-not questions aim to explain why certain expected tuples are absent from the query results, while why questions try to clarify ...
A Hybrid Approach to Answering Why-Not Questions on Relational Query Results
Special Issue on Provenance, Data and Information Quality

In analyzing and debugging data transformations, or more specifically relational queries, a subproblem is to understand why some data are not part of the query result. This problem has recently been addressed from different perspectives for various ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '19: Proceedings of the 2019 International Conference on Management of Data

June 2019

2106 pages

ISBN:9781450356435

DOI:10.1145/3299869

General Chairs:
Peter Boncz
CWI & Vrije Universiteit Amsterdam, The Netherlands
,
Stefan Manegold
CWI & Universiteit Leiden, The Netherlands
,
Program Chairs:
Anastasia Ailamaki
EPFL, Switzerland
,
Amol Deshpande
University of Maryland, USA
,
Tim Kraska
MIT, USA

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 June 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

SIGMOD/PODS '19

Sponsor:

SIGMOD

SIGMOD/PODS '19: International Conference on Management of Data

June 30 - July 5, 2019

Amsterdam, Netherlands

Acceptance Rates

SIGMOD '19 Paper Acceptance Rate 88 of 430 submissions, 20%;

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
945
Total Downloads

Downloads (Last 12 months)105
Downloads (Last 6 weeks)17

Reflects downloads up to 06 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zong CDong ZYang XWang BZhu HQiu TZhu R(2024)Exploring Optimal Parameters for Expected Results on Radius-Bounded k-Core Queries2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00183(2312-2324)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00183
Ye SXu XWang YFu T(2023)Efficient Complex Aggregate Queries with Accuracy Guarantee Based on Execution Cost Model over Knowledge GraphsMathematics10.3390/math1118390811:18(3908)Online publication date: 14-Sep-2023
https://doi.org/10.3390/math11183908
B. BRani KNeog A(2022)Finding Multidimensional Constraint Reachable Paths for Attributed GraphsICST Transactions on Scalable Information Systems10.4108/eetsis.v9i4.2581(e2)Online publication date: 22-Aug-2022
https://doi.org/10.4108/eetsis.v9i4.2581
Wang MMa HDaundkar AGuan SBian YSehirlioglu AWu YAl Hasan MXiong L(2022)CRUX: Crowdsourced Materials Science Resource and Workflow ExplorationProceedings of the 31st ACM International Conference on Information & Knowledge Management10.1145/3511808.3557194(5014-5018)Online publication date: 17-Oct-2022
https://dl.acm.org/doi/10.1145/3511808.3557194
Ma HGuan SToomey CWu YSelcuk Candan KLiu HAkoglu LLuna Dong XTang J(2022)Diversified Subgraph Query Generation with Group FairnessProceedings of the Fifteenth ACM International Conference on Web Search and Data Mining10.1145/3488560.3498525(686-694)Online publication date: 11-Feb-2022
https://dl.acm.org/doi/10.1145/3488560.3498525
Song QNamaki MLin PWu Y(2022)Answering Why-Questions for Subgraph QueriesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.304643634:10(4636-4649)Online publication date: 1-Oct-2022
https://doi.org/10.1109/TKDE.2020.3046436
Ma HGuan SWang MChang YWu Y(2022)Subgraph Query Generation with Fairness and Diversity Constraints2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00278(3106-3118)Online publication date: May-2022
https://doi.org/10.1109/ICDE53745.2022.00278
Fu TXu XWang Y(2022)An Execution Cost Model for Aggregate Queries over Knowledge Graphs2021 Ninth International Conference on Advanced Cloud and Big Data (CBD)10.1109/CBD54617.2021.00028(113-120)Online publication date: Mar-2022
https://doi.org/10.1109/CBD54617.2021.00028
Wang YXu XHong QJin JWu T(2022)Top-k star queries on knowledge graphs through semantic-aware bounding match scoresKnowledge-Based Systems10.1016/j.knosys.2020.106655213:COnline publication date: 23-Apr-2022
https://dl.acm.org/doi/10.1016/j.knosys.2020.106655
Rani AGoyal NGadia S(2022)Social data provenance framework based on zero-information loss graph databaseSocial Network Analysis and Mining10.1007/s13278-022-00889-612:1Online publication date: 3-Jul-2022
https://doi.org/10.1007/s13278-022-00889-6
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents