The MLPQ/GIS Constraint Database System

P. Revesz, R. Chen, P. Kanjamala, Y. Li, Y. Liu, Y. Wang

The current version of the MLPQ/PReSTO system merges the MLPQ/GIS and the PReSTO constraint database systems, which were both built at the University of Nebraska-Lincoln partially funded by the USA NSF under grants IRI-9625055 and IRI-9632871. The executable file of the MLPQ/PReSTO system, running Microsoft 2000, and all the sample text files listed in the appendix are available free as down-loadable files from the webpage: http://www.cse.unl.edu/ revesz, which also contains a list of publications related to both the MLPQ/GIS and the PReSTO systems. The present HTML document gives a brief introduction to the MLPQ/PReSTO system, based on the demo given by the authors at SIGMOD'2000 and extended with recent work on the PReSTO system by M. Cai, D. Keshwani, and P. Revesz.

1 Syntax

MLPQ/PReSTO accepts as input a ``.txt'' file. The input file can be opened by going to the {File} menu, and selecting the {Open} dialog. The syntax of the input is almost the same as that of traditional Datalog, with the following restrictions:

In the MLPQ/PReSTO system each input file is a set of rules bracketed by the keywords begin and end. It has the following structure:

begin %moduleName%
tex2html_wrap_inline588
tex2html_wrap_inline590

tex2html_wrap_inline592
end %moduleName%

where each tex2html_wrap_inline594 is a rule or a constraint tuple, and moduleName is a string. The module name should be the following.

``MLPQ'' - when each rule is as described in Section 1.1 and the program in the input file is non-recursive.

``RECURSIVE'' - when each rule is as described in Section 1.1 and the program in the input file is recursive.

``GIS'' - when each rule is as described in Section 1.2.

``STDB'' - when each rule is as described in Section 1.3.

1.1 MLPQ Syntax

 

MLPQ linear constraint rules may be specified in the form of equation (4.1) in the textbook, or as in Chapter 5 with the following differences.

First, each linear constraint must have the form

displaymath596

where each tex2html_wrap_inline598 is a constant and each tex2html_wrap_inline600 is a variable, and tex2html_wrap_inline602 is a relational operator of the form =, <, >, <=, >=.

Second, the optional aggregate operator has the form OP(f) where OP is one of the aggregate operators max, min, MAX, MIN, tex2html_wrap_inline624 or tex2html_wrap_inline626 , and f is a linear function of the variables in the rule. The aggregate operators have the following meanings.

max - gets maximum value for each constraint tuple.

sum_max - finds the sum of the values returned by max.

MAX - finds the maximum of the values returned by max.

min, MIN and sum_min are defined similarly to the above.

Third, for negation the symbol ! is used instead of not.

1.2 GIS Syntax

 

We sometimes restrict the head of the rules to be one of the following: r(id,x,y), or r(id,x,y,t) or r(id,x,y,z) where id is the identification number of an object, and x,y are two spatial variables, which could be augmented by a temporal variable t or a third spatial variable z. These cases of linear constraint databases allow us to do some extra operations that are special to GIS objects.

