CCT 424 ASSIGNMENT (GROUP 6)

CCT/00040/020

CCT/00015/020

CI/00126/018

CCT/00080/020

CCT/00081/020

Deductive Databases (DDBs)

• Introduction

• Prolog/Datalog Notation

• Rule Interpretation

• Inference Mechanisms

Introduction

Deductive Databases (DDBs) are a type of database system that extends traditional
relational databases by incorporating deductive reasoning capabilities. They allow users to
define rules and facts using logic-based languages like Prolog or Datalog, enabling more
expressive queries and powerful inference mechanisms. Here's an overview of the key
aspects of Deductive Databases.

Deductive Databases combine the features of relational databases with logic programming
paradigms. They aim to provide a declarative and expressive way to define complex
relationships and derive new information from existing data through logical inference.

Prolog/Datalog Notation

Prolog and Datalog are two commonly used languages for defining rules and facts in
Deductive Databases. Prolog is a logic programming language commonly used in artificial
intelligence and deductive database systems. It allows the definition of rules and queries
in a syntax that resembles first-order logic. Datalog is a subset of Prolog specifically
designed for defining deductive databases. It offers a simplified syntax focused on rule-
based definitions.

Principle: provide predicates with unique names

Predicate:

implicit meaning (via a suggestive name)

fixed number of arguments

If the arguments are all constant values, then the predicate states that a certain fact is

true.

If the arguments are variables, then the predicate is considered as a query or as a part of

a rule or constraint

Prolog Conventions adopted here:

1. constant values in a predicate are either numeric or character strings and they are

represented by identifiers starting with a lowercase letter only.

2. variable names start with an uppercase letter only.

Rule Interpretation

In Deductive Databases, rules are used to derive new information from existing data.
When a query is made against the database, the system interprets these rules to generate
results. This interpretation typically involves backward or forward chaining inference
mechanisms.

Rule interpretation in deductive databases is a fundamental aspect that governs how new
information is derived from existing data. It involves understanding the logical implications
of rules and applying them appropriately during query evaluation.

Depending on the inference mechanism used, rule interpretation can occur in different
modes:

• Forward Chaining: In forward chaining, the system applies rules to deduce new
information from known facts. It iteratively evaluates rules whose conditions are
satisfied by the current database state, generating new facts until no more rules
can be applied.
• Backward Chaining: In backward chaining, the system starts with the query and
works backward through the rules to find a chain of deductions that support the
query. It identifies rules whose heads match the query and then recursively
evaluates those rules' bodies to determine if the query can be satisfied.
Inference Mechanisms

Inference mechanisms play a crucial role in deductive databases, enabling them to derive
new information from existing data through logical reasoning. These mechanisms
determine how rules are applied and how queries are evaluated to generate results.

• Forward Chaining:

Forward chaining, also known as data-driven reasoning or bottom-up reasoning, is a

mechanism where the system starts with known facts and applies rules to derive new
conclusions. Here's how it works:

Initialization: The process begins with the known facts stored in the database.

Rule Application: The system iteratively evaluates rules whose conditions are satisfied by
the current database state. When a rule's conditions (body) match the existing data, the
system applies the rule to deduce new facts (head).

New Fact Generation: Each application of a rule generates new facts, which are added to
the database.

Iteration: The process continues iteratively, with newly derived facts becoming input for
further rule application. This iterative process continues until no more new facts can be
deduced.

Termination: The process terminates when no more rules can be applied, or when a
predefined termination condition is met.

Forward chaining is particularly useful for deriving conclusions in an incremental and

proactive manner, making it suitable for applications where the goal is to continuously
update and expand the database with new information.

• Backward Chaining:

Backward chaining, also known as goal-driven reasoning or top-down reasoning, is a

mechanism where the system starts with a query or goal and works backward through the
rules to find a chain of deductions that support the query. Here's how it works:

Goal Identification: The process begins with the user's query or goal that needs to be
satisfied.

Rule Matching: The system identifies rules whose heads (conclusions) match the query.

Rule Application: For each matched rule, the system recursively evaluates the conditions
specified in the rule's body to determine if the query can be satisfied. This recursive
process may involve further sub-goals.
Fact Retrieval: As the system traverses backward through the rules, it retrieves facts
from the database that satisfy the conditions specified in the rule bodies.

Termination: The process terminates when the query is satisfied, or when no further
deductions can be made to satisfy the query.

Backward chaining is particularly useful for answering specific queries and determining the
conditions under which certain conclusions can be derived. It allows for more targeted
reasoning compared to forward chaining.

• Hybrid Approaches:

In practice, deductive databases may employ hybrid approaches that combine elements of
both forward and backward chaining. These hybrid approaches aim to leverage the
strengths of each mechanism while mitigating their respective weaknesses. For example, a
hybrid approach might use backward chaining to identify relevant rules and forward
chaining to derive conclusions efficiently.

• Rule Optimization:

Efficient rule interpretation is crucial for the performance of deductive databases.

Techniques such as rule indexing, caching, and query optimization are employed to optimize
rule evaluation and improve the efficiency of inference mechanisms.

By leveraging these inference mechanisms, deductive databases can perform complex

logical reasoning and derive meaningful insights from the available data, making them
powerful tools for advanced data analysis and decision-making tasks.