A logical conundrum on ordered sets.

[Jamie Oglethorpe]

I am looking for a good way to characterize a particular member of a
totally ordered discrete set in terms of a non-empty subset of this
set.

It is the greatest member less than all members of the subset, if it
exists, otherwise it is the least member of the subset.

The problem arises from a SQL procedure that updates a versioned
database table with multiple rows that may overlap the existing data
in the table. The procedure merges the updates into the table, then
fixes the versioning.

A versioned table has two date/time fields on each record defining an
interval during which the row was valid. A predicate (or key index)
defines the rows that belong to a timeline and are versioned. For each
timeline, none of the intervals may overlap, and the gap between
successive rows is small - three milliseconds in this case. There are
other ways of versioning, say with linked rows, but the problem is the
same.

If a new row falls between two existing rows, then the older row must
be versioned off with the time on the new row, and the new row is in
turn versioned off with the time on the younger row. This process is
well understood, and is not the problem here.

The tables are huge, and many timelines may be updated simultaneously.
Good performance demands that only a small subset of the data is
examined. In this context only recent rows are affected, so I am
looking for the earliest one that could be affected by the merge
operation. This will be the immediate predecessor of the earliest
record I inserted in each timeline, if any.

It is this "if any" that is giving me difficulty. The problem is
common, and arises whenever a new timeline is started.

I have been playing around with notations, but none have been
satisfactory, so I don't want to pre-empt any ideas you guys may have.

Jamie

[Jamie Oglethorpe]

Here is my effort.

Given totally ordered discrete set T, and a proper subset S ⊂ T, we
have:

m∈S:〈A x∈S :: m≤x〉is the least member of S,
P:〈A x∈T :: x<m ≡ x∈P〉is the set of predecessors of m,
and for P≠∅,
n∈P:〈A x∈P :: n≥x〉is the greatest member of P.

The characteristic a∈T I want is
a: P=∅ ⇒ a=m ∧ P≠∅ ⇒ a=n


I think captures my idea: I need the minimum member of S, I need its
predecessors, I need the immediate predecessor, and I need to
distinguish between them.

Can anybody suggest a better answer?

Thanks,

Jamie

[Jeremy Weissmann]

Dear Jamie,

   Are you asking for comments on your scheme for some merging process?  Are you asking for a notation to capture it?  What ends should that notation serve?

   I'm afraid I don't quite understand what you are asking of us.

+j

Jamie

--
You received this message because you are subscribed the mathmeth.com mailing list.
To unsubscribe from this group, send email to Calculational-Math...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/Calculational-Mathematics?hl=en

[Jamie Oglethorpe]

Hi Jeremy,

I think I have answered my own question. I had battled to solve the
problem, and when I eventually got a solution, it felt wrong somehow.
This prompted me to post here. I then struggled to pose the problem
clearly, and eventually got to the first two paragraphs of my
posting.

I felt obliged to justify the problem statement, hence all that stuff
on data versioning. I should perhaps have resisted the temptation.

I then went ahead and answered my own question. I think that the
formal definitions I put down are the minimum required for my
purposes, but perhaps I am wrong. I am very much an amateur in these
matters.

Having gotten this far, I would welcome a critique of my efforts. The
corresponding SQL query still feels clunky to me.

Thanks

Jamie

On Mar 6, 3:11 pm, Jeremy Weissmann <jer...@mathmeth.com> wrote:
> Dear Jamie,
>
>    Are you asking for comments on your scheme for some merging process?
>  Are you asking for a notation to capture it?  What ends should that
> notation serve?
>
>    I'm afraid I don't quite understand what you are asking of us.
>
> +j
>
> On Mon, Mar 5, 2012 at 7:12 AM, Jamie Oglethorpe

> <jamieogletho...@gmail.com>wrote:

> > You received this message because you are subscribed the mathmeth.commailing list.

[Jeremy Weissmann]

Jamie,

   I would be happy to comment, but I confess I do not have much experience with environments like SQL.  (Not even enough to know if 'environment' is the right term!)  Thus it would be a great boon to me if you could frame your question a little more precisely, so I know what to comment on.

   Thanks!

