- From: Seaborne, Andy <andy.seaborne@hp.com>
- Date: Mon, 31 Jul 2006 13:28:32 +0100
- To: Fred Zemke <fred.zemke@oracle.com>
- CC: public-rdf-dawg@w3.org
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