How to sort list of sublists as per key/keys of sublist?

[Lev777]

I have the following structure:

object('obj1', [id='12', color='blue']).

object('obj4', [id='13', color='red', weight=120]).

object('obj21', [id='15 a', color='yellow', weight=1000, price=23]).

object('obj21', [id='16 a', color='blue', weight=200, price=230]).

I have a predicate which finds all objects with particular key, e.g. objects with color='blue'.

In many cases result will be list of objects.

My question is:

How to write a sorting predicate which will sort objects within a resulting list by one of one or many  keys(id or/and price, etc...)

Thanks! 

[Willem Robert van Hage]

Dear Levan,

On Jun 10, 2009, at 9:25 AM, Levan Cheishvili wrote:

> I have the following structure:
>
> object('obj1', [id='12', color='blue']).
> object('obj4', [id='13', color='red', weight=120]).
> object('obj21', [id='15 a', color='yellow', weight=1000, price=23]).
> object('obj21', [id='16 a', color='blue', weight=200, price=230]).
>
> I have a predicate which finds all objects with particular key, e.g.  
> objects with color='blue'.
> In many cases result will be list of objects.
> My question is:
> How to write a sorting predicate which will sort objects within a  
> resulting list by one of one or many  keys(id or/and price, etc...)

You define a predicate that states if an object should be ordered  
before, after, or either before or after, another object.
Then you call predsort/3 with this comparison predicate as first  
argument.

For example (perhaps not the most elegant or efficient way to do it...):

object_id_value(object(_,L), ID) :-
        member((id=ID), L).

compare_objects_by_id(<, X, Y) :-
        object_id_value(X, N),
        object_id_value(Y, M),
        sort([N,M], [N|_]).

compare_objects_by_id(>, X, Y) :-
        object_id_value(X, N),
        object_id_value(Y, M),
        sort([N,M], [M|_]).

compare_objects_by_id(=, _, _).


?- predsort(compare_objects,
   [
     object('obj21', [id='16 a', color='blue', weight=200, price=230]),
     object('obj1', [id='12', color='blue']),
     object('obj21', [id='15', color='yellow', weight=1000, price=23]),
     object('obj4', [id='13', color='red', weight=120])
   ],
   [
     object('obj1', [id='12', color='blue']),
     object('obj4', [id='13', color='red', weight=120]),
     object('obj21', [id='15', color='yellow', weight=1000, price=23]),
     object('obj21', [id='16 a', color='blue', weight=200, price=230])
   ]).
true.
       

You can combine the keys and their values in any particular way in the  
comparison predicate.

Cheers!

Willem

--
Dr. Willem Robert van Hage
Vrije Universiteit Amsterdam
wrvhage@... - http://www.few.vu.nl/~wrvhage






_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Ulrich Neumerkel]

Levan Cheishvili writes:
> For example (perhaps not the most elegant or efficient way to do it...):

There are two common ways to define sorting.  One is by defining a
comparison predicate, as you have done, and the other is mapping with
maplist/3 the list to a list of the form Key-Value, keysorting that
and mapping it back.  To me, using keysort/2 is still the more natural
way - maybe because keysort/2 is more common.  Also, ill defined
mappings result typically in a failure of the mapping - and not in
random results.


Your predicate compare_objects_by_id/3 can be generalized to
compare_objects_by/1 which illustrated the usage of continuations.

?- predsort(compare_objects_by(id), [object(o1,[id=2]),object(o0,[id=1])] , Ks).


object_id_value(Id,object(_,L),Val) :-
        member((Id=Val), L).

compare_objects_by(Id,<, X, Y) :-
        object_id_value(Id, X, N),
        object_id_value(Id, Y, M),
        sort([N,M], [N|_]).

compare_objects_by(Id,>, X, Y) :-
        object_id_value(Id,X, N),
        object_id_value(Id,Y, M),
        sort([N,M], [M|_]).

compare_objects_by(_,=, _, _).

However, there is another point here.  Is comparison really well
defined?  Are there terms, that compare both > and < ? Or > and =?  If
you look at the last fact...

?- compare_objects_by(qq1,=,qq2,qq3).

