[xquery-talk] Function for determining one XPath as subset of another
Pavel Velikhov
pavel.velikhov at gmail.com
Thu Jan 28 01:55:40 PST 2016
> Finally, can it be proved that /w[@a=b] is a subset of /w, taking into account that the filter can only contain standard operators (eq, gt, lt, etc as defined in the op namespace)?
Okay, now we are close! However now formal do you want the proof to be? I can give this informal proof:
The first path expression selects some subset of the children of the node that it applies, where the label is 'w'. The second one selects all descendants with label 'w', hence it's result contains all nodes of the first path expression.
But if you want to go formal, you need to use the semantics of XQuery path expressions, as well as the formal specification of the data model. There used to be a formal document on XQuery data model.
> 2016-01-27 17:46 GMT+01:00 Christian Grün <christian.gruen at gmail.com>:
>> > Well, so, to continue, let's assume that there are no user-defined
>> > functions, and in fact the only thing we want to proof is select+filter,
>> > where a filter is limited to the default operators. From that is it follows
>> > that
>> >
>> > -path1:
>> > select-child-nodes-by-name(select-child-nodes-by-name($context,'x'),'w')
>> > -path2: select-descendant-nodes-by-name($context,'w')
>>
>> Just to complete this: The predicate must not be numeric (//w[1] is
>> not equivalent to /descendant::w[1]).
>>
>>
>>
>> > Op woensdag 27 januari 2016 heeft daniela florescu <dflorescu at me.com> het
>> > volgende geschreven:
>> >>
>> >> >
>> >> > It seems to be a long-standing tradition that computer scientists, when
>> >> > asked to prove a difficult conjecture C, respond by giving a proof for a
>> >> > simplified conjecture C'. While this might lead to progress in the long run,
>> >> > and enables them to get papers published in the academic literature, it is
>> >> > totally useless to practical engineeers who want to know whether they can
>> >> > safely rely on C.
>> >>
>> >> Michael,
>> >>
>> >>
>> >> what you say is nice and true.
>> >>
>> >> However given that:
>> >> 1. path expressions point (syntactically hence esemantically) into
>> >> XQuery’s expressions
>> >> 2. XQuery expression language is Turing complete
>> >> 3. Subsumption for a Turing complete language is undecidable.
>> >>
>> >> Well, I can hardly see a way to decide this problem other then by
>> >> introducing SOME restrictions
>> >> of some sort… but of course some restrictions that would not nullify the
>> >> original problem all together
>> >> and make the solution useless.
>> >>
>> >> Best,
>> >> Dana
>> >
>> >
>> >
>> > --
>> >
>> > W.S. Hager
>> > Lagua Web Solutions
>> > http://lagua.nl
>> >
>> >
>> >
>> > _______________________________________________
>> > talk at x-query.com
>> > http://x-query.com/mailman/listinfo/talk
>
>
>
> --
> W.S. Hager
> Lagua Web Solutions
> http://lagua.nl
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://x-query.com/pipermail/talk/attachments/20160128/d99cf8aa/attachment.html>
More information about the talk
mailing list