Affiliations: Department of Computer and Information Science, Linköping University, S-581 83 Linköping, Sweden. e-mail: patdo@ida.liu.se | Soft Computer Consultants, 34350 US 19N, Palm Harbor, FL 34684, USA e-mail: jk@softcomputer.com | Institute of Informatics, Warsaw University, ul. Banacha 2, 02-097 Warsaw, Poland e-mail: szalas@mimuw.edu.pl
Note: [] Supported in part by the Swedish Council for Engineering Sciences (TFR) and the Wallenberg Foundation. Address for correspondence: Department of Computer and Information Science, Linköping University, S-581 83 Linköping, Sweden
Note: [] Address for correspondence: Soft Computer Consultants, 34350 US 19N, Palm Harbor, FL 34684, USA
Note: [] Supported in part by the Wallenberg Foundation. Address for correspondence: Institute of Informatics, Warsaw University, ul. Banacha 2, 02-097 Warsaw, Poland
Abstract: We introduce the notion of a meta-query on relational databases and a technique which can be used to represent and solve a number of interesting problems from the area of knowledge representation using logic. The technique is based on the use of quantifier elimination and may also be used to query relational databases using a declarative query language called SHQL (Semi-Horn Query Language), introduced in [6]. SHQL is a fragment of classical first-order predicate logic and allows us to define a query without supplying its explicit definition. All SHQL queries to the database can be processed in polynomial time (both on the size of the input query and the size of the database). We demonstrate the use of the technique in problem solving by structuring logical puzzles from the Knights and Knaves domain as SHQL meta-queries on relational databases. We also provide additional examples demonstrating the flexibility of the technique. We conclude with a description of a newly developed software tool, The Logic Engineer, which aids in the description of algorithms using transformation and reduction techniques such as those applied in the meta-querying approach.