This means that all objects are equal - provided someone asks that
question!

Further, consider when ?- compare_objects_by(Id,<,X,Y). may fail.  It
does not only fail, if X >= Y, it also fails if one of the first two
goals in the corresponding rule fails.  E.g., if a term is not an
object, or if the key is not provided.

?- predsort(compare_objects_by(weight), [ noobject,object(obj21, [weight=200])],Xs).
Xs = [noobject].
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Richard O'Keefe]

On 10 Jun 2009, at 7:25 pm, Levan Cheishvili wrote:

> I have the following structure:
>
> object('obj1', [id='12', color='blue']).
> object('obj4', [id='13', color='red', weight=120]).
> object('obj21', [id='15 a', color='yellow', weight=1000, price=23]).
> object('obj21', [id='16 a', color='blue', weight=200, price=230]).

I assume that that's a table of facts, so

:- type eq ---> =(atom,any).
:- pred object(atom, list(eq)).

The first thing that strikes me is that the Prolog convention for
a list of key-value pairs has been a list of Key - Value terms
since about 1979, that's 30 years.  There is a standard predicate
called keysort/2 for sorting such lists.  So why are you using
(=)/2 for your pairs instead of (-)/2?

[It's not that (-)/2 is a specially brilliant choice, although since
it is very often used with collections of pairs that are _not_ finite
maps, it's definitely better than (=)/2.  The point is just that it
is the _better-supported_ choice.]

How come you have two facts for obj21?

> I have a predicate which finds all objects with particular key, e.g.  
> objects with color='blue'.

The second thing that strikes me is that what you really have
seems to be a ternary relation,

oav(obj1, id,     12). % Object Attribute Value
oav(obj1, colour, blue).
oav(obj4, id,     13).
oav(obj4, colour, red).
oav(obj4, weight, 120).

Or possibly a collection of binary relations

id(obj1, 12).
id(obj4, 13).

colour(obj1, blue).
colour(obj4, red).

weight(obj4, 120).

All things considered, I think the binary relations are the way I'd
do it.  We can recover the other views if we really have to:

oav(Obj, id,     X) :- id(Obj, X).
oav(Obj, colour, X) :- colour(Obj, X).
oav(Obj, weight, X) :- weight(Obj, X).
oav(Obj, price,  X) :- price(Obj, X).

object(Obj, Attrs0) :-
     ( id(Obj,     I) -> Attrs0 = [id    =I|Attrs1] ; Attrs1 = Attrs0 ),
     ( colour(Obj, C) -> Attrs1 = [colour=C|Attrs2] ; Attrs2 = Attrs1 ),
     ( weight(Obj, W) -> Attrs2 = [weight=W|Attrs3] ; Attrs3 = Attrs2 ),
     ( price(Obj,  P) -> Attrs3 = [price =P|Attrs4] ; Attrs4 = Attrs3 ),
     Attrs4 = [].

If you want to find all the objects that are blue,

        setof(Obj, colour(Obj, blue), Blue_Objs)
or even
        findall(Obj, colour(Obj, blue), Blue_Objs)

is a lot easier than

        setof(Obj, ( object(Obj, Attrs), member(colour=blue, Attrs) ),
              Blue_Objs)

> My question is:
> How to write a sorting predicate which will sort objects within a  
> resulting list by one of one or many  keys(id or/and price, etc...)

There are several ways to do it.
One way is to exploit the fact that keysort is stable.
So sort by the least significant key first,
then the second least significant key,
...
and finally sort by the most significant key.

To sort a list by a particular key, simply take a list whose
elements are X and make a list whose elements are Key-X, and
sort that.  If you want to sort in decreasing order, just
reverse the result.

If you want ascending order for everything (except possibly
numbers, which you can negate), you can simply build
one super-key containing all the others.

For example, suppose you want to find all the blue objects
and sort them by decreasing price and (within the same price
level) increasing id.

     setof( key(Minus_Price,Id) - Object
          , ( colour(Object, blue),
              price(Object, Price), Minus_Price is -Price,
              id(Object, Id)
            )
          , Pairs),
     pairs_values(Pairs, Objects)

