Scholarlink

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 naïve evaluation, which treats nulls as fresh constants and applies standard query evaluation. While naïve 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 naïve evaluation computes certain answers.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

When Does Naïve Evaluation Work for Datalog?

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Heng Liu,
  • Eugenia Ternovska

摘要

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 naïve evaluation, which treats nulls as fresh constants and applies standard query evaluation. While naïve 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 naïve evaluation computes certain answers.