OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.

# xdi message

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]

Subject: RE: [xdi] \$or and \$and may not be necessary

• From: "Drummond Reed" <drummond.reed@cordance.net>
• Date: Wed, 16 Apr 2008 22:08:22 -0700

I like the variable approach very much, but in the example in Markus' messageI don't understand how the reference to "\$any\$1" resolves to "\$any\$1+age".

Would it be better to keep a clear mapping between the variable XRIs and the XDI statements they represent? For example:

=giovanni
+friend
\$any\$1
\$any\$2
\$any\$1
\$context
/
+age
\$greater
"40"
\$any\$2
\$context
/
+age
\$lesser
"27"

=Drummond

Sent: Wednesday, April 16, 2008 9:21 AM
To: Giovanni Bartolomeo
Cc: xdi@lists.oasis-open.org
Subject: Re: [xdi] \$or and \$and may not be necessary

Yes.. I think everyone who has some experience in logic will find this pattern familiar.

In some cases this disjunctive normal form will appear to be more complicated than your original form with brackets, for example:

"Give me all of Giovanni's friends who are younger than 27 OR older than 40". In order to implement the OR, you have to introduce two variables, i.e. you have to do it this way:

=giovanni
+friend
\$any\$1
\$any\$2
\$any\$1+age
\$greater
"40"
\$any\$2+age
\$lesser
"27"

Whereas in your original bracket form you would probably be able to somehow do this with just one variable.

BTW you don't need \$not either, because you can convert your \$not queries like this:
"Give me all of Giovanni's friends who are NOT (younger than 27 OR older than 40)".

Well that's just the same as
"Give me all of Giovanni's friends who are >= 27 AND <= 40.

It really seems to be just a simple matter of boolean algebra to convert just about any arbitrarily complex query to what you call "normal form".

Markus

P.S. You can try the query above at http://graceland.parityinc.net/xdi-querier/XDIQuerier

On Wed, Apr 16, 2008 at 1:47 PM, Giovanni Bartolomeo <giovanni.bartolomeo@uniroma2.it> wrote:

The solution proposed by Markus works because he has been able to express this complex query into a "normal form" compliant with the one used for "traditional" \$get. He correctly identified that this format allows to disjoin the graph into multiple graphs (he called them "clusters"). Adding different \$any variables, we can implicitly create AND and OR statements, in a simple way: AND statements are created when the same \$any variable appears into two or more clusters, OR statements are the default.
So this solution will work in general for any AND/OR expression. The only concern is that we've to arrange the query into this "normal form". Interestingly, the existence of a "normal form" for XDI has reminded me some expressions in logic which are known as disjunctive normal forms: http://en.wikipedia.org/wiki/Disjunctive_normal_form... not sure, but maybe it worths to be further investigated in the future.

Bests,
Giovanni

At 15.40 01/04/2008, Giovanni Bartolomeo wrote:
Hello Markus,

at a first glance it seems that this solution works fine, however I'm
not sure whether this could replace \$and, \$or etc. in any possible use
case (we need to elaborate some more examples).
But I agree that for now this is a good solution and we can reccomend
to use it :-)

Giovanni

At 20.46 30/03/2008, you wrote:
Maybe \$or and \$and are not necessary at all, because I think that
1) There's an implicit AND relation between query statements that
share variables.
2) There's an implicit OR relation between query statements that do
not share variables.

For example, take this query:

=giovanni
+friend
\$any\$1
+brother
\$any\$2
\$any\$1+age
\$lesser
"40"

It means give me all statements that are matched by the following:
( [=giovanni[+friend[\$any\$1]]] AND [\$any\$1+age[\$lesser["40"]]] ) OR (
[=giovanni[+brother[\$any\$2]]] )

In other words, you can divide the query graph into multiple disjunct
graphs (let's call them clusters). Every variable you use appears in
only one cluster. The query above consists of two clusters:

Cluster 1:

=giovanni
+friend
\$any\$1
\$any\$1+age
\$lesser
"40"

Cluster 2:

=giovanni
+brother
\$any\$2

Now the rule is that when executing the query you select everything
from your input graph that matches ALL statements in AT LEAST ONE of
the clusters. This results in the implicit AND and OR relations.

I'm not 100% sure, but I think that with Giovanni's \$any and \$all
words you can automatically model any query you want, without the need
for \$or and \$and.

Markus

P.S. I'm sure that in graph theory there's a better word for those
"clusters", but I don't know the correct expression in either English
or German. The point is that variables that are not "connected" end up
in different clusters.

---------------------------------------------------------------------
To unsubscribe from this mail list, you must leave the OASIS TC that
generates this mail.  You may a link to this group and all your TCs in OASIS
at:
https://www.oasis-open.org/apps/org/workgroup/portal/my_workgroups.php

---------------------------------------------------------------------
To unsubscribe from this mail list, you must leave the OASIS TC that
generates this mail.  You may a link to this group and all your TCs in OASIS
at:
https://www.oasis-open.org/apps/org/workgroup/portal/my_workgroups.php

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]