where pairs_values/2 is described in http://www.cs.otago.ac.nz/staffpriv/ok/pllib.htm

That draft library specification also calls for
sort/3 and msort/3.  There is a file which was written
for that but never included, because there seemed to be
very little interest in a standard library for Prolog.
I've attached it.  It's called msort.pl, and I've deleted
msort/2 from it because SWI Prolog already has msort/2.

With this, you would write a 3-way comparison predicate.
Using the binary relations version of your data,
you'd write

price_and_id_compare(R, Obj1, Obj2) :-
     price(Obj1, Price1),
     price(Obj2, Price2),
     compare(R1, Price2, Price1),  % note argument order!
     (   R1 == (=) ->
        id(Obj1, Id1),
        id(Obj2, Id2),
        compare(R, Id1, Id2)
     ;/* prices differ */
        R = R1
     ).

Then given a list of objects you could do

     msort(price_and_id_compare, Objects, Sorted_Objects)

if you want to keep duplicates, or sort/3 to discard them.


[msort.pl]

---

:- module(msort, [
    msort/3, % accept a comparison predicate, keep duplicates
    sort/3, % accept a comparison predicate, discard duplicates
    merge/4, % combine sorted lists keeping duplicates
    union/4, % combine sorted lists discarding duplicates
    key_compare/3, % so msort can do keysort.
    key_compare/4, % generalisation of key_compare/3,
    reverse_compare/3, % compare/3 with last two arguments swapped.
    reverse_key_compare/3,
    reverse_key_compare/4
]). % "duplicates" = "things that compare equal".

:- meta_predicate
    msort(3, +, ?), sort(3, +, ?),
    msort(+, +, -, -, 3), sort(+, +, -, -, 3),
    merge(3, +, +, ?), union(3, +, +, ?),
    merge_0(+, +, -, 3), union_0(+, +, -, 3),
    merge_1(+, +, -, 3, +), union_1(+, +, +, -, 3),
    merge_2(+, +, -, 3, +), union_2(+, +, +, +, +, -, 3),
    merge_12(+, +, -, 3, +, +, +).

/*  The plain predicates can be recovered by passing compare/3:

    msort(L, S)      :- msort(compare, L, S).
    sort( L, S)      :- sort( compare, L, S).
    merge(L1, L1, M) :- merge(compare, L1, L2, M).
ord_union(S1, S2, U) :- union(compare, S1, S2, U).
*/

/* pred
        msort(+Cmp, +List, ?List),
            msort(+integer, +List, -List, -List, +Cmp),
        sort( +Cmp, +List, ?List),
            sort( +integer, +List, -List, -List, +Cmp),
                sort2(+order, +T, +T, -List),
        merge(+Cmp, +List, +List, ?List),
            merge_0(+List, +List, -List, +Cmp),
                merge_1(+List, +List, -List, +Cmp, +T),
                merge_2(+List, +List, -List, +Cmp, +T),
                merge_12(+order, +List, -List, +Cmp, +T, +List, +T),
        union(+Cmp, +List, +List, ?List),
            union_0(+List, +List, -List, +Cmp),
                union_1(+List, +T, +List, -List, +Cmp),
                    union_2(+order, +T, +List, +T, +List, -List, +Cmp),
        key_compare(-order, +pair(X,Y), +pair(X,Y)),
        key_compare(+integer, -order, T, T),
        reverse_compare(-order, +T, +T),
        reverse_key_compare(-order, +pair(X,Y), +pair(X,Y)),
        reverse_key_compare(+integer, -order, +pair(X,Y), +pair(X,Y))
   where
        Cmp = void(-order, +T, +T),
        List = list(T).
*/


msort(C, List, Sorted) :-
    length(List, N),
    (   N >= 2 -> msort(N, List, _, S, C), Sorted = S
    ;   Sorted = List
    ).

msort(1, [X|Xs],   Xs, [X], _) :- !.
msort(2, [X,Y|Xs], Xs, S,   C) :- !,
    call(C, R, X, Y),
    (   R = (>) -> S = [Y,X]
    ;              S = [X,Y]
    ).
