期刊
ACM TRANSACTIONS ON DATABASE SYSTEMS
卷 44, 期 2, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3287285
关键词
Graph dependencies; conditional functional dependencies; keys; EGDs; TGDs; satisfiability; implication; validation; axiom system; built-in predicates; disjunction
资金
- 973 Program [2014CB340302]
- ERC [652976]
- NSFC [61421003]
- EPSRC [EP/M025268/1]
- Foundation for Innovative Research Groups of NSFC
- Huawei
- Edinburgh
- Beijing Advanced Innovation Center for Big Data and Brain Computing
- European Research Council (ERC) [652976] Funding Source: European Research Council (ERC)
- EPSRC [EP/M025268/1] Funding Source: UKRI
This article proposes a class of dependencies for graphs, referred to as graph entity dependencies (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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据