23.3. Deductive databases

By definition, a deductive database consists of two parts: an extensional one containing facts, and an intentional database containing rules for inferring new facts on the basis of the extensional part and a user request.

It is easy to see that with such a general definition, SQL-oriented relational DBMS can be attributed to deductive systems. Indeed, there are representations that are defined in the relational database scheme, but a non-intentional part of the database. In the end, it is not so important what specific mechanism is used to derive new facts from existing ones. In the case of SQL, the main element of the view definition is the SQL language selection statement, which is quite natural, since the result of the selection statement is the generated table. Necessary extensibility is also provided, since views can be defined not only over base tables, but also over views.

The main difference between a real deductive DBMS and a relational one is that both the rules of the intentional part of the database and user requests may contain recursion. One can argue about whether recursion is always good. However, the ability to define recursive rules and queries allows simple solutions in deductive databases of problems that cause big problems in relational systems (for example, problems of disassembling a complex part into primitive components). On the other hand, it is the possibility of recursion that makes the implementation of a deductive DBMS a very difficult and, in many cases, effectively unsolvable problem.

We will not consider in more detail the specific problems, the restrictions applied and the methods used in deductive systems. We only note that usually query languages ​​and definitions of the intentional part of a database are logical (therefore, deductive databases are often called logical). There is a direct connection of deductive databases with knowledge bases (the intentional part of the database can be considered as BR). Moreover, it is difficult to distinguish between these two entities; at least there is no consensus on this.

What is the connection between deductive databases and relational DBMS, except that the relational database is a degenerate special case of deductive? The main thing is that for the implementation of a deductive DBMS is usually used relational system. Such a system acts as a custodian of facts and executing requests coming from the level of a deductive database. By the way, such use of relational DBMSs makes the task of global query optimization very urgent.

With the usual use of a relational DBMS, requests are usually received for processing one at a time, so there is no reason for their global (inter-request) optimization. A deductive DBMS, when performing a single user request, generally generates a batch of requests to a relational DBMS that can be optimized together.

Of course, in the case when the set of rules for a deductive database becomes large, and it is impossible to place them in RAM, the problem arises of managing their storage and access to them in external memory. Here again, the relational system can be applied, but not very efficiently. More complex data structures and other sampling conditions are required. Private attempts to solve this problem are known, but there is no general solution yet.