Re: Reposting my paper on constructive formal semantics

Fred Zemke wrote:
> Oops, sorry, I inadvertently posted the wrong paper yesterday.
> Here is the paper I meant to post.  Feedack is encouraged.
> Thank you to Andy for spotting my mistake.
> 
> Fred

Fred,

Interesting paper - I find the constructive semantics approach useful,
especially in its handling of undefined and redundant bindings.

I wondered how you'd relate the two approaches to the top-down and bottom-up
evaluation approaches in "Semantics and Complexity of SPARQL" [1].

The destructive semantics you present would be equivalent to the constructive
semantics if there were notion of minimising a result set with respect to a
query pattern to produce necessary solutions.  That would be relative to the
query, not the dataset, so it would retain useful cardinality properties.
(Enrico outlines logical minimization algorithm for blank nodes in a result
set but that was dependent on the whole dataset).

==== Destructive formulation

"""M is the set of all mappings whose domain is a subset of var(Q)""" -
wouldn't the range of mappings would be limited to the scoping set of the
query.  Actually, it suggests that the scoping set might be different
depending on whether the variable was in a subject or object position; and the
intersection of the two scoping sets if appearing in both subject and object
positions in triple patterns.

==== Constructive formulation

== var(P)

In the constructive semantics, you state:

Section 4:
"""
A key difference from the destructive-centric semantics is that a solution S
of a pattern P is necessarily undefined on variables that do not appear in P.
That is, dom(S) is a subset of Var(P).
"""

Does this statement apply to the whole query pattern alone or to subpatterns?
Trying to follow your intent here, I wasn't sure.  Certainly the domain of
any solution should be bounded above by all the variables mentioned in the
query.  Following through to subpatterns I seemed to get contradictions:

e.g. S is a solution of GGP = { GP1, GP2, ... }

{ { ?x :p :v } { ?y :q :w } }

so ?y is not in var(GP1) and any solution S needs to contain ?x and ?y.
Suggestion: define the domain of S construcively, including variables as needs
(e.g. for group its the union of the var(GPi)).  Altenratively, the defintions
for group/union/... need to restrict the solution to var of the sub-pattern.

== cardinality I

OPTIONAL - the cardinality is the cardinality of (A & B) or A depending on
which way the optional was matched.  Isn't card(A&B), min(card(A), card(B)) - 
that is, card(group(A,B))?

== cardinality II

The cardinality of a solution to FBGP is fixed as one.  I find that odd as 
existentials don't have a notion of cardinality but it also seems restrictive 
and an implementation burden.  It's restrictive because for many cases (not 
all) bnodes can be implemented like any other variable because the 
data/entailment-regime permits more information. All variables with bindings 
have an existential nature in a query for a given solution, yet sometimes 
counting information is available and meaningful (e.g. editor use cases, 
entailment regimes with closures).  It's not the _:a uses that seem to be the 
issue - I'd hardly expect them to be common.  It's the convenience of the 
syntax for

	?x :p [ :q ?v ]

which is what lead us here in the first place.  (If we don't want COUNT(*) to 
ever mean number of rows, then there may be no problem.)

It's an implementation burden because the solutions would have to reduced to 
the right cardinality at the point of BGP matching - it couldn't be left until 
later unless the whole query is DISTINCT.  Possibly minor.


	Andy

[1] Perez, Arenas and Gutierrez
http://www.dcc.uchile.cl/~cgutierr/ftp/sparql-ext.pdf
via
http://lists.w3.org/Archives/Public/public-rdf-dawg-comments/2006Jun/0008

Received on Monday, 31 July 2006 12:28:58 UTC