paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Can One Escape Red Chains?

能否逃离 Red Chains？
LICS Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science2018匹配度 1/10 · 论文研究数据库理论中的查询决定性（query determinacy），属于逻辑与自动机/数据库理论方向，与用户关注的静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析等核心方向没有直接关联。引用 2 inbox
Grzegorz Głuch, Jerzy Marcinkowski, Piotr Ostropolski-Nalewaja
逻辑与自动机
crossref: 2026-09-12

AI 速览

一句话：研究查询决定性：给定查询集合与目标查询，判断视图信息是否足以计算目标查询结果。

本文研究查询决定性（query determinacy）：给定查询集合 Q={Q1,...,Qk} 与另一查询 Q0，若对任意数据库 D，Q(D) 所包含的信息都足以计算 Q0(D)，则称 Q 决定 Q0。论文标题中的 Red Chains 指向该性质分析中的关键结构或障碍，但所给摘要仅给出问题定义，未说明具体技术路线、判定算法或复杂度结果。因此，该工作应是在查询语言语义与信息充分性框架下，探讨 Q 是否决定 Q0 这一理论问题。

问题
在查询语言中，给定查询集合 Q 与目标查询 Q0，刻画 Q 的视图信息何时足以决定 Q0，即 query determinacy 问题。
方法
所给摘要未提供具体方法；标题中的 Red Chains 暗示论文可能围绕该结构分析查询决定性的边界或不可判定性。
评估
摘要未给出实验或评估细节；从问题性质看，评估应依赖理论判定、复杂度或语义论证。
原文摘要（Abstract）

For a given set of queries (which are expressions in some query language) Q = {Q1, Q2, ... Qk} and for another query Q0 we say that Q determines Q0 if -- informally speaking -- for every database D, the information contained in the views Q(D) is sufficient to compute Q0(D).

链接与引用

DOI 原文 ·

BibTeX 
@inproceedings{paperbot4388,
  title = {Can One Escape Red Chains?},
  author = {Grzegorz Głuch and Jerzy Marcinkowski and Piotr Ostropolski-Nalewaja},
  booktitle = {LICS},
  year = {2018},
  doi = {10.1145/3209108.3209120}
}