August 1998        Issue: 4

Journal of Conceptual Modeling
www.inconcept.com/jcm

Conceptual Level Information System
Implementation in Prolog
by Dennis Corbo

One of the ongoing challenges in the development of information systems is the translation of a conceptual model into an implementation of the model. This article will attempt to show the correlation between a conceptual model represented as an Object Role Model (ORM) and the model implemented in Prolog. The main purpose is to demonstrate that much of the conceptual nature of an ORM is not necessarily lost when implemented as a working information system. Practically speaking, a close correlation between a model and a model’s implementation makes it very feasible and attractive to use the model for maintenance of the system.

In "Programming in Prolog", the authors describe Prolog as a computer programming language that is used to solve problems that involve objects and the relationships between objects. Programming in Prolog consists of:

This description is very similar to the description of a conceptual information system in "Conceptual Schema and Relational Database Design". In it, the author describes a conceptual level information system as consisting of :

The conceptual schema is described as having three sections:

Stored fact types are described as the kinds of sentences or facts that may be stored in the conceptual database. These facts represent the objects that may exist in the database, how the objects are referenced, and the various relationships within which the objects may participate. It is evident that this section is closely aligned with the first activity of programming in Prolog listed earlier. The constraints section of a conceptual schema is said to list the constraints and restrictions that apply to the stored fact types. Static constraints are always applicable while dynamic constraints apply during database state transition. Constraints are implemented in the second activity listed above for programming in Prolog, "defining some rules about objects and their relationships". Derivation rules, the third section of the conceptual schema, are described as functions, operators and rules that may be used to derive information not explicitly stored in the database. This is handled by the second and third activities of programming in Prolog where relationships are defined and questions may be asked about relationships between objects. In Prolog, a collection of facts is called a database. The database is maintained by "asserting" facts into and "retracting" facts from the database. The conceptual database is said to be a set of sentences expressing propositions asserted to be true which may be added and removed from the database. Again, the similarity between the Prolog definition of a database and the definition of a conceptual database is striking. Last in this comparison is the conceptual information processor with the last activity of programming in Prolog. The conceptual information processor is said to be responsible for supervising updates to the database by the user and for answering user queries. We’ll begin our exploration of an ORM implementation in Prolog using the subschema depicted in Figure_1. The Prolog implementation developed is designed to illustrate the conceptual nature of Prolog when based on an ORM and should not be mistaken for a production ready facility.

Image37.gif (10379 bytes)

Examining the schema, we see several entity types, some of which are subtypes. The Product entity participates in 3 mandatory roles while one of Product’s subtypes, Scanner, participates in 2 mandatory roles. All of the relationships are one-to-many except for the "Product has shipping cost of MoneyAmount" relationship which is many-to-many. We can begin designing our Prolog implementation by defining the objects we need:

product(code)
scanner_kind(code)
weight(lbs)
money_amount(dollars)
density(dpi)
bits(code)
size(inches)

You can see that many of the objects would have traditionally been implemented as attributes but are declared as objects in Prolog. Next, we can define the 2 subtypes of Product:

software(product(code))
scanner(product(code))

The technique is simply to use the product object as an argument of a predicate that defines the subtype. Now that we have all of our objects, we can start defining relationships:

has(product(code), product_name(text))
has(product(code), description(text))

An explanation is in order. The ORM shows 2 relationships with Product:

Product has ProductName
Product has Description

These relationships are implemented in Prolog by making the relationship, in this case "has", into a predicate (sometimes called a functor) and using the objects participating in the relationship as arguments of the predicate. You may be wondering if the Prolog program will get confused because the relationship name is the same for the two different relationships. The answer is no, because the built-in pattern matching of Prolog can distinguish between a product_name(text) and a description(text). Using the techniques described thus far, the complete prolog definition of the ORM schema is:

%
% Translation of ORM model to Prolog
% See: mailordr sample
%
% Clauses
%
% product(code)
% has(product(code),product_name(text))
% has(product(code),description(text))
% weighs(product(code),weight(lbs))
% has_cost_of(product(code),money_amount(dollars))
% has_list_price_of(product(code),money_amount(dollars))
% has_negotiable_price_of(product(code),money_amount(dollars))
% has_shipping_cost_of(product(code),money_amount(dollars))
% product_kind(code)
% is_of(product(code),product_kind(code))
% software(product(code))
% scanner(product(code))
% scanner_kind(code)
% is_of(scanner(code),scanner_kind(code))
% comes_with(software(product(code)), scanner(product(code)))
% has(scanner(product(code)),requirement(text))
% has_resolution_in(scanner(product(code)),density(dpi))
% has_level_of(scanner(product(code)),bits(code))
% has_length(scanner(product(code)), size(inches))
% has_width(scanner(product(code)), size(inches))
product_kind(hw).
product_kind(sw).
product_kind(ac).
product(100).
product(101).
product(500).
product(501).
product(600).
is_of(product(100),product_kind(hw)).
is_of(product(101),product_kind(hw)).
is_of(product(500),product_kind(sw)).
is_of(product(501),product_kind(sw)).
is_of(product(600),product_kind(hw)).
has(product(100),product_name('Midget')).
has(product(101),product_name('Super Midget')).
has(product(500),product_name('Picture Perfect')).
has(product(501),product_name('OCR+')).
has(product(600),product_name('Ultra 1000')).
has(product(100),description('600 dpi b/w handheld scanner')).
has(product(101),description('800 dpi color handheld scanner')).
has(product(500),description('Imaging and graphics software')).
has(product(501),description('OCR software')).
has(product(600),description('1200 dpi color flatbed scanner')).
weighs(product(100),weight(2)).
weighs(product(101),weight(2.5)).
weighs(product(500),weight(12)).
weighs(product(501),weight(6)).
weighs(product(600),weight(20)).
has_cost_of(product(100),money_amount(175.00)).
has_cost_of(product(101),money_amount(275.00)).
has_cost_of(product(500),money_amount(12.50)).
has_cost_of(product(501),money_amount(14.00)).
has_cost_of(product(600),money_amount(1275.00)).
has_list_price_of(product(100),money_amount(250.00)).
has_list_price_of(product(101),money_amount(375.00)).
has_list_price_of(product(500),money_amount(22.50)).
has_list_price_of(product(501),money_amount(26.50)).
has_list_price_of(product(600),money_amount(2275.00)).
has_negotiable_price_of(product(100),money_amount(225.00)).
has_negotiable_price_of(product(101),money_amount(335.00)).
has_negotiable_price_of(product(500),money_amount(20.50)).
has_negotiable_price_of(product(501),money_amount(24.50)).
has_negotiable_price_of(product(600),money_amount(2175.00)).
has_shipping_cost_of(product(100),money_amount(15.00)).
has_shipping_cost_of(product(101),money_amount(15.00)).
has_shipping_cost_of(product(500),money_amount(5.50)).
has_shipping_cost_of(product(501),money_amount(5.50)).
has_shipping_cost_of(product(600),money_amount(35.00)).
software(product(500)).
software(product(501)).
scanner(product(100)).
scanner(product(101)).
scanner(product(600)).
scanner_kind(hh).
scanner_kind(fb).
is_of(scanner(product(100)),scanner_kind(hh)).
is_of(scanner(product(101)),scanner_kind(hh)).
is_of(scanner(product(600)),scanner_kind(fb)).
comes_with(software(product(500)),scanner(product(600))).
comes_with(software(product(501)),scanner(product(600))).
comes_with(software(product(501)),scanner(product(100))).
comes_with(software(product(501)),scanner(product(101))).
has(scanner(product(100)),requirement('One serial port, TWAIN compatible software')).
has(scanner(product(101)),requirement('One serial port, TWAIN compatible software')).
has(scanner(product(600)),requirement('One serial port or one SCSI connection, TWAIN compatible software')).
has_resolution_in(scanner(product(100)),density(600)).
has_resolution_in(scanner(product(101)),density(800)).
has_resolution_in(scanner(product(600)),density(1200)).
has_level_of(scanner(product(100)),bits(32)).
has_level_of(scanner(product(101)),bits(32)).
has_level_of(scanner(product(600)),bits(64)).
has_length(scanner(product(100)),size(6)).
has_length(scanner(product(101)),size(6)).
has_length(scanner(product(600)),size(16)).
has_width(scanner(product(100)),size(5)).
has_width(scanner(product(101)),size(5)).
has_width(scanner(product(600)),size(10)).
% Query Clauses
%
% Query a product
% query(product(Code), Name, Description, Weight)
%
% Get a product name
% get_name(product(Code),Name)
%
% Get product description
% get_description(product(Code),Description)
%
% Get product weight
% get_weight(product(Code),Weight)
%
get_name(product(Code),Name) :-
has(product(Code),product_name(Name)),!.
get_name(product(_),undefined).
get_description(product(Code),Description) :-
has(product(Code),description(Description)),!.
get_description(product(_),undefined).
get_weight(product(Code),Weight) :-
weighs(product(Code),weight(Weight)),!.
get_weight(product(_),undefined).
query(product(Code), Name, Description, Weight) :-
product(Code),
get_name(product(Code),Name),
get_description(product(Code),Description),
get_weight(product(Code),Weight).