1.3 PReSTO Syntax

 

  1. PReSTO Relation: A relation R in PReSTO is defined as follows:

    tabular117


    where

    tabular125


    Note: For non-periodic relations, tex2html_wrap_inline692 , tex2html_wrap_inline694 . The attributes id, x1, y1, x2, y2, t, p, s are default attributes.

  2. PReSTO Database: The PReSTO database must use ``STDB'' as the module name; that is, the input file must have the structure:

    tabular139


  3. PReSTO Query:

    1. Define a relation with non-default attributes.

      Example: Define the cloud relation with the attribute humidity. 

          clouds(h) :- i=1,
                 x1 - t = 105, 
                 y1 - 0.5t = 200,
                 x2 - t = 111, 
                 y2 - 0.6t = 205,
                 t >=0, t<=300,
                 p = -1, s = 0,
                 h = 0.
    2. Selection: tex2html_wrap_inline720 .

      Example: Find the cool area in Nebraska. 

        begin %STDB%
    Nebraska(temp) :- i=1, x1=4, y1=4.5, x2=19.5, y2=14.5,
                      t>=1,t<=15, p=-1,temp=30.
    Nebraska(temp) :- i=2, x1=20, y1=4.5, x2=35, y2=14.5,
                      t>=1,t<=15, p=-1,temp=90.
    Nebraska(temp) :- i=3, x1=35.5, y1=5, x2=46, y2=14.5,
                      t>=1,t<=15, p=-1,temp=60.

    cool_area(temp):- $(temp>=50,temp<=80)nebraska(temp).
  end %STDB%
    3. Projection: tex2html_wrap_inline722
    4. Intersection: Relation1 * Relation2.

      Example: Find if the ship and the torpedo will meet with each other. 

        begin %STDB%
    ship() :-     i=1,
                  x1-t=20,y1=20,
                  x2-t=30,y2=25,
                  t>=0,t<=25,
                  p=-1,s=-1.

    torpedo() :-  i=1,
                  x1=45,y1+t=45,
                  x2=48,y2+t=51,
                  t>=0,t<=25,
                  p=-1,s=-1.

    hit() :-      ship() * torpedo().
  end %STDB%

2 Operators

The MLPQ/PReSTO graphical user interface shown in Figure 1 contains a list of iconic queries.

   figure155
Figure 1: MLPQ Graphical User Interface

2.1 MLPQ Operators

Section 1: The [Query (Q)] Operator and [Buffer] Operator

   figure166
Figure 2: Buffer Example

  1. Consider Figure 2 which shows a map of interstate highway I-80, the location of hotels, the locations of exits form the highway, and the current location of a car traveling from west to east on the highway.

    Query: Find a convenient hotel to stay for the night. This is done by finding the nearest exit east of the current location of the car and then find the hotel within 50 miles from that exit.

    1. Click [Q], input the query to get the nearest exit on the east.

      tabular177


    2. Select ``Nearest'' Relation, click [Buffer].
    3. Input name ``Buf_Nearest'', and the Distance ``50''.
    4. Click [Q], input the query to get the convenient hotel away from at most 50 miles.

      displaymath728

Section 2: The [Line] Operator, [Rectangle] Operator and [Polygon] Operator

  1. Drawing Line:

    1. Open a non-empty database (i.e., a database that already contains at least one relation);
    2. Left click the right window;
    3. Left click [Line];
    4. Left click the mouse to get one point, move mouse, then left click the mouse to get another point;
    5. Input the relation name ``Line1'' (any string) to get the line relation ``Line1''.

  2. Drawing Rectangle:

    1. Open a non-empty database (i.e., a database that already contains at least one relation);
    2. Left click the right window;
    3. Left click [Rectangle];
    4. Left click the mouse to get one point, move mouse, then left click the mouse to get another point;
    5. Input the relation name ``Rectangle1'' (any string) to get the rectangle relation ``Rectangle1''.

  3. Drawing Polygon:

    1. Open a non-empty database (i.e., a database that already contain at least one relation);
    2. Left click the right window;
    3. Left click [Polygon];
    4. Left click the mouse to get one point, continue to left click the mouse to get other points;
    5. Double click to finish the drawing.
    6. Input the relation name ``Polygon1'' (any string), and the Object ID ``1'' (any integer number) to get the polygon relation ``Polygon1''.

  4. Show Constraints: After operation 2, left click the relation ``New_relation'' in the left window, to get the dialog which shows the constraints of this relation.

Section 3: The [Zoom Out] Operator and [Zoom In] Operator

  1. To enlarge or shrink the displayed object, click [Zoom In] or [Zoom Out].
  2. Left push down the mouse, include the object, then release the button. The selected object will be enlarged.

