The Knowledge Base Engine
In-memory Bitsets and Matrices: high-performance storage for logical reasoning.
Bitset-Oriented Design
Traditional databases (SQL) are Row-Oriented. They are great for retrieving a record, but slow for set operations. CNL-PL is Bitset-Oriented. The primary atom of storage is not a "Record" but a "Set".
Every entity in the system is interned to a dense integer ID (0..N). A Bitset is simply a compact array of bits where the N-th bit is 1 if Entity N is in the set.
The RelationMatrix
A binary predicate (like "user has role") is stored as a RelationMatrix.
RelationMatrix {
rows: Bitset[] // rows[SubjectID] -> Bitset of Objects
}
If we want to know "What roles does User_42 have?", we simply read rows[42]. The result is a Bitset representing the set of roles.
Crucially, we maintain the Inverse Matrix. This allows us to answer "Which users have the admin role?" instantly by looking up the admin ID in the inverse matrix.
Attribute Indices
NumericIndex
Stores primitive values like integers or floats.
NumericIndex { values: Float64Array, hasValue: Bitset }
Separates existence (hasValue) from magnitude, enabling fast filtering.
EntityAttrIndex
Stores attributes that point to other entities (e.g., User has a role of Admin).
EntityAttrIndex { values: Bitset[] }
Allows attributes to behave like relations but be scoped as properties.
FactID & Provenance
To explain "Why?", every bit in the KB must be traceable. However, storing an ID for every bit is expensive.
FactID Strategy: We derive a stable 64-bit or 128-bit hash from the tuple (PredID, SubjectID, ObjectID).
This allows us to look up justification trees (provenance) in a separate store without bloating the hot reasoning path.