

2013.05.22 12:47

Recursive Lineage Queries in SQL and RyuQ


Without explaining every detail, here is a “proper” (as in, non-NULL dependent) method for handling tree data within a recursive query. In the example below table foo has an id, a parent and aÂ dtg (date-time-group). Obviously real world examples will have more fields, but this illustrates the technique. This sort of thing is quite handy in a huge variety of situations as quite a lot of data is hierarchical in nature.

Adding a layer type attribute on the view is also a good way to accomplish things like, say, providing visual layout variables for threaded comments on a website, even if your (stupid) web framework doesn’t understand such things — you can bypass the framework garbage by defining a lineage-type view directly in the database and a “model” on top of it.

Â  $$
Â Â Â Â Â  NEW.parent :=;
Â  $$ LANGUAGE plpgsql;

Â  created_on timestamptz DEFAULT current_timestamp NOT NULL);

CREATE TRIGGER foo_default_parent

CREATE TRIGGER foo_reset_parent

Â  parents AS
Â Â Â  (SELECT * FROM foo WHERE parent = id),
Â  children AS
Â Â Â  (SELECT * FROM foo WHERE parent != id),
Â  tree AS
Â Â  (SELECT id,
Â Â Â Â Â Â Â Â Â Â  id::text AS branch,
Â Â Â Â Â Â Â Â Â Â  0 AS layer,
Â Â Â Â Â Â Â Â Â Â  parent
Â Â Â Â Â  FROM parents
Â Â Â Â Â Â Â Â Â Â  t.branch || '.' || AS branch,
Â Â Â Â Â Â Â Â Â Â  t.layer + 1 AS layer,
Â Â Â Â Â Â Â Â Â Â  c.parent
Â Â Â  FROM children AS c, tree AS t
Â Â Â  WHERE c.parent =
Â  SELECT * FROM tree ORDER BY branch;

CREATE OR REPLACE FUNCTION show_descendants(parent integer) RETURNS TABLE
Â Â  (idÂ Â Â Â Â  integer,
Â Â Â  lineage text,
Â Â Â  layerÂ Â  integer,
Â Â Â  parentÂ  integer) AS
Â  $$
Â Â Â  parents AS
Â Â Â Â Â  (SELECT * FROM foo WHERE id = $1),
Â Â Â  children AS
Â Â Â Â Â  (SELECT * FROM foo WHERE parent != id),
Â Â Â  tree AS
Â Â Â Â  (SELECT id,
Â Â Â Â Â Â Â Â Â Â Â Â  id::text AS branch,
Â Â Â Â Â Â Â Â Â Â Â Â  0 AS layer,
Â Â Â Â Â Â Â Â Â Â Â Â  parent
Â Â Â Â Â Â Â  FROM parents
Â Â Â Â Â Â Â Â Â Â Â Â  t.layer + 1 AS layer,
Â Â Â Â Â Â Â Â Â Â Â Â  c.parent
Â Â Â Â Â  FROM children AS c, tree AS t
Â Â Â Â Â  WHERE c.parent =
Â Â Â  SELECT * FROM tree ORDER BY branch;

Â  get_lineage(parent_id integer DEFAULT 0, hide_parent boolean DEFAULT false)
Â Â  (idÂ Â Â Â Â  integer,
Â Â Â  lineage text,
Â Â Â  layerÂ Â  integer,
Â Â Â  parentÂ  integer) AS
Â  $$
Â Â Â Â Â  IF parent_id > 0 AND hide_parent IS true THEN
Â Â Â Â Â Â Â  RETURN QUERY EXECUTE $query$ SELECT * FROM show_descendants($1) OFFSET 1 $query$
Â Â Â Â Â Â Â Â Â  USING parent_id;
Â Â Â Â Â  ELSIF parent_id > 0 AND hide_parent IS false THEN
Â Â Â Â Â Â Â  RETURN QUERY EXECUTE $query$ SELECT * FROM show_descendants($1) $query$
Â Â Â Â Â Â Â Â Â  USING parent_id;
Â Â Â Â Â Â Â  RETURN QUERY EXECUTE $query$ SELECT * FROM lineage $query$;
Â  $$ LANGUAGE plpgsql STABLE;

Let’s see some invocations:

insert into foo values (default);
insert into foo values (default);
insert into foo values (default);
insert into foo values (default, 1);
insert into foo (parent) values (1);
insert into foo (parent) values (1);
insert into foo (parent) values (1);
insert into foo (parent) values (2);
insert into foo (parent) values (3);
insert into foo (parent) values (3);
insert into foo (parent) values (4);
insert into foo (parent) values (5);
insert into foo (parent) values (7);
insert into foo (parent) values (7);
insert into foo (parent) values (10);
insert into foo (parent) values (15);

select * from lineage;
Â id |Â Â  branchÂ Â  | layer | parent 
Â  1 | 1Â Â Â Â Â Â Â Â Â  |Â Â Â Â  1 |Â Â Â Â Â  1
Â  4 | 1.4Â Â Â Â Â Â Â  |Â Â Â Â  2 |Â Â Â Â Â  1
Â 11 | 1.4.11Â Â Â Â  |Â Â Â Â  3 |Â Â Â Â Â  4
Â  5 | 1.5Â Â Â Â Â Â Â  |Â Â Â Â  2 |Â Â Â Â Â  1
Â 12 | 1.5.12Â Â Â Â  |Â Â Â Â  3 |Â Â Â Â Â  5
Â  6 | 1.6Â Â Â Â Â Â Â  |Â Â Â Â  2 |Â Â Â Â Â  1
Â  7 | 1.7Â Â Â Â Â Â Â  |Â Â Â Â  2 |Â Â Â Â Â  1
Â 13 | 1.7.13Â Â Â Â  |Â Â Â Â  3 |Â Â Â Â Â  7
Â 14 | 1.7.14Â Â Â Â  |Â Â Â Â  3 |Â Â Â Â Â  7
Â  2 | 2Â Â Â Â Â Â Â Â Â  |Â Â Â Â  1 |Â Â Â Â Â  2
Â  8 | 2.8Â Â Â Â Â Â Â  |Â Â Â Â  2 |Â Â Â Â Â  2
Â  3 | 3Â Â Â Â Â Â Â Â Â  |Â Â Â Â  1 |Â Â Â Â Â  3
Â 10 | 3.10Â Â Â Â Â Â  |Â Â Â Â  2 |Â Â Â Â Â  3
Â 15 | 3.10.15Â Â Â  |Â Â Â Â  3 |Â Â Â Â  10
Â 16 | |Â Â Â Â  4 |Â Â Â Â  15
Â  9 | 3.9Â Â Â Â Â Â Â  |Â Â Â Â  2 |Â Â Â Â Â  3
(16 rows)

select * from get_lineage(3);
Â id |Â  lineageÂ Â  | layer | parent 
Â  3 | 3Â Â Â Â Â Â Â Â Â  |Â Â Â Â  0 |Â Â Â Â Â  3
Â 10 | 3.10Â Â Â Â Â Â  |Â Â Â Â  1 |Â Â Â Â Â  3
Â 15 | 3.10.15Â Â Â  |Â Â Â Â  2 |Â Â Â Â  10
Â 16 | |Â Â Â Â  3 |Â Â Â Â  15
(5 rows)

select * from get_lineage(3, true);
Â id |Â  lineageÂ Â  | layer | parent 
(4 rows)

Notice that there are no NULLs. Most formulations of tree type data uses NULL to represent not having a parent — but this is wrong. NULL means something is unknown. If the top-level nature of an entity is known, then NULL is the wrong value and complicates any logic involving that field unnecessarily. If, instead, we define a top level entity as any entity which is its own parent, then we have no ambiguity in the structure, and we are providing a correct model. For this reason the parent column above is NOT NULL. If we wanted to provide the possibility of maintaining records where the parent was actually unknown, we could remove the NOT NULL constraint and unset the trigger.

That may sound nitpicky, but there are several places where this simplifies things or makes query execution downright unreliable because of a dependence on conditional logic shortcuts. Consider the common SQL function solution comparable to show_descendants() above:

CREATE OR REPLACE FUNCTION show_descendants(parent integer) RETURNS TABLE
Â Â  (idÂ Â Â Â Â  integer,
Â Â Â  lineage text,
Â Â Â  layerÂ Â  integer,
Â Â Â  parentÂ  integer) AS
Â  $$
Â Â Â Â  (SELECT id,
Â Â Â Â Â Â Â  FROM foo
        WHERE (parent IS NULL AND $1 = 0) OR (parent = $1)
Â Â Â Â Â  WHERE c.parent =
Â Â Â  SELECT * FROM tree ORDER BY branch;

This works just fine in Postgres 9.2 — but that is a quirk of implementation. SQL is supposed to be declarative in nature, and as such there is no guarantee which side of the OR condition in WHERE will be executed first. It is cheaper to check the single condition on the right side than the AND condition on the left, so it is likely a future execution optimization will detect that and run the query this way. The problem is that the right side expression can be true in invalid cases. There is no way to write this query safely as long as NULL is a possible value for parent.

Another problem is that using a NULL parent value in any calculation will nuke the entire operation because of NULL propagation. Say you want to do “parent::text || foo” somewhere later. Surprise! Any NULL is going to kill the entire string. There are convoluted ways to avoid that, but we’re fighting against the nature of an unnatural data definition instead of providing a natural definition at the outset and letting the positive consequences follow.

An argument can be made that handling for-real parent values instead of just using NULL definitions complicates the code above unnecessarily. Its true, in SQL you have to define a trigger to handle the top-level case and be a little more specific in the view and function definitions that follow. But that’s the end of it. We’ve trapped the NULL and completely contained the complexity involved in modeling an accurate parent relationship, not mention guarded against the undefined nature of logical OR execution (this is a huge issue on its own). If we were to permit a NULL here and didn’t really intend for that to mean unknown, then we would have traded the convenience of writing a quick and dirty definition for letting the complex and unpredictable side effects escape our model and propagate throughout the rest of the schema and every application that touches this table. With that in mind it is obviously a better solution to pay the complexity tax up front and write the insert trigger and function definitions and nip the issue in the bud.

In RyuQ this can be defined as:

create [relation]
Â  foo
Â Â Â  attributes
Â Â Â Â Â  idÂ Â Â Â Â Â Â Â  Serial
Â Â Â Â Â  parentÂ Â Â Â  Integer
Â Â Â Â Â  created_on TimestampTZ
Â Â Â  conditions
Â Â Â Â Â  pk id
Â Â Â Â Â  fks
Â Â Â Â Â Â Â  parent ->
Â Â Â Â Â  defaults
Â Â Â Â Â Â Â  parent = id
Â Â Â Â Â Â Â  created_on = current_timestamp

And define some elabels to operate on the data:

tree = union
Â Â Â Â Â Â Â Â  project [id, lineage = id::text, layer = 1, parent]
Â Â Â Â Â Â Â Â Â Â  select [parent == id] foo
Â Â Â Â Â Â Â Â  project [id =,
Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â  lineage = tree.lineage + '.' +,
Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â  layer = tree.layer + 1,
Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â  parent = foo.parent]
Â Â Â Â Â Â Â Â Â Â  join
Â Â Â Â Â Â Â Â Â Â Â Â  tree
Â Â Â Â Â Â Â Â Â Â Â Â  select [parent != id] foo

branch ID =
Â Â Â Â Â Â  union
Â Â Â Â Â Â Â Â Â Â  select [id == ID] foo
Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â  lineage = branch.lineage + '.' +,
Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â  layer = branch.layer + 1,
Â Â Â Â Â Â Â Â Â Â  join
Â Â Â Â Â Â Â Â Â Â Â Â  branch

headless ID = select [parent != id] branch ID

And that’s it. Notice that there are no NULLs here either; we are not using any MaybeType attributes. If we wanted to make the definition of a top-level entity “Something without a parent” then using the type NoneInteger would be correct. If we wanted to include the possibility that a parent relationship is unknown (but that this does not define a top-level entity) we could useÂ MaybeInteger. If we want to include both then we should define a domain that includes integers, None, and _|_ as members, possibly calling it MaybeNoneInteger.


insert [foo]
  (default), (default), (default)
  (1), (1), (1), (2), (3), (3), (4), (5), (7), (7), (10), (15)

 id |   branch   | layer | parent 
  1 | 1          |     1 |      1
  4 | 1.4        |     2 |      1
 11 | 1.4.11     |     3 |      4
  5 | 1.5        |     2 |      1
 12 | 1.5.12     |     3 |      5
  6 | 1.6        |     2 |      1
  7 | 1.7        |     2 |      1
 13 | 1.7.13     |     3 |      7
 14 | 1.7.14     |     3 |      7
  2 | 2          |     1 |      2
  8 | 2.8        |     2 |      2
  3 | 3          |     1 |      3
 10 | 3.10       |     2 |      3
 15 | 3.10.15    |     3 |     10
 16 | |     4 |     15
  9 | 3.9        |     2 |      3
(16 rows)

branch 3
 id |  lineage   | layer | parent 
  3 | 3          |     0 |      3
 10 | 3.10       |     1 |      3
 15 | 3.10.15    |     2 |     10
 16 | |     3 |     15
  9 | 3.9        |     1 |      3
(5 rows)

headless 3
 id |  lineage   | layer | parent 
 10 | 3.10       |     1 |      3
 15 | 3.10.15    |     2 |     10
 16 | |     3 |     15
  9 | 3.9        |     1 |      3
(4 rows)

Pretty simple. I find the RyuQ easier and more clear, but obviously I’m biased.

2013.05.20 22:17

More on a new Data Language

I’ve given more thought to the new data language I’m working on, and finally decided on a name as well.

The new baby shall be called RyuQ — a reference to where I live respelled to accommodate the mandatory “Q” in any shiny new query language. I’ve settled on a modified form of S-expressions, calling them SP-expressions to distinguish between real S-expressions and my mutated version. The (still infantile) language description is peppered with examples, so you can see pretty quickly if SP-expressions feel comfortable or more alien relative to SQL.

I have to say, the further I go on this the more I wonder what was going through the minds on the committee that created SQL. So many things are just so obvious when sticking to an algebraic notation rather than trying to form some new thing that is neither relational algebra nor relational calculus.

Until I have a complete implementation worked into a fork of Postgres I won’t be able to do anything but toy with this language — but the more thought I give it the less I am satisfied with the work I am currently compelled to do in SQL.

2013.05.16 21:43

Thinking About a Data Langauge

Filed under: Computing — Tags: , , , , — zxq9 @ 21:43

I’ve been thinking a lot lately about how a query and data definition language would look if I were able to write one myself. Well, it turns out I can write one myself, it just takes a lot of time. I don’t have a lot of time, but I’ve written down some of my ideas to clarify them and placed them here. This is mostly just a text-friendly way of writing relational algebra, but it has a few extras that would make it much nicer to use than SQL.

The mid-term goal is to implement at least some of the query language either as part of a runtime that sits outside of Postgres and feels like psql with something better than SQL, or hack an alternate parser into Postgres that would provide parsed Query trees to the optimizer. I haven’t decided which will be more time consuming in the long run just yet.

I’ll keep that area updated as I have time to work on the language spec more. There are quite a few ideas I’ve got left to commit to writing but just can’t yet due to time.

2012.08.27 11:55

Lean on Your Database

Filed under: Computing — Tags: , , , — zxq9 @ 11:55

Doing computations in the database is almost always the right answer. Writing your own database procedures instead of relying on an ORM framework is even better. These go hand in hand since ORMs don’t allow you enough control over your data schema to define calculations in the first place (most can’t even properly handle multi-column primary keys and instead invent meaningless integer ID for everything; this should tell you something). Many, maybe most (at least that I’ve met), web developers don’t even know what sort of calculations are available to be performed in the database because they’ve been taught, in an absolute vacuum of personal experience, that “SQL hard. Relational thinking hard. OOP good. Trust framework”. There is so much missing here.

Frameworks try to be “database agnostic”. This is fundamentally flawed thinking. This implies that the data layer is merely there for “persistence” and that the “persistence layer” can be whatever — all RDBMS systems “aren’t OO and therefore suck” and so any old database will do. If this is true then it follows that frameworks and applications should be designed to work against any database system and not delve too deeply into any specific feature sets — after all, the application functionality is the focus, not the data, right? This is exactly backwards.

Even forgetting that this condemns you to least-common-denominator data design, this is still exactly backwards. Let me put the right way on a line all by itself, because it just that important:

Data designs should strive to be application agnostic.

Data drives everything. Your functions are what you can change around easily, but your data schema is critical and represents everything about your system logic. If you show me a well-labeled data schema I can probably guess what you are trying to do, but if you show me just your functions and objects I’ll require either a code tour or a lot of familiarization time before getting anything serious done (that project documentation will be lacking is a truism not worth addressing here).

Consider that changing your app code is cake whereas changing your data schema is major project surgery. OOP has us so in a stupor that we think if we just get our objects right everything will be fine. It won’t. Ever. As long as you think that you’ll also believe other crap like that each object should map directly to a table. There are certain basic truths about certain types of data. It is striking that I can give a data requirement to two DBAs schooled on two different RDBMSes and ask for a normalized data model (let’s just say NF3 for argument) and get back two very similar looking schemas, but I can give a feature requirement to two Java programmers and get back radically different system designs.

This should tell us something. In fact, it screams the truth that data is a foundation from which you must work up toward the application code, not the other way around. The database layer is the most important place to make sound choices. The choice of database system itself should be based on project requirements, because that choice matters. Most critically, I’ll say it again here because it is so important and implies so much on contemplation: the database designs should strive to be application agnostic.

2012.08.14 05:52


Filed under: Computing — Tags: , , , , , , — zxq9 @ 05:52




















class ProductRecord(models.Model):

Â Â Â  class Meta:
Â Â Â Â Â Â Â  managed = False


class ProductValueHistory(models.Model):

Â Â Â  class Meta:
Â Â Â Â Â Â Â  managed = False




CREATE VIEW sales.product_record AS
Â Â Â Â Â  inventory.item AS i, sales.product AS s
Â Â Â Â Â  i.nsn = s.item;



CREATE VIEW sales.product_value_history AS
Â Â Â Â Â  p.sku AS sku,
Â Â Â Â Â Â Â  WHEN p.start_date < c.start_date
Â Â Â Â Â Â Â Â Â  THEN p.start_date
Â Â Â Â Â Â Â Â Â  ELSE c.start_date
Â Â Â Â Â Â Â  AS start_date,
Â Â Â Â Â Â Â  WHEN p.end_date < c.end_date
Â Â Â Â Â Â Â Â Â  THEN p.end_date
Â Â Â Â Â Â Â Â Â  ELSE c.end_date
Â Â Â Â Â Â Â  AS end_date,
Â Â Â Â Â  c.value AS cost,
Â Â Â Â Â  p.value AS price
Â Â Â Â Â  sales.price_history AS p,
Â Â Â Â Â Â Â  p.product = c.sku





product = ProductRecord.objects.get(id=number)
value_history = product.price_history.all()


product = ProductRecord.objects.get(nsn=value)
value_history = ProductValueHistory.objects.filter(sku=product.sku)


current_value = ProductValueHistory.objets.filter(sku=product.sku)[0]








2012.08.12 17:27

On Looping and Recursion



wearetheborg wrote:


















#include <stdio.h>

int main()
    int x = 10;

    while (x > 0)
        printf("%d\n", x);

    return 0;


(define (countdown x)
    (display x)
    (if (> x 1)
      (countdown (1- x))
      (display "Blastoff!\n"))))

(countdown 10)




(define (countdown x)
  (if (> x 1)
    (countdown (1- x))
    (display "Blastoff!\n")))





Powered by WordPress