msort(N, Xs0, Xs, S, C) :-
    A is N // 2, Z is N - A,
    msort(A, Xs0, Xs1, S1, C),
    msort(Z, Xs1, Xs,  S2, C),
    merge_0(S1, S2, S, C).


merge(C, S1, S2, L) :-
    merge_0(S1, S2, T, C),
    L = T.

merge_0([],     L,  L, _).
merge_0([X|Xs], Ys, L, C) :-
    merge_1(Ys, Xs, L, C, X).

%   merge_1(Ys, Xs, L, C, X) -- list 1 has been taken apart

merge_1([],     Xs, [X|Xs], _, X).
merge_1([Y|Ys], Xs,   L,    C, X) :-
    call(C, R, X, Y),
    merge_12(R, Xs, L, C, X, Ys, Y).

merge_12(>, Xs, [Y|L], C, X, Ys, Y) :-
    merge_1(Ys, Xs, L, C, X).
merge_12(<, Xs, [X|L], C, X, Ys, Y) :-
    merge_2(Xs, Ys, L, C, Y).
merge_12(=, Xs, [X|L], C, X, Ys, Y) :-
    merge_2(Xs, Ys, L, C, Y).

%   merge_2(Xs, Ys, L, C, Y) -- list 2 has been taken apart

merge_2([],     Ys, [Y|Ys], _, Y).
merge_2([X|Xs], Ys,   L,    C, Y) :-
    call(C, R, X, Y),
    merge_12(R, Xs, L, C, X, Ys, Y).

sort(C, List, Sorted) :-
    length(List, N),
    (   N >= 2 -> sort(N, List, _, S, C), Sorted = S
    ;   Sorted = List
    ).

sort(1, [X|Xs],   Xs, [X], _) :- !.
sort(2, [X,Y|Xs], Xs, S,   C) :- !,
    call(C, R, X, Y),
    sort2(R, X, Y, S).
sort(N, Xs0, Xs, S, C) :-
    A is N // 2, Z is N - A,
    sort(A, Xs0, Xs1, S1, C),
    sort(Z, Xs1, Xs,  S2, C),
    union_0(S1, S2, S, C).


sort2(<, X, Y, [X,Y]).
sort2(>, X, Y, [Y,X]).
sort2(=, X, _, [X]).

union(C, S1, S2, U) :-
    union_0(S1, S2, S, C),
    U = S.

union_0([],      U,  U, _).
union_0([H1|T1], S2, U, C) :-
    union_1(S2, H1, T1, U, C).

union_1([], H1, T1, [H1|T1], _).
union_1([H2|T2], H1, T1, U, C) :-
    call(C, R, H1, H2),
    union_2(R, H1, T1, H2, T2, U, C).

union_2(<, H1, T1, H2, T2, [H1|U], C) :-
    union_1(T1, H2, T2, U, C).
union_2(>, H1, T1, H2, T2, [H2|U], C) :-
    union_1(T2, H1, T1, U, C).
union_2(=, H1, T1, _,  T2, [H1|U], C) :-
    union_0(T1, T2, U, C).


%   Utility predicate to sort in reverse without reversing the
%   list.  Since this treats as equivalent only terms that are
%   identical,
% msort(reverse_compare, L, S) <=> msort(compare, L, T), reverse(T, S)
% sort( reverse_compare, L, S) <=> sort( compare, L, T), reverse(T, S).
%   For comparisons with other notions of equality, this is NOT true.
%   For example, the corresponding equivalences involving
%   key_compare/3 and reverse_key_compare/3 do NOT hold.

reverse_compare(R, X, Y) :-
    compare(R, Y, X).

key_compare(R, X-_, Y-_) :-
    compare(R, X, Y).

key_compare(N, R, A, B) :-
    arg(N, A, X),
    arg(N, B, Y),
    compare(R, X, Y).

reverse_key_compare(R, X-_, Y-_) :-
    compare(R, Y, X).

reverse_key_compare(N, R, A, B) :-
    arg(N, A, X),
    arg(N, B, Y),
    compare(R, Y, X).

---

