Boolean Query DAG Evaluation over Inverted Indices

This post establishes the theoretical boundaries of executing complex logic natively over an inverted index. It formalizes a retrieval language (L_R) based on Directed Acyclic Graphs (DAGs) and proves that its evaluation problem is strictly P-Complete. To make evaluation tractable, it introduces ComputePN, a deterministic, sparsity-aware evaluation algorithm. By decoupling logical negation from universe-scale materialization via a novel Positive-Negative dual representation, and utilizing native DAG memoization, ComputePN strictly bounds evaluation time to O(|Q| · |U_active|). This approach successfully evaluates P-Complete queries natively over the index, avoiding both the combinatorial tree-expansion bottleneck and the universal scan penalty, laying the formal foundation for computational retrieval.