.png){kind=icon}
Return
When Does Naive Evaluation Work for Datalog?
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-08887-1_5.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Query answering over incomplete data is typically predicated on the notion of certain answers, comprising the set of tuples that appear in the query result across all possible complete databases. Computing certain answers is often computationally expensive, with lower bounds such as coNP-hardness or even undecidability in many cases. One tractable approach is naive evaluation, which treats nulls as fresh constants and applies standard query evaluation. While naive evaluation is known to compute certain answers for positive Datalog, its behavior for more expressive extensions of Datalog has remained less understood. This paper identifies syntactic extensions of Datalog for which naive evaluation computes certain answers.
Keywords:
Incomplete data
Datalog
Certain answers
Preservation theorems
Journal
R
IF:
0
Papers:
15
Citations:
0
Organization
Cited Papers
Complexity of answering queries using materialized views.png)
Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems
OAAI
Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsIF0
OAAIShareSaveShareSave
View more