Space-Efficient Data Structures for the Inference of Subsumption and
Disjointness Relations
José Fuentes-Sepúlveda, Diego Gatica, Gonzalo Navarro,
M. Andrea Rodríguez, and Diego Seco
Conventional database systems function as static data repositories, storing vast
amounts of facts and offering efficient query processing capabilities. The sheer volume of data these systems store has a direct impact on their scalability, both in terms
of storage space and query processing time. Deductive database systems, on the other
hand, require far less storage space since they derive new knowledge by applying
inference rules. The challenge is how to efficiently obtain the required derivations,
compared to having them in explicit form. In this study, we concentrate on a set of
predefined inference rules for subsumption and disjointness relations, including their
negations. We use compact data structures to store the facts and provide algorithms
to support each type of relation, minimizing even further the storage space requirements. Our experimental findings demonstrate the feasibility of this approach, which
not only saves space but is often faster than a baseline that uses well-known graph
traversal algorithms implemented on top of a traditional adjacency list representation to derive the relations.