>
> Thanks!

[Lev777]

On Thu, Jun 11, 2009 at 2:00 AM, Richard O'Keefe <ok@...> wrote:

On 10 Jun 2009, at 7:25 pm, Levan Cheishvili wrote:

I have the following structure:

object('obj1', [id='12', color='blue']).
object('obj4', [id='13', color='red', weight=120]).
object('obj21', [id='15 a', color='yellow', weight=1000, price=23]).
object('obj21', [id='16 a', color='blue', weight=200, price=230]).

I assume that that's a table of facts, so

:- type eq ---> =(atom,any).
:- pred object(atom, list(eq)).

The first thing that strikes me is that the Prolog convention for
a list of key-value pairs has been a list of Key - Value terms
since about 1979, that's 30 years.  There is a standard predicate
called keysort/2 for sorting such lists.  So why are you using
(=)/2 for your pairs instead of (-)/2?

While selecting a proper structure for data representation I read a newsletter: http://www.ainewsletter.com/newsletters/aix_0309.htm#ontology

and did not know that in prolog (=)/2 is not supported as (-)/2. (I am learning prolog while working on my very first project in this language).

 

[It's not that (-)/2 is a specially brilliant choice, although since
it is very often used with collections of pairs that are _not_ finite
maps, it's definitely better than (=)/2.  The point is just that it
is the _better-supported_ choice.]

How come you have two facts for obj21?

My data is like:

object(type1, id, title, [

  prop1-val1,

  prop2-val2,...

  propN-valN

]).

 

Data come from external source in form of XML, and I have no idea how many properties will be, but I know that there will be type, id and title which will form a unique key.

XML I am parsing using PHP to Prolog (thus avoiding dealing with SQL database structures and writing wrapping classes and other 'gifts' of OOP).

 

I have a predicate which finds all objects with particular key, e.g. objects with color='blue'.

The second thing that strikes me is that what you really have
seems to be a ternary relation,

oav(obj1, id,     12).          % Object Attribute Value
oav(obj1, colour, blue).
oav(obj4, id,     13).
oav(obj4, colour, red).
oav(obj4, weight, 120).

Or possibly a collection of binary relations

id(obj1, 12).
id(obj4, 13).

colour(obj1, blue).
colour(obj4, red).

weight(obj4, 120).

During my work on this project I have tried several structures. And first one was binary relation. But I found it difficult for me to write predicates for querying it, as I have complex properties, like e.g. prop(obj, val1, val2, val3...) and each value may be connectedc to another property etc.

That's why I have selected above structure where each  object has three basic common properties and list of other properties. If some of properties are compound my external script generates new objects for them.   

However I think that RDF would be better in this case....I will do it in RDF when I learn it :-)

 

All things considered, I think the binary relations are the way I'd
do it.  We can recover the other views if we really have to:

oav(Obj, id,     X) :- id(Obj, X).
oav(Obj, colour, X) :- colour(Obj, X).
oav(Obj, weight, X) :- weight(Obj, X).
oav(Obj, price,  X) :- price(Obj, X).

object(Obj, Attrs0) :-
   ( id(Obj,     I) -> Attrs0 = [id    =I|Attrs1] ; Attrs1 = Attrs0 ),
   ( colour(Obj, C) -> Attrs1 = [colour=C|Attrs2] ; Attrs2 = Attrs1 ),
   ( weight(Obj, W) -> Attrs2 = [weight=W|Attrs3] ; Attrs3 = Attrs2 ),
   ( price(Obj,  P) -> Attrs3 = [price =P|Attrs4] ; Attrs4 = Attrs3 ),
   Attrs4 = [].

If you want to find all the objects that are blue,

       setof(Obj, colour(Obj, blue), Blue_Objs)
or even
       findall(Obj, colour(Obj, blue), Blue_Objs)

is a lot easier than

       setof(Obj, ( object(Obj, Attrs), member(colour=blue, Attrs) ),
             Blue_Objs)

My question is:
How to write a sorting predicate which will sort objects within a resulting list by one of one or many  keys(id or/and price, etc...)

