Psqlog: Prolog implemented in PostgreSQL

Summary

Psqlog allows you to discover information latently present in your existing relational database. Psqlog lets you use the familiar and widely-available SQL query language to discover this information. The information latently present refers to the logical relationships that you specify between rows and columns in your database.

Psqlog is intended to be a practical extension of PostgreSQL rather than a language in itself. That is, its most natural application is to analyze existing PostgreSQL databases, rather than being used as a dialect of Prolog.

Example: Introduction

Suppose you are keeping track of who reports to who in an organization. The organization's reporting structure can be represented graphically as:

It is evident from the chart that Eugene reports to Gustavo, and that Gustavo reports to Lex.

Now suppose your database stores these direct reporting relationships. That is, you can query your database to know directly reports to who. However, you would also like to know all of the subordinates of a given person. That is, you'd like to know that not only does Bob reports to Eugene, but that Bob also reports to Gustavo, and to Lex as well. In other words, you'd like to know who all of the superiors of a given employee are, not just his or her direct superior.

The reasoning is more formally expressed by the following two rules:

A is a superior of B if:

1. A is a manager (ie a direct superior) of B, or
2. there is someone named C, who A manages, and who is himself a superior of B.

Note that rule 2 is a recursive definition: it defines the 'superior' relation between A and B in terms of the 'superior' relation between C and B.

Psqlog gives you the ability to express these rules, such as 1) and 2) above, in your database, and to then make queries in the familiar form of SQL.

Examples: Table Setup

We store the information shown in the above diagram in a conventional, normalized table form as:

Employee table

company=# \d employee
                                     Table "public.employee"
    Column    |          Type          |                 Modifiers                        
--------------+------------------------+-----------------------------------
 employee_id  | integer                | not null default nextval
                                            ('employee_sequence'::regclass)
 name         | character varying(256) | 
Indexes:
    "employee_pkey" PRIMARY KEY, btree (employee_id)

Management table

company=# \d management;
                              Table "public.management"
    Column     |  Type   |                         Modifiers                         
---------------+---------+------------------------------------------
 management_id | integer | not null default nextval
                            ('management_sequence'::regclass)
 manager       | integer | 
 managed       | integer | 
Indexes:
    "management_pkey" PRIMARY KEY, btree (management_id)
Foreign-key constraints:
    "management_managed_fkey" 
          FOREIGN KEY (managed) REFERENCES employee(employee_id)
    "management_manager_fkey" 
          FOREIGN KEY (manager) REFERENCES employee(employee_id)

The above org chart would be added to the database by INSERTs such as the following:

company=# INSERT into employee (name) VALUES ('Eugene');
company=# INSERT into employee (name) VALUES ('Bob');
company=# SELECT employee_id FROM employee WHERE name='Eugene'; 
 employee_id 
-------------
           4
(1 row)

company=# SELECT id FROM employee WHERE name='Bob' 
 employee_id 
-------------
           8
(1 row)

company=# INSERT INTO management (manager, managed) VALUES (4,8);

..rest of management relations are inserted..

company=# select boss.name AS boss, worker.name AS worker
             FROM management,employee AS boss,employee AS worker
             WHERE management.manager = boss.employee_id AND
                   management.managed = worker.employee_id;
  boss   | worker  
---------+---------
 Lex     | Gustavo
 Gustavo | Eugene
 Gustavo | Salman
 Lex     | Lei
 Lex     | Xavier
 Salman  | Greg
 Eugene  | Bob
(7 rows)

Examples: Psqlog Queries

Now, we can query the database after loading this database with Psqlog functionality:

-- who works under Lex?
company=# SELECT unify_arg1 AS A, unify_arg2 AS B FROM 
          unify2( 'superior' , 'A' , 'B' , 'Lex',NULL );
  a  |    b    
-----+---------
 Lex | Bob
 Lex | Greg
 Lex | Eugene
 Lex | Salman
 Lex | Gustavo
 Lex | Lei
 Lex | Xavier
(7 rows)

-- who works above Bob?
SELECT unify_arg1 AS A, unify_arg2 AS B FROM 
       unify2( 'superior' , 'A' , 'B' , NULL,'Bob' );

    a    |  b  
---------+-----
 Gustavo | Bob
 Lex     | Bob
 Eugene  | Bob
(3 rows)

-- does Bob work for Gustavo? (yes)
SELECT unify_arg1 AS A, unify_arg2 AS B FROM 
       unify2( 'superior' , 'A' , 'B' ,
                         'Gustavo','Bob' );

    a    |  b  
---------+-----
 Gustavo | Bob
(1 row)

-- does Greg work for Eugene? (no)
SELECT unify_arg1 AS A, unify_arg2 AS B FROM 
       unify2( 'superior' , 'A' , 'B' ,
                          'Greg','Eugene' );

 a | b 
---+---
(0 rows)

Usage

1. Get the software.
2. make sure you have xsltproc installed (part of libxslt usually).
3. make sure you have PostgreSQL installed, running, and accessible to localhost clients.
4. set up a PostgreSQL user named "www" who has permission to create new databases.
5. run "sh company.sh"

Benefits

Familiarity

Transparency

Safety

Limitations

Prolog compliance

• Syntax is SQL, not Prolog (see Usage)
• Support for lists
• Support for the "cut" operator
• Support for DCGs (Definite Clause Grammars)

Efficiency

Psqlog currently makes use of a temporary table that it must update. This is overly expensive: instead, future versions of Psqlog will make use of in-memory data structures, which will likely be represented as SQL SELECTs (of constants rather than tables). (On the other hand, the table is declared as TEMPORARY and if the session is READ ONLY, then presumably, PostgreSQL will not need to write the data to disk).

Related Work

As mentioned above, Psqlog is intended to be a practical extension of PostgreSQL rather than a language in itself. The links mentioned below should be compared to Psqlog with that in mind.

• Ciao Prolog to SQL translator allows access to a sql database from prolog.
• XSB is a Logic Programming and Deductive Database system for Unix and Windows.
• gppostgresql, a GNU-Prolog interface to PostgreSQL.

Software

Psqlog is copyrighted by Eugene Koontz and free for you to use, modify and distribute under the GPL version 2 or higher.