{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,27]],"date-time":"2025-06-27T18:23:50Z","timestamp":1751048630913},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:p>This paper proposes a class of graph rules for deducing associations between entities, referred to as Graph Rules with Oracles and denoted by GROs. As opposed to previous graph rules, GROs support oracle functions to import (a) external knowledge, and (b) internal computations such as aggregate operators and machine learning predicates, and so on. Moreover, the semantics of GROs are defined in terms of pivoted dual simulation, in contrast to the subgraph isomorphism. We show how GROs can be used to predict links and catch anomalies, among other things. We formalize the association deduction problem with GROs in terms of the chase, and prove their Church-Rosser property. We show that both the deduction and incremental deduction problems with GROs are in PTIME, as opposed to the intractability of their counterparts with prior graph rules. We also provide sequential and parallel algorithms for association deduction and incremental deduction. Using real-life and synthetic graphs, we experimentally verify the effectiveness, scalability, and efficiency of the algorithms.<\/jats:p>","DOI":"10.14778\/3654621.3654641","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T22:21:08Z","timestamp":1717107668000},"page":"1775-1787","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Extending Graph Rules with Oracles"],"prefix":"10.14778","volume":"17","author":[{"given":"Xueli","family":"Liu","sequence":"first","affiliation":[{"name":"Tianjin University, China"}]},{"given":"Bowen","family":"Dong","sequence":"additional","affiliation":[{"name":"Tianjin University, China"}]},{"given":"Wenzhi","family":"Fu","sequence":"additional","affiliation":[{"name":"University of Edinburgh, UK"}]},{"given":"Nannan","family":"Wu","sequence":"additional","affiliation":[{"name":"Tianjin University, China"}]},{"given":"Xin","family":"Wang","sequence":"additional","affiliation":[{"name":"Tianjin University, China"}]},{"given":"Wenjun","family":"Wang","sequence":"additional","affiliation":[{"name":"Tianjin University, China"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Dbpedia. http:\/\/wiki.dbpedia.org\/Datasets."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/551350"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1350-7"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623619"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00075"},{"key":"e_1_2_1_6_1","volume-title":"AMW","author":"Cort\u00e9s-Calabuig A.","year":"2012","unstructured":"A. Cort\u00e9s-Calabuig and J. Paredaens. Semantics of constraints in RDFS. In AMW, 2012."},{"key":"e_1_2_1_7_1","first-page":"715","volume-title":"SIGMOD","author":"Fan G.","year":"2020","unstructured":"G. Fan, W. Fan, Y. Li, P. Lu, C. Tian, and J. Zhou. Extending graph patterns with conditions. In SIGMOD, pages 715--729. ACM, 2020."},{"key":"e_1_2_1_8_1","volume-title":"Conditional functional dependencies for capturing data inconsistencies. TODS, 33(1)","author":"Fan W.","year":"2008","unstructured":"W. Fan, F. Geerts, X. Jia, and A. Kementsietsidis. Conditional functional dependencies for capturing data inconsistencies. TODS, 33(1), 2008."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407795"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920986"},{"key":"e_1_2_1_11_1","volume-title":"SIGMOD","author":"Fan W.","year":"2018","unstructured":"W. Fan, X. Liu, P. Lu, C. Hu, and Y. Cao. Discovering graph functional dependencies. In SIGMOD, 2018."},{"key":"e_1_2_1_12_1","volume-title":"SIGMOD","author":"Fan W.","year":"2018","unstructured":"W. Fan, X. Liu, P. Lu, and C. Tian. Catching numeric inconsistencies in graphs. In SIGMOD, 2018."},{"key":"e_1_2_1_13_1","volume-title":"PODS","author":"Fan W.","year":"2017","unstructured":"W. Fan and P. Lu. Dependencies for graphs. In PODS, 2017."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3317315.3317318"},{"key":"e_1_2_1_15_1","first-page":"459","volume-title":"SIGMOD","author":"Fan W.","year":"2021","unstructured":"W. Fan, C. Tian, R. Xu, Q. Yin, W. Yu, and J. Zhou. Incrementalizing graph algorithms. In SIGMOD, pages 459--471, 2021."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2489791"},{"key":"e_1_2_1_17_1","volume-title":"PVLDB","author":"Fan W.","year":"2014","unstructured":"W. Fan, X. Wang, and Y. Wu. Distributed graph simulation: Impossibility and possibility. PVLDB, 2014."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824048"},{"key":"e_1_2_1_19_1","volume-title":"SIGMOD","author":"Fan W.","year":"2016","unstructured":"W. Fan, Y. Wu, and J. Xu. Adding counting quantifiers to graph patterns. In SIGMOD, 2016."},{"key":"e_1_2_1_20_1","volume-title":"SIGMOD","author":"Fan W.","year":"2016","unstructured":"W. Fan, Y. Wu, and J. Xu. Functional dependencies for graphs. In SIGMOD, 2016."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035942"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3282488"},{"key":"e_1_2_1_23_1","first-page":"403","volume-title":"ICBD","author":"Fard A.","year":"2013","unstructured":"A. Fard, M. U. Nisar, L. Ramaswamy, J. A. Miller, and M. Saltz. A distributed vertex-centric approach for pattern matching in massive graphs. In ICBD, pages 403--411. IEEE Computer Society, 2013."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.aau7224"},{"key":"e_1_2_1_25_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M.","year":"1979","unstructured":"M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2014.05.181"},{"key":"e_1_2_1_27_1","first-page":"453","volume-title":"FCS","author":"Henzinger M. R.","year":"1995","unstructured":"M. R. Henzinger, T. A. Henzinger, and P. W. Kopke. Computing simulations on finite and infinite graphs. In FCS, pages 453--462, 1995."},{"key":"e_1_2_1_28_1","unstructured":"IMDb. http:\/\/www.imdb.com\/stats\/search\/."},{"key":"e_1_2_1_29_1","volume-title":"NeurIPS","author":"Kazemi S. M.","year":"2018","unstructured":"S. M. Kazemi and D. Poole. Simple embedding for link prediction in knowledge graphs. In NeurIPS, 2018."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2011.11.004"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90192-K"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528937"},{"issue":"1","key":"e_1_2_1_33_1","article-title":"Capturing topology in graph pattern matching","volume":"39","author":"Ma S.","year":"2014","unstructured":"S. Ma, Y. Cao, W. Fan, J. Huai, and T. Wo. Strong simulation: Capturing topology in graph pattern matching. ACM Trans. on Database Systems, 39(1), 2014.","journal-title":"ACM Trans. on Database Systems"},{"key":"e_1_2_1_34_1","first-page":"949","volume-title":"WWW","author":"Ma S.","year":"2012","unstructured":"S. Ma, Y. Cao, J. Huai, and T. Wo. Distributed graph pattern matching. In WWW, pages 949--958. ACM, 2012."},{"key":"e_1_2_1_35_1","volume-title":"Prentice Hall","author":"Milner R.","year":"1989","unstructured":"R. Milner. Communication and Concurrency. Prentice Hall, 1989."},{"key":"e_1_2_1_36_1","volume-title":"SIGMOD","author":"Myoungji H.","year":"2019","unstructured":"H. Myoungji, K. Hyunjoon, G. Geonmo, P. Kunsoo, and H. Wook-Shin. Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together. In SIGMOD, 2019."},{"key":"e_1_2_1_37_1","volume-title":"SIGMOD","author":"Sadri F.","year":"1980","unstructured":"F. Sadri and J. D. Ullman. The interaction between functional dependencies and template dependencies. In SIGMOD, 1980."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2008.02.001"},{"key":"e_1_2_1_39_1","volume-title":"VLDB 2015 Workshops","volume":"9579","author":"Sch\u00e4tzle A.","year":"2015","unstructured":"A. Sch\u00e4tzle, M. Przyjaciel-Zablocki, T. Berberich, and G. Lausen. S2X: graph-parallel querying of RDF with graphx. In VLDB 2015 Workshops, volume 9579 of Lecture Notes in Computer Science, pages 155--168. Springer, 2015."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242667"},{"key":"e_1_2_1_41_1","volume-title":"ICML","author":"Trouillon T.","year":"2016","unstructured":"T. Trouillon, J. Welbl, S. Riedel, \u00c9. Gaussier, and G. Bouchard. Complex embeddings for simple link prediction. In ICML, 2016."},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1016\/j.ins.2018.01.018","article-title":"Parallel algorithms for flexible pattern matching on big graphs","volume":"437","author":"Wang H.","year":"2018","unstructured":"H. Wang, N. Li, J. Li, and H. Gao. Parallel algorithms for flexible pattern matching on big graphs. Inf. Sci., 436--437:418--440, 2018.","journal-title":"Inf. Sci., 436--"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/645505.656434"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3654621.3654641","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T22:22:16Z","timestamp":1717107736000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3654621.3654641"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3]]},"references-count":43,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["10.14778\/3654621.3654641"],"URL":"https:\/\/doi.org\/10.14778\/3654621.3654641","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,3]]},"assertion":[{"value":"2024-05-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}