Section 4: The [Area] Operator

  1. Area: Calculate the area of relation ``Buf_Nearest''.

    1. Select the Generated relation ``Buf_Nearest'' in the left window.
    2. Click [Area].
    3. Input the MinX, MaxX, and Step Size of the area to be calculated. By referring the coordinates of the window, input the number for MinX ``0'', and MaxX ``400'', and the Step Size ``400'', then get the total area of the relation since it is in the region totally.
    4. Input the area relation name ``Buf_Nearest_Area'', left click it to show the area in constraints.

    Note: The step size is to get various aggregate information for different bands of the object.

  2. Bands Area: Calculate the area of relation ``Buf_Nearest'' with bands.

    1. Select the Generated relation ``Buf_Nearest'' in the left window.
    2. Click [Area].
    3. Input the MinX ``0'', the MaxX ``400'', the Step Size ``200''.
    4. Input the relation name ``Buf_Nearest_Area'', left click it to show the areas of these two bands from 0 to 200 and 200 to 400 in constraints.

Section 5: The [Intersection ( tex2html_wrap_inline752 )] Operator and [Union ( tex2html_wrap_inline754 )] Operator

  1. Intersection: Calculate the intersection of two relations.

    1. Select two relations from the left window which have the same attributes.
    2. Click [ tex2html_wrap_inline752 ].
    3. Input relation name ``Intersect'' which is the intersection of these two relations.

    Note: For intersection, the system also matches the ids of the objects. So if two objects have the different ids, then the intersection would be empty.

    Hint: To make two relations R1(id, x, y) and R2(id, x, y) have the same id, insert the following Datalog query (``New_R1'' and ``New_R2'' will have the same id ``1''):

    displaymath729

    displaymath730

  2. Union: Calculate the union of two relations.

    1. Select two relations from the left window.
    2. Click [ tex2html_wrap_inline754 ].
    3. Input the relation name ``Union'' which is the union of these two relations.

    Note: for union, these two relations need not to have the same id since they are still in the output even they have different ids.

Section 6: The [Max] Operator and [Min] Operator

  1. Max: Calculate the maximum value for a given evaluation function.

    1. crops.txt: Calculate the maximum profit for the evaluation function: 300corn + 250rye + 100sunflower + 150wheat.

      1. Select the relation ``crops'' from the left window.
      2. Click [Max].
      3. Input new relation name ``max_profit'', the evaluation function ``300corn+250rye+100sunflower+150wheat'', and the constant value for the evaluation function is ``0''.
      4. Right click the relation ``max_profit'' to show the maximum profit.

  2. Min: Calculate the minimum value for a given evaluation function.

    1. Select one relation from the left window.
    2. Click [Min].
    3. Input new relation name ``min_rel'', the evaluation function, and the constant value for the evaluation function.
    4. Right click the relation ``min_rel'' to show the minimum value.

    Note: The [Max] and [Min] operators only work for the evaluation function which will return the positive maximum/minimum value.

Section 7: The 2D Animation

  1. sface.txt: select relations one by one, then click [Play], then see the face becomes smiling.

       figure246
    Figure 3: Two Snapshots of a Video on California Gull Ranges

  2. Consider Figure 3 which shows two snapshots of the habitat range of the California Gull birds. The data is available in file sgull.txt. Select all except Gull, then select ``Gull'' relation, then click [Play], then see the gull changing.

    Query 1: How much did the area of the California Gull change from 1970 to 1990?

    1. Click [Q] to insert the query to get the Gull snapshot at 1970:

      displaymath731

    2. Click [Q] to insert the query to get the Gull snapshot at 1990:

      displaymath732

    3. Click the relation ``Gull0'', then click [Area] to get the area of the Gull at 1970. Input the MinX=0, MaxX=500 and Step=500. Give the name of the area of the relation ``Gull0'' as ``Gull0_Area''.
    4. Click the relation ``Gull60'', then click [Area] to get the area of the Gull at 1990. Input the MinX=0, MaxX=500 and Step=500. Give the name of the area of the relation ``Gull60'' as ``Gull60_Area''.
    5. Click [Q] to insert the query to get the area difference of the California Gull t between 1970 and 1990:

      tabular261


    6. Right Click the relation ``CA_Gull_Area_Diff'' to show the constraints and the area difference.

    Query 2: How much did the area of the California Gull change from 1970 to 1990 in the state of California?

    1. Click [Q] to insert the query to get the Gull snapshot at 1970:

      displaymath733

    2. Click [Q] to insert the query to get the Gull snapshot at 1990:

      displaymath734

    3. Select the relation ``Gull70'' and ``CA'', then click [ tex2html_wrap_inline752 ] to get the area of the Gull at 1970 in the state of California. Input the relation name ``CA_Gull70''.
    4. Click the relation ``Gull90'' and ``CA'', then click [ tex2html_wrap_inline752 ] to get the area of the Gull at 1990 in the state of California. Input the relation name ``CA_Gull90''.
    5. Click the relation ``CA_Gull70'', then click [Area] to get the area of the Gull at 1970 in the state of California. Input the MinX=0, MaxX=500 and Step=500. Give the name of the area of the relation ``CA_Gull70'' as ``Gull70_Area''.
    6. Click the relation ``CA_Gull90'', then click [Area] to get the area of the Gull at 1990 in the state of California. Input the MinX=0, MaxX=500 and Step=500. Give the name of the area of the relation ``CA_Gull90'' as ``Gull90_Area''.
    7. Click [Q] to insert the query to get the area difference of the California Gull t between 1970 and 1990 in the state of California:

      tabular267


    8. Right Click the relation ``CA_Gull_Area_Diff'' to show the constraints and the area difference.

  3. Consider the file slincoln.txt. Select ``City'' relation, then click [Play], then see the Lincoln, Nebraska city area changing.

