Title :
Deduction graphs: an algorithm and applications
Author_Institution :
Dept. of Comput. Sci., North Texas Univ., Denton, TX, USA
fDate :
1/1/1989 12:00:00 AM
Abstract :
A deduction graph (DG) for logically deducing a new functional dependency (FD) or function-free Horn formula (extended from Horn clauses) from a subset of a given FDs or function-free headed Horn clauses in a relational database or rule-based expert systems is defined. An algorithm with a polynomial time complexity for constructing a DG based on a number of rules is designed. Applications of DGs to relational databases, rule-based expert systems, logic programming, and artificial intelligence are investigated. In addition to graphically solving the inference problem by DGs, many logic queries can be answered by DGs with substitutions for unifying expressions
Keywords :
database theory; expert systems; inference mechanisms; logic programming; relational databases; Horn clauses; artificial intelligence; deduction graph; function-free Horn formula; functional dependency; inference problem; logic programming; logic queries; polynomial time complexity; relational database; rule-based expert systems; Algorithm design and analysis; Artificial intelligence; Control systems; Deductive databases; Expert systems; Inference algorithms; Logic programming; Polynomials; Relational databases; Terminology;
Journal_Title :
Software Engineering, IEEE Transactions on