+j

You received this message because you are subscribed the mathmeth.com mailing list.

[Jamie Oglethorpe]

Jeremy,

I don't think we need to go into Codd's theory of relational
databases, except to note that a database table is a functional
relationship between each row's key and the rest of the data in that
row. The problem arises from updating the table, which can be thought
of as replacing the table's functional relation with the union of the
original relation and the update table's functional relation. In the
intersection of the two relations, the functional values of the update
relation replace the original function values.

So far so simple.

My problem is that my table is versioned, and represents the update
history of a collection of objects. Each row represents the object's
value over a time period. This is achieved by attaching a Timestamp
from which the object had a given value to the object's key.

When we refer to an object at a particular time, we want to find the
one with the most recent Timestamp on or before the given time. To
avoid a lot of searching, we define a second function in terms of the
object key and the from Timestamp, namely the shortest possible time
before the next version's from Timestamp. This function value is
calculated and saved on the row. If there is no following version, we
set it to eternity.

After we have done our update union, we need to recompute our to
Timestamp function. Here we have a performance problem. The table can
contain many millions of rows, an for the vast majority the function
remains unchanged. Only inserted rows can affect it, so we need only
consider the row preceding the first insertion to the end for each
timeline. We could also be creating a new timeline, so there is no
predecessor.

My original problem statement was an abstraction of this problem.
Almost all key field data is totally ordered, so we can usually sort
keys into lexicographic (dictionary) order, hence the table and each
timeline is totally ordered. The update relation is a subset of the
merged relations, and the update relation is recent (I.e. has high key
values). So we can save time by only considering the rows current at
the time that the first update row was inserted for each timeline.

I want to identify that row.

I have learned several things from writing this posting.

0. I had not considered the To Timestamp function before. It can play
a part in finding my rows.
1. I had previously thought in terms of the earliest update row in
each timeline, not the earliest inserted update row. The inserted rows
can be identified by eternity To Timestamp values, so one of my
quantifiers could be eliminated.
2. It occurs to me that many timelines are unaffected by the update,
and could be ignored if I knew the earliest update table From
Timestamp value.

Jamie

On Mar 6, 4:37 pm, Jeremy Weissmann <jer...@mathmeth.com> wrote:
> Jamie,
>
>    I would be happy to comment, but I confess I do not have much experience
> with environments like SQL.  (Not even enough to know if 'environment' is
> the right term!)  Thus it would be a great boon to me if you could frame
> your question a little more precisely, so I know what to comment on.
>
>    Thanks!
>
> +j
>
> On Tue, Mar 6, 2012 at 8:57 AM, Jamie Oglethorpe

> <jamieogletho...@gmail.com>wrote:

[Dhruv Matani]

Hello Jamie,

Why don't you just create an index on the timestamp column and perform
a predecessor query for the timestamp you are interested in?
Something like: SELECT * FROM tablename WHERE timestp <= QUERY ORDER
BY timestp DESC LIMIT 1;

A good optimizer will be able to perform this query in O(log n) time
(for some base 'B' of the logarithm). To aid the optimizer, you can
create a descending index on timestamp.

Regards,
-Dhruv.

> You received this message because you are subscribed the mathmeth.com mailing list.

> To unsubscribe from this group, send email to Calculational-Math...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/Calculational-Mathematics?hl=en

--
   -Dhruv Matani.
http://dhruvbird.com/

"What's the simplest thing that could possibly work?"
-- Ward Cunningham

[Jamie Oglethorpe]

Dhruv,

That would be nice, but sadly Microsoft SQL Server does not have the
LIMIT option on the ORDER BY clause. I need the upper value, either as
part of the key, or as key data (INCLUDE) to achieve O(log.n)
performance.

Jamie

>    -Dhruv Matani.http://dhruvbird.com/

[Jamie Oglethorpe]

Dhurv,