There are several ways to do it.
One way is to exploit the fact that keysort is stable.
So sort by the least significant key first,
then the second least significant key,
...
and finally sort by the most significant key.

To sort a list by a particular key, simply take a list whose
elements are X and make a list whose elements are Key-X, and
sort that.  If you want to sort in decreasing order, just
reverse the result.

If you want ascending order for everything (except possibly
numbers, which you can negate), you can simply build
one super-key containing all the others.

For example, suppose you want to find all the blue objects
and sort them by decreasing price and (within the same price
level) increasing id.

   setof( key(Minus_Price,Id) - Object
        , ( colour(Object, blue),
            price(Object, Price), Minus_Price is -Price,
            id(Object, Id)
          )
        , Pairs),
   pairs_values(Pairs, Objects)

where pairs_values/2 is described in http://www.cs.otago.ac.nz/staffpriv/ok/pllib.htm

That draft library specification also calls for
sort/3 and msort/3.  There is a file which was written
for that but never included, because there seemed to be
very little interest in a standard library for Prolog.
I've attached it.  It's called msort.pl, and I've deleted
msort/2 from it because SWI Prolog already has msort/2.

With this, you would write a 3-way comparison predicate.
Using the binary relations version of your data,
you'd write

price_and_id_compare(R, Obj1, Obj2) :-
   price(Obj1, Price1),
   price(Obj2, Price2),
   compare(R1, Price2, Price1),  % note argument order!
   (   R1 == (=) ->
       id(Obj1, Id1),
       id(Obj2, Id2),
       compare(R, Id1, Id2)
   ;/* prices differ */
       R = R1
   ).

Then given a list of objects you could do

   msort(price_and_id_compare, Objects, Sorted_Objects)

if you want to keep duplicates, or sort/3 to discard them.

 

Many thanks for your guidance ! I really appreciate your help. 

I have rewritten structure of terms, query predicates and now they work much faster and speed is suitable for my php application..   

 

Best Regards

Levan Cheishvili

Thanks!

[Richard O'Keefe]

On 12 Jun 2009, at 9:23 am, Levan Cheishvili wrote:
>
> I have the following structure:
>
> object('obj1', [id='12', color='blue']).
> object('obj4', [id='13', color='red', weight=120]).
> object('obj21', [id='15 a', color='yellow', weight=1000, price=23]).
> object('obj21', [id='16 a', color='blue', weight=200, price=230]).
>

> While selecting a proper structure for data representation I read a  
> newsletter: http://www.ainewsletter.com/newsletters/aix_0309.htm#ontology
> and did not know that in prolog (=)/2 is not supported as (-)/2. (I  
> am learning prolog while working on my very first project in this  
> language).

I think it might be better to read a good book.
And while Prolog is _better_ than SQL, a lot of the stuff in
data base _theory_ (which SQL little respects) is useful to know.

> How come you have two facts for obj21?
>
> My data is like:
>
> object(type1, id, title, [
>   prop1-val1,
>   prop2-val2,...
>   propN-valN
> ]).
>
> Data come from external source in form of XML, and I have no idea  
> how many properties will be, but I know that there will be type, id  
> and title which will form a unique key.

The point of an "id" is to be a unique identifier.
In fact, surely 'obj1', 'obj4', and so on *are* "ids".

With all the earnestness I possess, I tell you that life
will be *far* simpler if the things you use as unique keys
are SINGLE atoms or SINGLE numbers.  (What William Kent in
his wonderful book "Data and Reality" calls "surrogates".)

In general you will need relations mapping between surrogates
(internal keys) and external names.  So if external names are
(type,id,title) keys, use

surrogate(Atom, Type, Id, Title).
  % fd  Atom -> Type, Id, Title
  % fd Type, Id, Title -> Atom


I'm still very troubled by something being *called* an Id that is none.

If your data are provided in XML, then it simply isn't try that
your data "is (sic.) like:
        object(type1, id1, title, [ ... ])."
Your data are like *whatever you want them to be like*.

The big difference between
        prop1(key1, val1).
and
        object(key1, [...,prop1-val1,...])
is that

    If you just want to know "what is the value of prop1 for key1"
    then the first version (one relation per property) JUST RETURNS
    THE INFORMATION YOU WANT, while the second version COPIES
    EACH AND EVERY PROPERTY for that object EVERY TIME.

That is to say, using the list-of-properties version is
seriously inefficient, and that's throwing roses at it.

>
>
> During my work on this project I have tried several structures. And  
> first one was binary relation. But I found it difficult for me to  
> write predicates for querying it,

Give specific examples.  The data structure you displayed in your
message only really handles binary relations, so there could be no
simple queries easily expressible that way that are not easier
expressed using binary relations.

> as I have complex properties, like e.g. prop(obj, val1, val2,  
> val3...) and each value may be connectedc to another property etc.

This is not clear.  Give an example.  There is no reason why the
*value* of a property cannot be a list or arbitrary term.

Why don't you tell us what your _abstract_ problem is, your
"logical data model", as it were, and _then_ we can discuss how
it might be mapped well onto Prolog.
>

> However I think that RDF would be better in this case....I will do  
> it in RDF when I learn it :-)

