Data and Knowledge Bases with Incomplete Information in a Set of Strings Framework

Igor Sheremet

Incompleteness of information about monitored objects is immanent property of many information processing systems. That is why databases with incomplete information (DBI) modeling is constantly actual area of the theoretical computer science as well as foundation of efficiency of DBI-centered software and hardware. This article describes an approach to such modeling, the main feature of which is representation of the DBI as a finite set of so-called incomplete (N-) facts being sentential forms (SF) of context-free grammar, which set of rules form metadatabase (MDB). Relation of the mutual informativity on the N-facts set is defined, and set-theoretical, mathematical and operational semantics of the DBI data manipulation language (DML) are described, as well as generalized model of the associative storage and access supporting N-facts handling. Augmented Post systems being knowledge representation model associated with mentioned DBI are introduced.