I see that SQL SERVER 2012 has a LAG operator to fetch a value from a
preceding record according to some ORDER sequence, and LEAD for a
value from a following record. They will allow versioning without the
To Timestamp, hopefully with O(log.n) for the first key and O(1)
performance for the second key if the index and clustering is set up
correctly.

Unfortunately we cannot count on that.

Jamie

[Dhruv Matani]

Hello Jamie,

Maybe you can try the workaround mentioned in this articles below.
http://www.aspfaq.com/sql2005/show.asp?id=11
http://channel9.msdn.com/forums/Coffeehouse/102407-SQL-Server-and-LIMIT-clauses-on-SELECT-statements/

Additionally, if you are using cursors, you can just get the first
result and discard the rest (close connection, etc...) for the similar
worst case complexity.

This is hardly "calculational math though"!

Regards,
-Dhruv.

> For more options, visit this group at http://groups.google.com/group/Calculational-Mathematics?hl=en

--
   -Dhruv Matani.

[Jamie Oglethorpe]

Hi Dhruv,

Let us do some calculational math then. First, terminology.

Let Table be our table, TLkey be the key field that identifies our
timeline, FTS be the From Timestamp field TTS be the To Timestamp
field, and Data our data field. I am deliberately oversimpifying here.
We also have UTable, our update table. It also has TLkey, FTS and
Data.

Let T, T0, T1, ... be the relation that represents the value of Table
at various moments. We say T = Table.relation.
Let U, U0, U1, ... be the relation that represents the value of UTable
at various moments. We say U = UTable.relation.

Let t, t0, t1, ... be the elements of any of T, T0, T1, ...
Let u, u0, u1, ... be the elements of any of U, U0, U1, ...
These represent the rows of Table and UTable respectively.

We postulate that the values of TLkey, FTS and TTS are totally
ordered. TTS can also take the value eternity so that [t.TTS ≤
eternity]. Otherwise FTS and TTS can take the same values.

We define for both t, u, here x, x.key as totally ordered where for
any x0, x1,
x0.key ≤ x1.key ≡ x0.TLkey < x1.TLKey ∨ (x0.TLkey = x1.TLKey ∧ x0.FTS
≤ x1.FTS).

I won't prove here that key is totally ordered equivales TLkey and FTS
are totally ordered.

Our "MERGE" program has precondition
P: T0 = Table.relation ∧ U0 = UTable.relation,
and postcondition
R: T1 = Table.relation
∧ 〈A t, u : t∈T0 ∧ u∈U0 ∧ t.key=u.key : 〈E t0 : t0∈T1 :
t0.key=t.key ∧ t0.Data=u.Data ∧ t0.TTS=t.TTS 〉〉
∧ 〈A t : t∈T0 : ~〈E u: u∈U0 : t.key=u.key〉 : 〈E t0 : t0∈T1 :
t0.key=t.key ∧ t0.Data=t.Data ∧ t0.TTS=t.TTS 〉〉
∧ 〈A u : u∈U0 : ~〈E t: t∈T0 : t.key=u.key〉 : 〈E t : t∈T1 :
t.key=u.key ∧ t.Data=u.Data ∧ t.TTS=eternity 〉〉
∧ 〈A t : t∈T1 : 〈E t0: t0∈T0 : t.key=t0.key〉 ∨ 〈E u: u∈U0 :
t.key=u.key〉〉

I will not include the SQL here, but it is straightforward. In
essence, it uses an INSERT statement to establish the second clause
and an UPDATE statement to establish the fourth clause. The third
clause is established by the precondition. The final clause says that
we don't do anything else. The INSERT uses a subquery or LEFT OUTER
JOIN to confirm that the row does not yet exist, and the UPDATE uses
an INNER JOIN to join to existing rows.

