Query Evaluation for Deductive Database

The query evaluation for the deductive database is as follows:

phase 1: storage and access

• The deductive database stores rules and facts on datalog formulas in clausal form
• It contains quantifiers like existential and universals
• Clausal forms of the formula are made up of a number of clauses each clause is composed of a number of literals connected by OR logical connection or AND logical connection

phase2: interpretation of rules

• The deductive database then interprets all rules using various methods.
• Interpretation of rules the fact is considered as axioms. Rules are also called deductive axioms and are used to construct a proof that derives new facts from existing facts.
• Another method of interpretation we have given is an infinite domain of constant values with an assigned predicate for each combination of values for an argument.

Deductive Database Prototype

There are many deductive prototypes are available many such systems are memory based. it assumes all required permanent relations are stored in the main memory and during the computation process, temporary relations generated can be stored in memory.

for example RDL/c and megalog

Pre-requisites: What is a Database?

We classify the relation in Datalog Program or deductive database as either output relation or input relation. output relations are defined by rules and input relations have a set of tuples explicitly listed (e.g. assembly) given the instance of the input relation we must compute instances for the output relations.

The major advantage of a deductive database is the ability to write queries. we can understand deductive databases more easily using the following diagram.

The meaning Datalog programming usually defines deductive database in two different ways both of which essentially describe the relation instance for output relation. technically a query is a section over one of the output relations. however, the meaning of the query is clear once we understand how relation instances are associated with output relation in Datalog Program