Query–subquery nets for Horn knowledge bases in first-order logic. Issue 1 (2nd January 2017)

• Record Type: Journal Article
• Authors: Cao, Son Thanh; Nguyen, Linh Anh
• Is Part Of: Journal of information and telecommunication. Volume 1:Issue 1(2017)
• Page Start: 79
• Page End: 99
• Publication Date: 2017-01-02
• Subjects: Horn knowledge bases -- deductive databases -- Datalog -- query processing -- evaluation methods -- magic-sets transformation -- query–subquery -- QSQ -- QSQR -- QSQN; Telecommunication -- Periodicals; Information technology -- Periodicals; 621.382
• DOI: 10.1080/24751839.2017.1295664
• Languages: English
• ISSNs: 2475-1839

Abstract

ABSTRACT: We formulate query–subquery nets and use them to create the first framework for developing algorithms for evaluating queries to Horn knowledge bases with the properties that: the approach is goal-directed; each subquery is processed only once and each supplement tuple, if desired, is transferred only once; operations are done set-at-a-time; and any control strategy can be used. Our intention is to increase efficiency of query processing by eliminating redundant computation, increasing adjustability (i.e. easiness in adopting advanced control strategies) and reducing the number of accesses to the secondary storage. For this purpose, we transform a logic program into an equivalent net structure and use it to determine which set of tuples or subqueries should be evaluated at each step, in an efficient way. The framework forms a generic evaluation method called QSQN, which is sound and complete and has polynomial time data complexity when the term-depth bound is fixed. The experimental results confirm the efficiency and usefulness of this method.