The lines beginning with ‘%’ are comments that are ignored by the Prolog system. The version of Prolog used for this sample does not require stored facts (objects) to be declared in advance. The comments were added as documentation to show the reader how the ORM schema is represented in the Prolog program. It should be obvious that the conceptual nature of the ORM is very much preserved when implemented in Prolog. The major difference is the use of "prefix" syntax for predicates while the ORM uses a "mixfix" syntax.

As you can see, several Products and associated relationships are instantiated in the Prolog database. The objects were entered manually since this small program does not yet contain any rules to enforce constraints. However, it does contain several clauses (sentences) that allow a user to query the Prolog database using the conceptual objects and relationships present. The following "conversation" with the prolog database will demonstrate the conceptual nature of the interaction.

The Prolog system used for this example is the Amzi! Logic Explorer that is a free package available at http://www.amzi.com.

This first conversation asks to see all product id’s:

?- product(Product_Id).
Product_Id = 100 ;
Product_Id = 101 ;
Product_Id = 500 ;
Product_Id = 501 ;
Product_Id = 600 ;
no
?-

The ‘?-‘ symbol is the Prolog system prompt, the ‘;’ at the end of each line is a request to see another product id, and the ‘no’ at the end is the system telling me that it cannot find anymore products.

Now let’s ask for each product along with it’s name:

?- has(product(Product), product_name(Name)).
Product = 100
Name = 'Midget' ;
Product = 101
Name = 'Super Midget' ;
Product = 500
Name = 'Picture Perfect' ;
Product = 501
Name = 'OCR+' ;
Product = 600
Name = 'Ultra 1000' ;
no
?-

Queries may also filter information as in this next example that find all products with a cost greater than $100 :

?- has_cost_of(product(Product), money_amount(Cost)),
Cost > 100.
Product = 100
Cost = 175.000000 ;
Product = 101
Cost = 275.000000 ;
Product = 600
Cost = 1275.000000 ;
no
?-

The ‘,’ in the sentence is equivalent to a logical AND so that both parts of the sentence must be true to return information.

Although a knowledgeable user may query the system using the elemental objects, views may also be created for complex queries that are repeated, to return default values when information is not present and as an aid for the casual user. The example Prolog program contains four rules that implement views of the information. Three of the rules, get_name, get_description and get_weight are designed to simply find the corresponding object and return it’s value. The fourth view, query, is built up from the other three views and returns all three pieces of information at once.

For example:

?- query(product(100), Name, Description, Weight).
Name = 'Midget'
Description = '600 dpi b/w handheld scanner'
Weight = 2
yes
?-

Another example that finds products that weigh more than 5 lbs.:

?- query(product(Product), Name, Description, Weight),
Weight > 5.
Product = 500
Name = 'Picture Perfect'
Description = 'Imaging and graphics software'
Weight = 12 ;
Product = 501
Name = 'OCR+'
Description = 'OCR software'
Weight = 6 ;
Product = 600
Name = 'Ultra 1000'
Description = '1200 dpi color flatbed scanner'
Weight = 20 ;
no
?-

The ORM schema we used did not have any inverse relations. If it did, these can also be implemented very nicely in Prolog. If we wanted to add an inverse to the "Scanner has resolution in Density" relationship, we may say "Density is resolution for Scanner". In Prolog, we have a choice of how this may be implemented. The first choice is to simply add another fact: is_resolution_for(density(dpi), scanner(product(code))). The other choice is to define a rule that would represent the sentence: "Density is the resolution for a scanner if the scanner has a resolution of that density". This is defined in Prolog as:

is_resolution_for(density(DPI), scanner(product(Code))) :-
has_resolution_in(scanner(product(Code)),density(DPI)).

After defining this rule in the Prolog system, it may be used in the following manner:

?- query(product(Product), Name, Description, Weight),
is_resolution_for(density(DPI), scanner(product(Product))).
Product = 100
Name = 'Midget'
Description = '600 dpi b/w handheld scanner'
Weight = 2
DPI = 600 ;
Product = 101
Name = 'Super Midget'
Description = '800 dpi color handheld scanner'
Weight = 2.500000
DPI = 800 ;
Product = 600
Name = 'Ultra 1000'
Description = '1200 dpi color flatbed scanner'
Weight = 20
DPI = 1200 ;
no
?-

