{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,6]],"date-time":"2026-11-06T20:42:58Z","timestamp":1793997778640,"version":"4.8.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,2,13]],"date-time":"2019-02-13T00:00:00Z","timestamp":1550016000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100012166","name":"973 Program","doi-asserted-by":"crossref","award":["2014CB340302"],"award-info":[{"award-number":["2014CB340302"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100015639","name":"Beijing Advanced Innovation Center for Big Data and Brain Computing","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100015639","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Foundation for Innovative Research Groups of NSFC"},{"name":"Joint Lab between Edinburgh and Huawei"},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61421003"],"award-info":[{"award-number":["61421003"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/M025268\/1"],"award-info":[{"award-number":["EP\/M025268\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ERC","award":["652976"],"award-info":[{"award-number":["652976"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2019,6,30]]},"abstract":"<jats:p>\n                    This article proposes a class of dependencies for graphs, referred to as\n                    <jats:italic>graph entity dependencies<\/jats:italic>\n                    (GEDs). A GED is defined as a combination of a graph pattern and an attribute dependency. In a uniform format, GEDs can express graph functional dependencies with constant literals to catch inconsistencies, and keys carrying id literals to identify entities (vertices) in a graph. We revise the chase for GEDs and prove its Church-Rosser property. We characterize GED satisfiability and implication, and establish the complexity of these problems and the validation problem for GEDs, in the presence and absence of constant literals and id literals. We also develop a sound, complete and independent axiom system for finite implication of GEDs. In addition, we extend GEDs with built-in predicates or disjunctions, to strike a balance between the expressive power and complexity. We settle the complexity of the satisfiability, implication, and validation problems for these extensions.\n                  <\/jats:p>","DOI":"10.1145\/3287285","type":"journal-article","created":{"date-parts":[[2019,2,14]],"date-time":"2019-02-14T14:36:17Z","timestamp":1550154977000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":50,"title":["Dependencies for Graphs"],"prefix":"10.1145","volume":"44","author":[{"given":"Wenfei","family":"Fan","sequence":"first","affiliation":[{"name":"University of Edinburgh, Beihang University, and Shenzhen Institute of Computing Sciences"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ping","family":"Lu","sequence":"additional","affiliation":[{"name":"BDBC, Beihang University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,2,13]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Foundations of Databases","author":"Abiteboul Serge"},{"key":"e_1_2_2_2_1","doi-asserted-by":"crossref","unstructured":"Waseem Akhtar Alvaro Cort\u00e9s-Calabuig and Jan Paredaens. 2010. Constraints in RDF. In SDKB. 23--39.   Waseem Akhtar Alvaro Cort\u00e9s-Calabuig and Jan Paredaens. 2010. Constraints in RDF. In SDKB. 23--39.","DOI":"10.1007\/978-3-642-23441-5_2"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303983"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2638547"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543625"},{"key":"e_1_2_2_6_1","volume-title":"IFIP Congress. 580--583","author":"Armstrong William Ward","year":"1974"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1632"},{"key":"e_1_2_2_8_1","volume-title":"Vardi","author":"Beeri Catriel","year":"1981"},{"key":"e_1_2_2_9_1","volume-title":"Vardi","author":"Beeri Catriel","year":"1981"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2949689.2949698"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3167892.3167895"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/371920.371984"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0306-4379(03)00028-0"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/2876473.2876475"},{"key":"e_1_2_2_15_1","unstructured":"Andrea Cal\u00ec and Andreas Pieris. 2011. On equality-generating dependencies in ontology querying - Preliminary report. In AMW.  Andrea Cal\u00ec and Andreas Pieris. 2011. On equality-generating dependencies in ontology querying - Preliminary report. In AMW."},{"key":"e_1_2_2_16_1","doi-asserted-by":"crossref","unstructured":"Diego Calvanese Wolfgang Fischl Reinhard Pichler Emanuel Sallinger and Mantas Simkus. 2014. Capturing relational schemas and functional dependencies in RDFS. In AAAI.   Diego Calvanese Wolfgang Fischl Reinhard Pichler Emanuel Sallinger and Mantas Simkus. 2014. Capturing relational schemas and functional dependencies in RDFS. In AAAI.","DOI":"10.1609\/aaai.v28i1.8867"},{"key":"e_1_2_2_17_1","unstructured":"Qiang Cao Michael Sirivianos Xiaowei Yang and Tiago Pregueiro. 2012. Aiding the detection of fake accounts in large scale social online services. In NSDI. 197--210.   Qiang Cao Michael Sirivianos Xiaowei Yang and Tiago Pregueiro. 2012. Aiding the detection of fake accounts in large scale social online services. In NSDI. 197--210."},{"key":"e_1_2_2_18_1","volume-title":"Database Systems: 65-98","author":"Codd E. F."},{"key":"e_1_2_2_19_1","unstructured":"Alvaro Cort\u00e9s-Calabuig and Jan Paredaens. 2012. Semantics of constraints in RDFS. In AMW. 75--90.  Alvaro Cort\u00e9s-Calabuig and Jan Paredaens. 2012. Semantics of constraints in RDFS. In AMW. 75--90."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376938"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1085304.1085309"},{"key":"e_1_2_2_22_1","volume-title":"Vardi","author":"Fagin Ronald","year":"1984"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824056"},{"key":"e_1_2_2_24_1","unstructured":"Wenfei Fan and Floris Geerts. 2012. Foundations of Databases. Morgan 8 Claypool Publishers.  Wenfei Fan and Floris Geerts. 2012. Foundations of Databases. Morgan 8 Claypool Publishers."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1366102.1366103"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196916"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989373"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/567112.567117"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056114"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915232"},{"key":"e_1_2_2_31_1","volume-title":"USEWOD Workshop.","author":"Gallego Mario Arias"},{"key":"e_1_2_2_32_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey Michael"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536360.2536363"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/4904.4798"},{"key":"e_1_2_2_36_1","unstructured":"Ivana Grujic Sanja Bogdanovic-Dinic and Leonid Stoimenov. 2014. Collecting and analyzing data from E-government Facebook pages. In ICT Innovations.  Ivana Grujic Sanja Bogdanovic-Dinic and Leonid Stoimenov. 2014. Collecting and analyzing data from E-government Facebook pages. In ICT Innovations."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90294-K"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2630602.2630605"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-04939-7_12"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-015-9473-7"},{"key":"e_1_2_2_41_1","unstructured":"Holger Knublauch and Dimitris Kontokostas. 2017. Shapes Constraint Language (SHACL). W3C Working Draft. https:\/\/www.w3.org\/TR\/shacl\/#dfn-shacl-instance.  Holger Knublauch and Dimitris Kontokostas. 2017. Shapes Constraint Language (SHACL). W3C Working Draft. https:\/\/www.w3.org\/TR\/shacl\/#dfn-shacl-instance."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353404"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559799"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1804669.1804694"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920859"},{"key":"e_1_2_2_46_1","unstructured":"Neo4j Team. 2017. The Neo4j Developer Manual v3.1 (Chapter 3.5.2: Constraints). http:\/\/neo4j.com\/docs\/developer-manual\/current\/.  Neo4j Team. 2017. The Neo4j Developer Manual v3.1 (Chapter 3.5.2: Constraints). http:\/\/neo4j.com\/docs\/developer-manual\/current\/."},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1999299.1999306"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1938551.1938583"},{"key":"e_1_2_2_49_1","doi-asserted-by":"crossref","unstructured":"Vladislav Rutenburg. 1986. Complexity of generalized graph coloring. In MFCS. 573--581.   Vladislav Rutenburg. 1986. Complexity of generalized graph coloring. In MFCS. 573--581.","DOI":"10.1007\/BFb0016284"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/582250.582258"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/582475.582484"},{"key":"e_1_2_2_53_1","volume-title":"Retrieved on","year":"2018"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1804669.1804675"},{"key":"e_1_2_2_55_1","volume-title":"XML Schema Part 1: Structures","author":"Thompson Henry S."},{"key":"e_1_2_2_56_1","unstructured":"Yang Yu and Jeff Heflin. 2011. Extending functional dependency to detect abnormal data in RDF graphs. In ISWC.   Yang Yu and Jeff Heflin. 2011. Extending functional dependency to detect abnormal data in RDF graphs. In ISWC."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3287285","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3287285","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:01:53Z","timestamp":1750194113000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3287285"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,13]]},"references-count":55,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6,30]]}},"alternative-id":["10.1145\/3287285"],"URL":"https:\/\/doi.org\/10.1145\/3287285","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,13]]},"assertion":[{"value":"2017-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}