The _basic_ data model in RDF is binary relations, where admittedly
the relation names can be very long.  RDF can be written in Notation3,
after all.

Please do tell us more about what you are trying to model/do.
Let's see how well it can be done.


_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Lev777]

Let me start from the beginning...

There is XML data which is separate for each type of objects.

It looks like:

...

<Oil_Painting>305</Oil_Painting>

<Title>Original Title</Title>

<Title_English>Some Title</Title English>

<Title_German>Some other title in German</Title German>

<Place>Bonn,school of arts, 1997</Place>

<Exhib>Exhibition of XYZ, Gallery of Bonn, Germany, 1980/1981</Exhib>

<Exhib>Exhibition of XYZ1, Gallery of Amsterdam, Holland, April 1981- 1982</Exhib>

<Monographs>M.L. Sam, The book name 1940-2001, Catalogue of Paintings, Cologne, 2002, Vol. II, p. 1174</Monographs>

<Monographs>M.L. Markus, The book name, Catalogue of Paintings, Cologne, 2003, p. 1174 (c)</Monographs>

.....

<Tapestry>305</Tapestry>

<Title English>Original Title</Title English>

<Author>A.S. Kushkin, 1963</Author>

<Reproduced By></Reproduced By>

<Based On></Based On>

<Year>1980 April 2</Year>

<Exhibition></Exhibition>

<Catalog></Catalog>

<.....

....

As you may see type of object I am taking from the first (or agreed with author of XML) field, which is OilPainting, Tapestry, etc. Unique ID within the Type is the value of the Type field.

Title is main descriptive field of the object. These 2 properties - ID and Type are unique and shall be used to genererate Primary Key (or as you say a surrogate key).

The XML is parsed by PHP script into Prolog terms (Knowledge Base) Then this knowledge base run as a local http server.

Main web site sends http requests to Prolog server and gets results which are shown in a browser.

XML data format is not strictly defined. Some fields have compound data like:

<Monographs>M.L. Sam, The great painter T.Smith 1940-2001, Catalogue of Paintings, Cologne, 2002, Vol. II, p. 1174</Monographs>

When parser find this type of value it may leave it as it is or may try to parse into several objects: Author of Monograph, 1st name of book, 2nd name(or line) of book, Publisher City, Year of publish, etc....

The problem is that, I can not demand from XML issuer to generate 'proper' XML with all fields and values separated.

Data come from an Old database system which was meant for entering data printing it on paper in a human readable way.    

However extracting and structuring information (generating new objects and linking to parent objects) from this kind of compound fields is priceless.

Further, objects will be categorized manually by Art expert and will be linked to different categories. Categories are hierarchical.

Objects itself will be interconnected as well (by an Art expert). Relations will be parent->child or node<=>node.

Thus we will get undirected graph...

When we get XML with updates/or new objects, all created so far linkage should be (of course!) persisted. And here, a surrogate key will help (Type+Id).

 

That is all, basically.

On Fri, Jun 12, 2009 at 1:05 AM, Richard O'Keefe <ok@...> wrote:

