1989 | OriginalPaper | Chapter
DBA*: Solving Combinatorial Problems with Deductive Databases
Authors : Helmut Schmidt, Werner Kiessling, Ulrich Güntzer, Rudolf Bayer
Published in: Datenbanksysteme in Büro, Technik und Wissenschaft
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The evolution of database (DB) technology, with its origins in hierarchical databases, has currently reached the stage of matured relational DB systems and is about to grow into deductive DB systems, where logic programming — originated by the artificial intelligence (AI) community — plays a central theoretical role. Until now, however, no smooth integration of another important part of AI, namely that of heuristic search and intelligent planning, into DB technology was known. This paper contributes a first step beyond deductive DB systems towards intelligent DB systems. We describe the well-known A*-algorithm in terms of a general theoretical framework for deductive DB systems, the sloppy deltaiteration scheme, and give a generalized algorithm, called DBA*-algorithm. As an immediate consequence, heuristic search strategies for combinatorial problems become now feasible in the DB environment in a natural and efficient way. We also present a prototype implementation of the DBA*-algorithm, with the 15-Puzzle and the Traveling Salesman Problem as sample combinatorial problems. The benchmark results gained from this testbed demonstrate the applicability and efficiency of our approach for heuristic search in deductive DB systems.