TF-Query and Kleene Star

[dirkroorda]

TF-Query is inspired by MQL queries, as implemented in Emdros.

One thing that is currently lacking in TF-Query is the Kleene Star.

In MQL you can say for example:

[clause domain=N]
[clause domain=Q] * {1-50}
[clause domain=N]

meaning: match a clause with domain=N, then at least one and up to 50 clauses with domain=Q, and then a clause with domain=N again.

This is not possible in TF-Query.
Can we make this possible?

[dirkroorda]

This construct violates a few assumptions that the implementation of TF-Query makes.

Suppose we have a query like this

clause domain=N
<: clause domain=Q
<: clause domain=Q
<: clause domain=N

then the results are 4-tuples, in which each member of a result tuple corresponds with a clause line in the query.
When we allow the Kleene star, we get result tuples of variable length.

Moreover, when TF-Query runs a query, it first builds a graph of qnodes, where each qnode corresponds with an element in the query. It then analyses the graph, and constrains the result space, and uses the graph to stitch results together.

With the Kleene star, we can no longer build such a q-graph, or we have to modify the meaning of the q-graph.

[dirkroorda]

What we can do is:

allow a result tuple to contain a tuple of sub results, but only for q-nodes with a Kleene-star. Then the outer number of results in each tuple is still constant.

We do have to modify the functions plainTuple() and prettyTuple() functions that display tuples, but that is doable.

[dirkroorda]

Then the interpretation:

When we stitch results together, based on q-nodes, what we do is:

we start with a q-node and find a match for that in the text.

Say we find text node t1 that matches q-node q1.

Then we go from q1 to a certain q2 along a q-edge. A q-edge corresponds to a relational constraint, such as "word contained in clause". So, say that qe1 is the q-edge between q1 and q2, and say that qe1 corresponds to the relation r1 between text nodes.

So, we look for a text-node t2 that matches q2, and for which it holds that t1 stands in relationship r1 to t2, or for short: r1(t1, t2).

This is how it works now.

[dirkroorda]

Now suppose we have a qnode qn that corresponds to an item with a Kleene star, say * {2-10}

If this is the only node, it is easy to find matches:

We start with any t1 that fits qn, and then examine whether we can find a t2 that fits the bill to, and for which t1 <: t2 (adjacent),
and so on. Then we retain all such sequences of length 1-50 (and we can optimize in a number of ways).

If we have qn-qe-qm in our query graph, and qe corresponds to relation r, and we have a sequence T1 = (t1, ..., tk) matching qn, then we have to find a tm matching qm, such that tk-r-tm.

I.e.: for outgoing edges the relation most hold between the last element of a matching sequence of qn, and a match for qm.

Likewise, for incoming edges qm-qe-qn, the relation most hold between the match for qm and the first element of the match for qn.

If both qn and qm correspond to Kleene-starred qnodes, it is also clear.
In case of qn-qe-qm the relation must hold between the last element of a match of qn and the first element of a match of qm.

[dirkroorda]

So far so good. It seems if we generalize our notion of q-nodes, so that they represent sequences of text nodes, we can deal with the Kleene-star on single objects in our queries.

But even then, MQL is a step ahead. In MQL you can say

[clause
 [
   [word sp=verb]
   [word sp=noun]
 ] * {2-4}
]

i.e. you can not only star single atoms but whole groups.

[dirkroorda]

Now, how could we implement the corresponding TF-Query?

clause
  (
    word sp=verb
    word sp=noun
  ) * {2-4}

So far, we do not even have the syntax ( ) for groups.

[dirkroorda]

Again, two problems: what do the result tuples look like, and how do we model groups in terms of q-nodes and q-edges?

Results: the result of a group is a tuple of the results of the individual group members.

So a result of

clause
  word
  word

is a tuple (c, w1, w2), where c is a clause node, w1 and w2 are word nodes.

But a result of

clause
  (
    word
    word
  )

is a tuple (c, (w1, w2)).

[dirkroorda]

And the result of

clause
  (
    word sp=verb
    word sp=noun
  ) * {2-4}

looks like

(c, ((w11, w21), (w12, w22), (w13, w23)))

[dirkroorda]

As to the graph:

we need the concept of a cluster of q-nodes, which represents a group in the query.