On 12 Jun 2009, at 9:23 am, Levan Cheishvili wrote:

I have the following structure:

object('obj1', [id='12', color='blue']).
object('obj4', [id='13', color='red', weight=120]).
object('obj21', [id='15 a', color='yellow', weight=1000, price=23]).
object('obj21', [id='16 a', color='blue', weight=200, price=230]).

While selecting a proper structure for data representation I read a newsletter: http://www.ainewsletter.com/newsletters/aix_0309.htm#ontology
and did not know that in prolog (=)/2 is not supported as (-)/2. (I am learning prolog while working on my very first project in this language).

I think it might be better to read a good book.
And while Prolog is _better_ than SQL, a lot of the stuff in
data base _theory_ (which SQL little respects) is useful to know.

How come you have two facts for obj21?

My data is like:

object(type1, id, title, [
 prop1-val1,
 prop2-val2,...
 propN-valN
]).

Data come from external source in form of XML, and I have no idea how many properties will be, but I know that there will be type, id and title which will form a unique key.

The point of an "id" is to be a unique identifier.
In fact, surely 'obj1', 'obj4', and so on *are* "ids".

With all the earnestness I possess, I tell you that life
will be *far* simpler if the things you use as unique keys
are SINGLE atoms or SINGLE numbers.  (What William Kent in
his wonderful book "Data and Reality" calls "surrogates".)

In general you will need relations mapping between surrogates
(internal keys) and external names.  So if external names are
(type,id,title) keys, use

surrogate(Atom, Type, Id, Title).
 % fd  Atom -> Type, Id, Title
 % fd Type, Id, Title -> Atom


I'm still very troubled by something being *called* an Id that is none.

If your data are provided in XML, then it simply isn't try that
your data "is (sic.) like:
       object(type1, id1, title, [ ... ])."
Your data are like *whatever you want them to be like*.

The big difference between
       prop1(key1, val1).
and
       object(key1, [...,prop1-val1,...])
is that

  If you just want to know "what is the value of prop1 for key1"
  then the first version (one relation per property) JUST RETURNS
  THE INFORMATION YOU WANT, while the second version COPIES
  EACH AND EVERY PROPERTY for that object EVERY TIME.

That is to say, using the list-of-properties version is
seriously inefficient, and that's throwing roses at it.

During my work on this project I have tried several structures. And first one was binary relation. But I found it difficult for me to write predicates for querying it,

Give specific examples.  The data structure you displayed in your
message only really handles binary relations, so there could be no
simple queries easily expressible that way that are not easier
expressed using binary relations.

as I have complex properties, like e.g. prop(obj, val1, val2, val3...) and each value may be connectedc to another property etc.

This is not clear.  Give an example.  There is no reason why the
*value* of a property cannot be a list or arbitrary term.

Why don't you tell us what your _abstract_ problem is, your
"logical data model", as it were, and _then_ we can discuss how
it might be mapped well onto Prolog.

However I think that RDF would be better in this case....I will do it in RDF when I learn it :-)

The _basic_ data model in RDF is binary relations, where admittedly
the relation names can be very long.  RDF can be written in Notation3,
after all.

Please do tell us more about what you are trying to model/do.
Let's see how well it can be done.

[Ulrich Neumerkel]

Levan Cheishvili writes:
> Let me start from the beginning...There is XML data ...
> ... <Oil_Painting> ...
 
One application of SWI is ClioPatria.  There might be some
parallels.  See: http://www.swi-prolog.org/web/
 
You might also look into Jan's Thesis (follow the link publications).
Even more so as Jan is defending it today :-).
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Lev777]

Yeap, it is like e-culture, but much smaller :-).

Good luck to Jan !!!

On Fri, Jun 12, 2009 at 2:08 PM, Ulrich Neumerkel <ulrich@...> wrote:

Levan Cheishvili writes:
> Let me start from the beginning...There is XML data ...
> ... <Oil_Painting> ...

One application of SWI is ClioPatria.  There might be some
parallels.  See: http://www.swi-prolog.org/web/

You might also look into Jan's Thesis (follow the link publications).
Even more so as Jan is defending it today :-).