Section 8: The Exponential 2D Animation

  1. mulcolony.txt:

    1. Select the relation from the left window.
    2. Click [(Animation (A)] then click ``Yes'' for observing the exponential animation.

    Note: If click [A] then click ``No'', then execute the linear animation.

  2. sincolony.txt: Click [(Animation (A)] then click ``Yes'' for observing the exponential animation.
  3. sinirreg.txt: Click [(Animation (A)] then click ``Yes'' for observing the exponential animation.
  4. threecolony.txt: Click [(Animation (A)] then click ``Yes'' for observing the exponential animation.

Section 9: Recursive Queries

  1. houses.txt: the relation ``can_build'' is created by recursive Datalog query. See the constraint tuples of the relation.
  2. pollution.txt: the relation ``oktobuy'' is created by recursive Datalog query. See the constraint tuples of the relation, not the display result.
  3. powernew.txt: the relation ``can_build'' is created by recursive Datalog query. See the constraint tuples of the relation, not the display result.

    Note: For [Q] Operator, the recursive query only can be inserted into recursive database, that is, the new recursive query could be inserted only when the current database is recursive.

Section 10: The Transformation from the TIN to Constraint Database

  1. tin_ia.net: Transform the TIN of Iowa to constraint database.

    1. Click menu {New}, then click submenu {File}, click {Import File}, then click {Elevation File}.
    2. Choose the file ``tin_ia.net''.
    3. Input the relation name ``tin_ia'', then input ``tin_ia_ascii'' in the third filed, click ok button to Generate the constraint file ``tin_ia.txt''.
    4. Use Notepad to open the file ``tin_ia.txt'' to see the transformed constraints.

    Note: The file ``tin_ia.net'' is the TIN structure of Iowa State with the longitude, latitude and elevation for each point. The file ``tin_ia_ascii'' includes the slope and aspect of each point.

  2. tin_ne.net: Transform the TIN of Nebraska to constraint database.

    1. Click menu {New}, then click submenu {File}, click {Import File}, then click {Elevation File}.
    2. Choose the file ``tin_ne.net''.
    3. Input the relation name ``tin_ne'', then input ``tin_ne_ascii'' in the third filed, click ok button to generate the constraint file ``tin_ne.txt''.
    4. Use Notepad to open the file ``tin_ne.txt'' to see the transformed constraints.

Section 11: The Transformation from Polygon File to Constraint Database

  1. veg90.pol: Transform polygon file to constraint database.

    1. Click menu {New}, then click submenu {File}, click {Import File}, then click {Elevation File}.
    2. Choose the file ``veg90.pol''.
    3. Input the relation name ``vege''.
    4. Click the ``vege'' relation in the left window, you will see the constraint tuples of these polygons.

Section 12: The [Similarity (S)] Operator for Similarity Queries

  1. db.lin: Query similarities among the lines.

    1. Click menu {New}, then click submenu {File}, then click {Import File}, then click {Import Line}.
    2. Select the file ``db.lin''.
    3. Input the relation name ``lines''.
    4. Then select any one relation, then click [S], then the relations are ordered as the similarity order from the specified one.

Section 13: Querying Maps

  1. usmap_info.txt:

    1. Select all of the relations, then see the U.S. map with 50 states.
    2. The scale of this map is shown by clicking the constraints of the relation ``Scale'', the unit is kilometer.
    3. The ``Capital'' relation is the capital cities of the states.

    Query 1: Find the capital city of Nebraska:

    1. Click [Q], then input

      displaymath735

    2. Right click the relation ``NE_capital'' to see the capital city of Nebraska State.

    Query 2: Find the area of the state of Nebraska in MST zone.

    1. Click [Q], then input

      displaymath736

    2. Select the relation ``NE_MST'', then click [Area].
    3. Input MinX=0, MaxX=500 and Step=500.
    4. Input the name of the area relation as ``NE_MST_Area''.
    5. Then right click the relation ``NE_MST_Area'' to see the area of the state of Nebraska in MST zone.

2.2 GIS Operators

Section 1: The [Set] Operator and [Color Relation] Operator for Color Bands Display

  1. Color_Circle.txt:

    1. Select ``Circle'' relation, see the monochromatic circle.
    2. Select ``NEW_Circle'' relation, then click [Color Relation].
    3. Select the new Generated ``Color_NEW_Circle'' relation, see the color circle (if not, click the {View} Menu, uncheck {Same Relation Color} Option).

  2. tin.txt:

    1. Select ``tin'' relation, click [Color Relation].
    2. Select the Generated ``Color_tin'' relation, then see the color Nebraska (different colors stand for different heights of those places).

  3. tiniowa_final.txt:

    1. Select ``tiniowa_final'' relation, then click [Set], then click add button in the dialog, then input ``1000'', ``5000'' and select ``red'' color. Then click the ok button.
    2. Then click [Color Relation], then select the new Generated ``Color_tiniowa_final'' relation, then see the red partial Iowa state (only the heights between 1000 and 5000 are displayed). (If it's not red, then select {View} menu, then uncheck {Same Relation Color}.)

  4. tinne_final.txt:

    1. Select ``tinne_final'' relation, then click [Set], then click add button, then input ``1000'', ``3000'' and select ``blue'' color. Then click ok button.
    2. Then click [Color Relation], then select ``Color_tinne_final'' relation, then see the blue partial Nebraska state (only the heights between 1000 and 3000 are displayed). (If it's not blue, then select {View} menu, then uncheck {Same Relation Color}.)

  5. tinresult.txt: Monochromatic map display. Select ``tin'' relation, then see the Nebraska state map, also shown in Figure 4.

  figure345
Figure 4:   Mean Annual Air Temperature

2.3 PReSTO Operators

Section 1: The [Intersection ( tex2html_wrap_inline752 )] Operator and [Union ( tex2html_wrap_inline754 )] Operator

  1. weather.txt:

    Query 1: Find which region is likely to get rain.

    1. Select the relation ``cool_area'' and ``wet_cloud'' from the left window.
    2. Click [ tex2html_wrap_inline752 ].
    3. Input a relation name ``get_rain'' which is the intersection of these two relations.

    Query 2: Find which region is likely to get snow.

    1. Select the relation ``cold_area'' and ``wet_cloud'' from the left window.
    2. Click [ tex2html_wrap_inline752 ].
    3. Input a relation name ``get_snow'' which is the intersection of these two relations.

    Query 3: Find which region is likely to get rain or get snow.

    1. Select the relation ``get_rain'' and ``get_snow'' from the left window.
    2. Click [ tex2html_wrap_inline754 ].
    3. Input a relation name ``get_rain_snow'' which is the union of these two relations.

  2. flight.txt:

    Query: Will the plane hit the fleet?

    1. Select the relation ``plane'' and ``fleet'' from the left window.
    2. Click [ tex2html_wrap_inline752 ].
    3. Input a relation name ``hit_fleet'' which is the intersection of these two relations.

Section 2: The [Area] Operator

  1. cloudmap.txt:

    Query: Find the area of the clouds at time 10.

    1. Select the relation ``clouds'' from the left window.
    2. Click [Area].
    3. Input the time of the clouds ``10''.
    4. A dialog box pop up to give the area of the clouds at time ``10''.

Section 3: The [Difference (-)] Operator

  1. cloudmap.txt:

    1. Select the relation ``california'' and ``clouds'' from the left window.
    2. Click [-].
    3. Input the relation time ``diff''.
    4. Click the relation ``diff'' which shows the difference between California and the clouds at time ``0''.

Section 4: The [Complement (C)] Operator

  1. cloudmap.txt:

    1. Select the relation ``clouds'' from the left window.
    2. Click [C].
    3. Input the relation time ``comp''.
    4. Click the relation ``comp'' which shows the complement of clouds at time ``0''.

Section 5: The [Query (Q)] Operator

  1. weather.txt:

    1. Click [Q].
    2. To get the area where the temperature between 50 and 80, input the query:

      displaymath788

    3. Click the relation ``cool'' which shows the interested area.

Section 6: The [Collide (X)] Operator

  1. collide.txt:

    1. Select all relations, then click [Play], then see both are moving.
    2. Click [Collide], input the relation name ``collide''.
    3. Then select the new generated relation ``collide'', then click [Play], then see them collide then bounce back from each other.

Section 7: The [Block (B)] Operator

  1. yellowstone.txt: Foam blocks the fire.

    1. Select the relation ``lake'' and the relation ``foam1''.
    2. Click [ tex2html_wrap_inline754 ], give the relation name ``blocks''.
    3. Select the relation ``blocks'' and the relation ``fire''.
    4. Click [Block], input the relation name ``blockfire'' and set time ``10''.
    5. Click [Forward] button 10 times till t = 10. Then see the snapshot of the blocked fire at that time.

Section 8: The 2D Animation

  1. halley.txt: select all relations, then click [Play], then see Halley hit some stars.
  2. comet3.txt: select all relations, then click [Play], then see they are moving.
  3. flight.txt: select all relations, then click [Play], then see the planes hit the targets.
  4. shuttle.txt: select all relations, then click [Play], then see the bus is moving.
  5. torpedo.txt: select all relations, then click [Play], then see the torpedo is moving.
  6. weather.txt: select all relations, then click [Play], then see the result.
  7. cloudmap.txt:

    1. Select all relations except ``clouds'' relation, then select ``clouds'' relation, click [Play], then see the cloud is moving. Two snapshots of the animation are shown in Figure 5.

        figure426
      Figure 5:   Cloud at t=25 (left) and t=182 (right) in the PReSTO system

    2. Click [Animation], change the speed to ``95'', then the animation speed will be slower than it was ``100''.

APPENDIX: Input Databases

  1. MLPQ Databases: The files in database/MLPQ are as follows: 

    Color_Circle.RNG
Color_Circle.txt
buffer.txt
cost.dat
Crops.txt
db.lin
houses.txt
linear.txt
mulcolony.txt
pollution.txt
powernew.txt
sface.txt
sgull.txt
sincolony.txt
sinirreg.txt
slincoln.txt
threecolony.txt
tin.RNG
tin.txt
tin_ia.net
tin_ia_ascii
tin_ia_data
tin_ne.net
tin_ne_ascii
tin_ne_data
tiniowa_final.txt
tinne_final.txt
tinresult.RNG
tinresult.txt
usmap_info.txt
veg90.pol
vege.ldb
vege.mdb
vege_db
  2. PReSTO Database: The files in database/PReSTO are as follows: 

    cloudmap.txt
collide.txt
comet3.txt
fight.txt
halley.txt
torpedo.txt
weather.txt
yellowstone.txt

About this document ...

The MLPQ/GIS Constraint Database System

This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 -show_section_numbers specification.tex.

The translation was initiated by Peter Revesz on Sun Feb 4 11:33:25 CST 2001

Peter Revesz
Sun Feb 4 11:33:25 CST 2001