一句话：界定 MATLANG 中与 free-connex、q-hierarchical 合取查询对应的片段，识别支持常数延迟枚举和常数时间更新的线性代数程序。
由于线性代数与矩阵运算在数据分析中日益重要，人们希望借助关系查询优化技术来求值稀疏线性代数程序。近期工作建立了线性代数程序与关系代数之间的紧密联系，从而可以迁移后者的优化技术。本文研究 MATLANG 中哪些线性代数程序对应于合取一阶逻辑的 free-connex 与 q-hierarchical 片段：前者支持线性时间预处理后的常数延迟枚举，后者进一步支持常数时间更新。作者改进并推广了 MATLANG 与在半环标注关系上求值的关系代数之间的对应关系，并识别出使复杂度界从布尔标注推广到一般半环成立的半环性质。通过刻画相应的 MATLANG 片段，本文识别出可常数延迟枚举与常数时间更新的线性代数程序片段。
Due to the importance of linear algebra and matrix operations in data analytics, there is significant interest in using relational query optimization and processing techniques for evaluating (sparse) linear algebra programs. In particular, in recent years close connections have been established between linear algebra programs and relational algebra that allow transferring optimization techniques of the latter to the former. In this paper, we ask ourselves which linear algebra programs in MATLANG correspond to the free-connex and q-hierarchical fragments of conjunctive first-order logic. Both fragments have desirable query processing properties: free-connex conjunctive queries support constant-delay enumeration after a linear-time preprocessing phase, and q-hierarchical conjunctive queries further allow constant-time updates. By characterizing the corresponding fragments of MATLANG, we hence identify the fragments of linear algebra programs that one can evaluate with constant-delay enumeration after linear-time preprocessing and with constant-time updates. To derive our results, we improve and generalize previous correspondences between MATLANG and relational algebra evaluated over semiring-annotated relations. In addition, we identify properties on semirings that allow to generalize the complexity bounds for free-connex and q-hierarchical conjunctive queries from Boolean annotations to general semirings.
@article{paperbot4036,
title = {Enumeration and updates for conjunctive linear algebra queries through expressibility},
author = {Thomas Muñoz and Cristian Riveros and Stijn Vansummeren},
journal = {Logical Methods in Computer Science},
volume = {Volume 22, Issue 1},
year = {2026},
doi = {10.46298/lmcs-22(1:1)2025}
}