Our "FIX TTS" has the precondition
P: T0 = Table.relation
and establishes the postcondition
R: T1 = Table.relation
∧ 〈A t, t0 : t∈T1 ∧ t0∈T0 ∧ t.key=t0.key : t.Data = t0.Data〉
∧ 〈A t : t∈T1 : 〈E t0 : t0∈T0 : t.key=t0.key〉〉
∧ 〈A t : t∈T0 : 〈E t0 : t0∈T1 : t.key=t0.key〉〉
∧ 〈A t : t∈T1 : 〈E t0 : t0∈T1 : t.TLkey=t0.TLkey ∧ t.FTS>t0.FTS
∧ ~〈E t1 : t1∈T1 : t.TLkey=t1.TLkey ∧ t.FTS>t1.FTS ∧
t1.FTS>t1.FTS〉
∧ t.TTS=t0.FTS-δ〉〉
∧ 〈A t : t∈T1 : ~〈E t0 : t0∈T1 : t.TLkey=t0.TLkey ∧ t.FTS>t0.FTS〉
∧ t.TTS=eternity〉

where δ is the smallest possible time interval. Here the second, third
and fourth clauses say that we only change TTS, and the final two
clauses spell out the changes if a successor exists, and if there is
no successor.

The obvious implementation uses an UPDATE statement with two LEFT
OUTER JOINS from the Table to itself, all of which equal TLKey, both
have FTS greater than the first table, and the third has FTS less than
the second. The WHERE clause ensures that the third row does not exist
(i.e. the second, if any, is the immediate successor of the first).
TTS is set to eternity if the second row does not exist, otherwise it
sets it to the FTS on the second row less a small amount.

Like I said before, this is not the issue. The issue is that we can
assume that before the MERGE, we have the precondition:
P: T0 = Table.relation ∧ U0 = UTable.relation,
∧ 〈A t : t∈T0 : 〈E t0 : t0∈T0 : t.TLkey=t0.TLkey ∧ t.FTS>t0.FTS
∧ ~〈E t1 : t1∈T0 : t.TLkey=t1.TLkey ∧ t.FTS>t1.FTS ∧
t1.FTS>t1.FTS〉
∧ t.TTS=t0.FTS-δ〉〉
∧ 〈A t : t∈T0 : ~〈E t0 : t0∈T0 : t.TLkey=t0.TLkey ∧ t.FTS>t0.FTS〉
∧ t.TTS=eternity〉

and its postcondition asserts that TTS is unchanged for all rows in
the table before the update. Because this table records the history of
the data values of some entities, I posit that for each TLkey, there
is a minimum value of MFTS before which TTS already has the correct
value. The precondition for "FIX TTS" then becomes:
P: T0 = Table.relation
∧ 〈A t : t∈T0 ∧ t.FTS < t.MFTS : 〈E t0 : t0∈T0 : t.TLkey=t0.TLkey
∧ t.FTS>t0.FTS
∧ ~〈E t1 : t1∈T0 : t.TLkey=t1.TLkey ∧ t.FTS>t1.FTS ∧
t1.FTS>t1.FTS〉
∧ t.TTS=t0.FTS-δ〉〉
∧ 〈A t : t∈T0 ∧ t.FTS < t.MFTS : ~〈E t0 : t0∈T0 :
t.TLkey=t0.TLkey ∧ t.FTS>t0.FTS〉
∧ t.TTS=eternity〉

The point of my original posting was to establish the value of MFTS.

I have the following observations.

0. MFTS depends on UTable.relation, in particular on the least FTS for
each TLkey that did not match an element of Table.relation.
1. MERGE set TTS to eternity for each inserted row.
2. If the first inserted row t has a predecessor t0, then t0.TTS is
invalid, but all its predecessors are valid, then t0.MFTS = t0.FTS.
3. If the first inserted row t does not have a predecessor, then
t.MFTS = t.FTS.
4. If we don't attempt this optimization, we should still compare
t.TTS with t0.FTS-δ, and not update when they are already equal. At
least we avoid the cost of all those saves to disk.

On Mar 6, 11:41 pm, Dhruv Matani <dhruvb...@gmail.com> wrote:
> Hello Jamie,
>

> Maybe you can try the workaround mentioned in this articles below.http://www.aspfaq.com/sql2005/show.asp?id=11http://channel9.msdn.com/forums/Coffeehouse/102407-SQL-Server-and-LIM...

> ...
>
> read more »