Such a cluster is itself a q-node, and its matches are sequences of matches of the q-nodes that make up the cluster.

So, now q-nodes can be atomic q-nodes or trees of q-nodes. And matches of q-nodes are tuples that are in fact trees of text-nodes.

Probably, we are getting very close to the notion of sheaf of @emg !

I think this is implementable in TF-Query, but it will take a fair amount of very careful work.

[dirkroorda]

This should probably be forbidden

clause
  (
    =: word sp=verb
    <: word sp=noun
  ) * {2}

There is a meaning though: the words inside the group should match a verb and an immediately following noun, and the verb should be the first word in the clause.

We need two consecutive matches of this word group, and that it not possible, because every match of the word group has the first word of the clause as its first word.

This points to something inelegant: the relation <: is implied in the Kleene-star.

When we say

thing * {2-50}

we look for 2 - 50 things and tacitly assume that these things should be adjacent to each other.

But why adjacent?

That is an MQL thing: blocks come after each other.

[dirkroorda]

If we can implement the Kleene star in this way, we are ahead of MQL, because MQL does not allow Kleene-stars on unordered groups.

In fact, unordered groups are severely restricted in MQL, and the meaning is still not completely documented.

Suppose we have a clause with two phrases, one lying inside a gap of the other, like so

phrase1	phrase2	phrase1
w1 w2	w3 w4	w5 w6

[dirkroorda]

Then neither of the following MQL queries will find it, I think

[clause
  [phrase]
  [phrase]

and

[clause
  [unorderedgroup
    [phrase]
    [phrase]
  ]
]

[dirkroorda]

This is because in MQL there is always the implicit adjacency relationship between blocks in a query.

TF-Query, on the other hand, does not assume any spatial relationship:

clause
phrase
phrase

means a clause and two phrases, without any relationship between them (it is therefore not a valid TF-query, because
a query should be a connected graph of q-nodes and q-edges).

But

c:clause
p1:phrase
p2:phrase

p1 ]] c
p2 ]] c

is allowed and states explicitly that p1 is embedded in c and p2 is embedded in c.
It does not say anything about how p1 and p2 are related.
Not only it does not say that p2 follows p1, it does not even say that they have to be adjacent, or disjoint, or that one is completely before the other.

So this query also finds the case where p2 is inside a gap of p1.

We can explicitly ask for the adjacency, and hence order:

c:clause
p1:phrase
p2:phrase

p1 ]] c
p2 ]] c
p1 <: p2

We can abbreviate this in two steps (the abbreviation is a purely syntactic variant)

clause
  p1:phrase
  p2:phrase

p1 <: p2

Indentation means: embedding.

Next step

clause
  phrase
  <: phrase

We can put an explicit relation requirement between two blocks.

Instead of adjacency we can also weaken it to mere order:

clause
  phrase
  < phrase

which corresponds to MQL

[clause
  [phrase]
  ..
  [phrase]
]

[dirkroorda]

What I mean to say is: in TF-Query we can talk better about spatial relationships.
They are part of the language, and can be varied at will, consciously.

So when we implement Kleene-star, we should not silently assume that the relation between the elements of the matching sequence is one specific relation, namely <:.

The TF-Query framework can handle arbitrary relationships here.

Are there meaningful queries that need a Kleene-star but with a different relationship?

[dirkroorda]

clause
    =: phrase
      w1:word
    w2:word * {1-}

w1 .lex. w2
w1 < w2

[dirkroorda]

This looks for lexemes in the first phrase of a clause and collects all words with the same lexeme further on in the clause, if any.

[dirkroorda]

And here the w:word matches are not supposed to be adjacent.

So how can we express when we do want a specific relation between the elements of a series that matches a Kleen-star?

[dirkroorda]

Something like this?

clause
  (
    phrase
    phrase
  ) * {2-5} <:

versus

clause
  (
    phrase
    phrase
  ) * {2-5} :=

In the first one, the elements matching the kleene-star are adjacent, in the second case they all end at the same position.

[dirkroorda]

The relation is not optional, there should be one.
Otherwise we get disconnected elements and an explosion of results.

[dirkroorda]

Probably the relation should be a very constraining relation, such as ==, :=, =:, [[, ]], &&, because if it is loose, like <, >, #, <<, >>, || the number of results will explode.