In order to completely implement a conceptual model, we must have the ability to enforce constraints. This last section will demonstrate how constraint enforcement can be accomplished using Prolog for some selected constraints. The approach in this article will be to check constraints on an existing schema. A full transaction processing system with full constraint support is beyond the scope of this article.

One of the most often encountered constraints is that of a mandatory role. For example, in our ORM, we have a mandatory role: Product has ProductName. To check the constraint, we can simply query the facts like this:

?- has(product(100), product_name(_)).
yes
?-

Since we only wanted to know if the product had a name, not necessarily the value of the name, the anonymous variable ‘_’ was used. As you can see, the system answered ‘yes’, because the name does exist. Now consider this:

?- retract(has(product(100),product_name(_))).
yes
?- has(product(100),product_name(_)).
no
?-

The name of the product was retracted (removed) from the Prolog database. Now when the facts are queried, the name is not found.

Most of the time we are asked to determine if a violation of constraints will occur before the database is changed. To use the method above, the newly asserted information could be tagged in some way and tested. If a violation was found, the information could be retracted using the tag. Another way would be to use a temporary database to stage the transaction, validate it and move it to the permanent database if no constraints were violated.

Another common constraint is to limit the number of times an object may participate in a role. In the Product schema above, a product has one, and only one, Description. We can easily verify that a Product has at least one description by asking:

?- has(product(100),description(Description)).
Description = '600 dpi b/w handheld scanner' ;
no
?-

In fact, this query could be used to determine if more than one description existed. A much better way, though, is to define a rule that can implement the conceptual notion of ‘exactly one’. The solution presented here counts the number of descriptions for a given product and checks if the sum is equal to 1.

% Constraints Enforcement
% exactly_one(has(product(code), description(text)))
% count(product(code), description, sum)
%
exactly_one(has(product(Code), description(Description))) :-
count(product(Code), description, Sum),
Sum = 1.
count(product(Code), description, Sum) :-
findall(Description,has(product(Code),description(Description)),
Description_List),
length(Description_List, Sum).

As you can see, the definition of exactly_one closely matches our conceptual notion of what it means to have an object participate in a role exactly once. The count clause that supports the exactly_one rule, however, is not easily understood without some knowledge of Prolog. The length clause, code not shown, is a general purpose utility for determining the size of a list.

Following are some examples using the exactly_one constraint:

?- exactly_one(has(product(100), description(_))).
yes
?- assert(has(product(100), description('another description'))).
yes
?- exactly_one(has(product(100), description(_))).
no
?- retractall(has(product(100), description(_))).
yes
?- exactly_one(has(product(100), description(_))).
no
?-

We saw earlier that ‘Product 100’ did indeed have only one description, so the first use of exactly_one answers ‘yes’. After asserting another description for ‘Product 100’ the answer to exactly_one becomes ‘no’. After removing all descriptions for ‘Product 100’ the answer is still no.

In summary, Prolog allows a constraint to be expressed in a conceptual manner and allows supporting and utility clauses to be defined that implement the constraint. In this manner, constraint clauses can be defined in a consistent manner, possibly to the point of automation.

This article has attempted to show that a Prolog implementation of a conceptual model, an ORM, can use language that is closely correlated to the language of the model. It showed how objects are defined and instantiated, and how roles are defined. Several query views were developed that demonstrate how Conceptual Information Processing Interface query views could be implemented. Lastly, constraints were addressed and it was mentioned that a method could be developed to implement a consistent conceptual constraint language in Prolog.

REFERENCES

Conceptual Modeling and Relational Database Design, Second Edition, Terry Halpin, Prentice Hall Australia, 1995

Programming in Prolog, Fourth Edition, W.F. Clocksin and C.S. Mellish, Springer-Verlag, 1994

InfoModeler Guide to FORML, Asymetrix Corporation, 1994

Amzi! Logic Explorer, Amzi! Inc., http://www.amzi.com

Dennis Corbo is an independent consultant specializing in information and knowledge engineering for business systems. His experience includes the development of metadata, business rules and logic systems for the financial, insurance and distribution industries. In addition, he spends much of his time reading, writing and evaluating business system requirements specifications. He considers ORM one of the best kept industry secrets.

Contact Information:

Dennis Corbo
MRO Inc.
368A Broad Street
Bloomfield, NJ 07003
corbo@bellatlantic.net

tel: (973) 748-0777
fax: (973) 748-1999

© Copyright, 1998-2004 InConcept (Information Conceptual Modeling, Inc.) All Rights Reserved. Privacy Statement.
ISSN: 1533-3825