% 
% 		Copyright 1985,1986,1987,1988,1989,1990,1991,1992,1993
% 	    by Microelectronics and Computer Technology Corporation (MCC)
% 				All Rights Reserved
% 
%            MCC/CARNOT CONFIDENTIAL AND PROPRIETARY
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%
% The Airline Intelligent Reservation System (AIRS)
%
% This is a LDL++ application that supports the queries
% for flight inquiry for a airline flight reservation system.
% These queries include finding the route, flights and mileage
% accumulated between cities.
%
% The purpose of this application is to demonstrate the recursive
% query processing capability and how such complex query can be
% expressed in a concise logical specification.
%
% In this demo, we will first list the cities and the travel
% agents involved.
% Then, we will show four main types of queries:
%  1. Given the source and destination cities, find all possible
%     routes, which includes the flight ids, transit cities and
%     the mileage accumulated
%     (Note the bonus mileage varies for different travel agent)
%  2. Given the source city, find all the possible cities and routes
%     to fly to.
%  3. Given the destination city, find all possible cities and routes
%     to fly from.
%  4. Find all the possible routes between all the cities.
%  5. Given the flight id, find the source and destination cities.
%
% Query 1-4 are complex recursive queries while query 5 is equivalent
% to traditional relational query expressable in SQL.
%

%
% Schema Declarations
%
% The following shows two tables/relations.
%
% The table "flight_info" has four columns and it stores
% the flight id, source city, destination city and the mileage
%
% The table "agent_info" has three columns and it stores
% the travel agent, the flight id and the bonus mileage granted
% for that particular flight id if the ticket is purchased through
% the travel agent.
%

database( {

  flight_info( FlightID:string, Source:string,
	       Destination:string, Mileage:integer ),
  agent_info( Agent:string, FlightID:string,
	      BonusMileage:integer )

	  } ).

index(flight_info, [1]).
index(flight_info, [2]).
index(flight_info, [1,2]).
index(agent_info, [0,1]).

%
% External C++ Function Declarations
%
% The declaration imports two C++ pretty-print routines,
% i.e. print_header and print_result.
% The purpose is to demonstrate the open architecture
% the LDL++ system to interface with procedural routines.
%

import foreign
  print_header( $Origin:string, $Destination:string,
	        $NumberOfOptions:integer ),
  print_result( $Agent:string, $Mileage:integer,
		$TransitList:list, $FlightIDList:list )
  from 'airline.o'.

%
% Exported Query Forms
%
% These are queries that are exported to the users.
%

export city( City ).
export travel_agent( TravelAgent ).
export flight_options( Source, Destination, NumberOfOptions ).
export flight_options( $Origin, Destination, NumberOfOptions ).
export flight_options( Source, $Destination, NumberOfOptions ).
export flight_options( $Origin, $Destination, NumberOfOptions ).
export flight( $FlightID, Source, Destination ).

%
% Rule Base
%

%
% flight_options( Source, Destination, NumberOfOptions )
%
% Find all the possible flight options for all the possible travel
% agents. Print the header for the number of possible options found
% and print each of the found option.
%

flight_options( Source, Destination, NumberOfOptions ) <-
	find_routes_and_mileage( Source, Destination, ResultSet ),
	cardinality( ResultSet, NumberOfOptions ),
	print_header( Source, Destination, NumberOfOptions ),
	print_options( ResultSet ).

%
% print_options( ResultSet )
%
% Print each flight option found
%

print_options( ResultSet ) <-
	member( (Agent, TransitList, FlightIDList, Mileage ), ResultSet ),
	print_result( Agent, Mileage, TransitList, FlightIDList ),
	false.
print_options( _ ).

%
% find_routes_and_mileage( Source, Destination,
%                          AgentTransitListFlightIDListMileageSet )
%
% Find set of routes, list of transit cities and mileage
%

find_routes_and_mileage( Source, Destination,
			 < (Agent, TransitList, FlightIDList, Mileage ) > ) <-
	travel_agent( Agents ),
	member( Agent, Agents ),
	route( Source, Destination, Agent, TransitList, FlightIDList, Mileage ).

%
% route( Source, Destination, Agent, TransitList,
%	 FlightIDList, TotalMileage )
%
% This is a recursive definition for a transitive closure.
%
% The first rule says that there is a route from one city to another
% if there is a direct flight from one to the other. 
% The total mileage is the flight mileage plus the bonus mileage.
%
% The second rule says that there is a route from city S to city D
% if there is a sub-route from city S to some transit city T and
% there is a direct flight from city T and city D.
% The total mileage is the summation of the total mileages for
% the sub-route and the direct flight.
%
% Note that cyclic route has to be avoided.
%

route( Source, Destination, Agent, [], [FlightID], TotalMileage ) <-
	flight_info( FlightID, Source, Destination, Mileage ),
	agent_info( Agent, FlightID, BonusMileage ),
	TotalMileage = Mileage + BonusMileage.

route( Source, Destination, Agent, TransitList, FlightIDList, TotalMileage ) <-
	route( Source, Transit, Agent, TransitList0, FlightIDList0, Mileage0 ),
	Source ~= Transit,
	flight_info( FlightID, Transit, Destination, Mileage1 ),
	Source ~= Destination,
	agent_info( Agent, FlightID, BonusMileage ),
	~member( Destination, TransitList0 ),
	append( TransitList0, [ Transit ], TransitList ),
	append( FlightIDList0, [ FlightID ], FlightIDList ),
	TotalMileage = Mileage0 + Mileage1 + BonusMileage.

%
% travel_agent( AgentSet )
%
% Find the set of travel agents.
%

travel_agent( < Agent > ) <-
	agent_info( Agent, _, _ ).

%
% city( City )
%
% Find all the cities.
%

city( City ) <-
	flight_info( _, City, _, _ ).
city( City ) <-
	flight_info( _, _, City, _ ).

%
% flight( FlightID, Source, Destination )
%
% A derived view of the flight information.
%

flight( FlightID, Source, Destination ) <-
	flight_info( FlightID, Source, Destination, _ ).