Thread: Inheritance Algebra

Inheritance Algebra

From
Trent Shipley
Date:
[
This post is theory oriented, so it can't go in HACKERS
nor can it go in SQL
so it gets posted to GENERAL.

I would polish this more.  Unfortunately, it is at the point were I'd seek
feedback were I in a seminar.
]

Relational Constraint Inheritance Algebra
With regard to class and attribute uniqueness

 0 Intro: Postgresql inheritance and uniqueness

Postgresql's INHERITS is one of the most intriguing features of the
at-liberty, open-source database.  At the same time, most observers regard
INHERITS as an incomplete implementation of a fully object-oriented, or
better, class-aware, database function.  The most glaring omission is that
primary key and unique constraints are not inherited by children.

Nevertheless, the implementation of     INHERITS has not changed much through the
last several revisions of Postgresql.  Bizgres' partitioning scheme,
constraint based exclusion [?], relies on the current default behavior of
inheritance in Postgresql.  No doubt other consumers have taken advantage of
the feature's current behavior, so any extension must preserve existing
behavior by either developing sub-clauses that further specify the behavior
of the INHERITS or they must develop an entirely new lexis for building
inheritance based relational classes.

When a constraint is declared in a database that supports relational
inheritance, the constraint necessarily has scope.  In the simplest cases,
constraint scope is local, applying only to the table where the constraint
was declared, or the scope is to the subclass, applying to this table and all
descendants unless over-ridden.  According to the Postgresql 8.0
documentation, all constraints are automatically inherited unless over-ridden
(the subclass model) except for foreign and unique constraints that are
unsupported at the class level.  In effect, under Postgresql 8.0 foreign and
unique constraints have local scope.

Another notable quirk of Postgresql's inheritance model is that no table is
explicitly aware it could become a parent.  There is no “abstract” or “final”
clause nor any other clause restricting the behavior or potential children
exists in “CREATE TABLE”.  Indeed, the top of any inheritance hierarchy
necessarily begins as a strictly relational table.  One side effect of the
current model is that implementing class-wide uniqueness is problematic.
Either the parent model would need to be abstract (a nonexistent clause) or a
child's inheritance of a unique constraint would change the behavior of the
parents heretofore table-local unique (or even non-unique) column.

Postgresql's current hybrid implementation of inheritance, having both
implicitly local and subclass scope for  different kinds of constraints,
points to a powerful hybrid model where columns can have   constraints that
are explicitly declared with table-local or subclass-wide scopes.

The rest of this essay examines the interaction of localism-class cross
plurality-uniqueness[1].  It seems obvious that the distinctions have
theoretical discussion (and hopefully acceptance).  More important is whether
the supporting these distinctions would be useful in any real-world product.
I believe that supporting such fine distinctions would be of some use, but
will make no further effort to argue the case.

 1 Types of relational inheritance models

Relational inheritance of a constraint feature has scope [2].  Levels of scope
include absent (necessarily local), table-local, subclass, class-wide, mixed,
and dual.
Obviously, support for relational inheritance can simply be absent.  This is
the norm.  Any  such table is strictly relational and all constraints are
necessarily local.  Tables in this essay are explicitly not under the
“absent” relational inheritance scope.

Another family of models for relational inheritance scope might be called
local (table-local or relation-local).  If Postgresql's CREATE TABLE ... LIKE
clause allowed for “inheritance” of all constraints, triggers, and so on, it
would be an implementation of the local model.  In particular, unique
constraints are checked for each table in the class but are not enforced over
the whole of an entire class or subclass.  Presumably, if table-local scope
were the default behavior across a database, queries would not recurse into
descendant tables by default.  Note that this used to be Postgresql's default
behavior.  SQL developers had to ask the engine to recurse into descendant
tables.

Mixed scope models extend the local model, allowing for class-like treatment
of some relational aspects.  (In this essay we are particularly concerned
with plurality-uniqueness.)  Arguably (and unfortunately), Postgresql
currently implements a mixed model.  Some constraints have subclass scope and
some have local scope.

A traditional, strictly hierarchical inheritance of constraints from
object-aware tables by descendants is a powerful scoping model.   Strictly
speaking, every table belongs to a class, and if one table inherits from
another it becomes parent of a new subclass.  Unless over-ridden, a given
constraint in a child table is the same as the constraint in the parent.
Furthermore, in the case of uniqueness (or any other constraint that makes
semantic sense as a property of the class-as-a-whole) the constraint is
enforced for the entire class on the basis of inclusion by subclass.

It is possible to create a “flat” class model where any class member can
change flass-wide behavior.  In particular, where first generation children
necessarily inherit from a “strictly relational” parent  it is tempting to
set class parameters at the F-1 generation rather than at F-0.  That is,
designers may be tempted to develop a set of “flat” rules for class behavior
that allow children to alter or constrain the current behavior of parents
[3].  In general, flat class models are unwise.

The most powerful model might be called “dual” because strictly relational
tables and class-aware tables can freely interact.  It largely follows a
subclass model but allows old-fashioned relational tables to exist outside
the class structure.   Dual scope models might allow for found inheritance
where purely relational tables can be captured as parents by class-oriented
tables.  A dual scope model could also allow for sub-class or local scope in
uniqueness, as advocated here.


 2 Algebra

 2.1 Domain

There are three main variables to consider when working on the algebra of
inheriting unique or plural constraints.  The first is whether or not the
constraint in This table has local or subclass scope.  The second is whether
This constraint is plural or unique.  The third is inheritance constraints,
that is, how This column constrains the class orientation and uniqueness of
descendants.

Both the “This scope variable” and the “This uniqueness variable” are binary.
The “descendant inheritance constraint variable”, however, is a composite
vector.  It has four sub-variables: local-plural, local-unique,
subclass-plural, and subclass-unique.  Each sub-variables can take on the
values of “forbid creation”, “allow creation”, or “require creation”.
Local-plural means controls whether descendant columns can be constrained
with plural table-local scope.  Subclass-unique controls whether descendant
columns must be subclass (class) unique, can be subclass unique, or are
forbidden to be subclass unique.

Note that descendant column constraints cannot be in two exclusive states at
once.  Thus, if any descendant inheritance constraint variable is required
then no other can be required.  For the same reason, if one sub-variable is
required and others are allowed, the allowances are irrelevant.  However, any
number of descendant inheritance constraint variables can be masked as
forbidden.  Likewise, any number can be allowed.

<pre>
-----------------------------------------------------
Descendant Inheritance Permissions
-----------------------------------------------------
       | Local                |Subclass
-----------------------------------------------------
Plural | forbid,allow,require | forbid,allow,require
-----------------------------------------------------
Unique | forbid,allow,require | forbid,allow,require
-----------------------------------------------------
</pre>

The domain (or raw truth table) for inheritance of plural and unique
constraints contains 324 elements.  Fortunately, all but 80 of the resulting
values are either wholly contradictory in that the contain two required
descendant constraints or partially contradictory because the contain one
required inherited constraint and allowed constraints that can never be
realized.  In practice, a hacker would cause the parser to throw an error if
it encountered a hard contradiction and would merge a partial contradiction
to one of the 80 simple states along with a notice or warning.  (See
Appendix.)


 2.2 Operations

Relational inheritance of uniqueness constraints needs to support at least
three operations: INHERIT, MERGE, and ALTER.  In addition one would want to
include drop, but one suspects that drop is a special case of ALTER.  Each
case involves an 80 * 80 sparse table (many results are inconsistent states),
so I have yet to work on them.

INHERIT takes a parent table, a child declaration, and produces a child
signature lying in the domain.

MERGE is needed when supporting multiple inheritance.  MERGE takes the
signature of parent_a and  parent_b.  It returns the merger of both as
pseudo_parent signature.  I expect that MERGE will not be associative but
will be commutative.

ALTER (that is, alter class-aware uniqueness constraint) is unusual because
the (future) behavior of a parent is constrained by its descendants.  ALTER
compares parent to descendant returning TRUE or FALSE, TRUE meaning that the
alteration is allowed.  This is repeated for each descendant in any
convenient order.  The results for each descendant are ANDed.  Note that
INHERIT is implicitly a compatibility table that could be recycled for ALTER.

DROP in a naive interpretation would always be allowed in a subclass system.
Each child would simply become the new root of an autonomous hierarchy.  In a
single rooted inheritance hierarchy (ala Java) dropping a parent requires
adjusting the would be orphans.  If multiple hierarchies are allowed, then
simply dropping parents would still be an excellent way to prevent mayhem.
One might want to allow developers (as opposed to administrators) to make
selected parent tables resistant to drops.  One winds up with at least simple
drop, drop and merge shrubs (creating an abstract root if needed), and drop
cascade (all subtrees dropped too).

-----
[1]:  I maintain that for the purposes of this essay “plural” is preferable to
“not unique” or “non-unique”.  Plural is of  course shorter, but I also find
it is easier to think in terms of the positive attribute  “plural” than in
terms of the negation of uniqueness, especially as the problem becomes more
involved.  Furthermore,  plurality is the most common parameter for a column
(relational attribute), arguably it is better to think of the phenomenon as a
first-class concept rather than only as the negation of the linguistically
marked, but relatively rare phenomenon of uniqueness.

[2]: Presumably other properties of a relation, including attributes
(columns), rules, and triggers would similarly have scope.

[3]: Children necessarily constrain future changes on parents in terms of
structural alteration or dropping the parent table entirely.

------


Appendix [*.csv]

"Domain for relation's inheritance of unique constraints (states)",,,,,,,,,,
,,,,,,,,,,
"Dimensions",,,,,,,,,,
"C = Local | subClass constraint scope on This column in This table",,,,,,,,,,
"U = Plural | Unique  constraint on This column in This table",,,,,,,,,,
"kp = forbid | allow | require subclassed inheritance as plural in
descendants",,,,,,,,,,
"kq = forbid | allow | require subclassed inheritance as unique in
descendants",,,,,,,,,,
"lp = forbid | allow | require local inheritance as plural in
descendants",,,,,,,,,,
"lq = forbid | allow | require local inheritance as unique in
descendants",,,,,,,,,,
,,,,,,,,,,
"Contradictions: ",,,,,,,,,,
,"-","no contradiction",,,,,,,,
,"x","contradiction: descendants required to be in two states ",,,,,,,,
,"p","partial: a required state hides allowed states",,,,,,,,
,,,,,,,,,,
,,,,,,,,,,
,"C","U","kp","kq","lp","lq",,"contradiction",,"note"
0,"L","P","f","f","f","f",,"-",0,"final"
1,"L","P","f","f","f","a",,"-",1,
2,"L","P","f","f","f","r",,"-",2,
3,"L","P","f","f","a","f",,"-",3,
4,"L","P","f","f","a","a",,"-",4,"implicitly supported by Postgresql"
5,"L","P","f","f","a","r",,"p",4,
6,"L","P","f","f","r","f",,"-",5,"obligatory local plural"
7,"L","P","f","f","r","a",,"p",5,
8,"L","P","f","f","r","r",,"x",5,
9,"L","P","f","a","f","f",,"-",6,
10,"L","P","f","a","f","a",,"-",7,
11,"L","P","f","a","f","r",,"p",7,
12,"L","P","f","a","a","f",,"-",8,
13,"L","P","f","a","a","a",,"-",9,
14,"L","P","f","a","a","r",,"p",9,
15,"L","P","f","a","r","f",,"p",9,
16,"L","P","f","a","r","a",,"p",9,
17,"L","P","f","a","r","r",,"x",9,
18,"L","P","f","r","f","f",,"-",10,
19,"L","P","f","r","f","a",,"p",10,
20,"L","P","f","r","f","r",,"x",10,
21,"L","P","f","r","a","f",,"p",10,
22,"L","P","f","r","a","a",,"p",10,
23,"L","P","f","r","a","r",,"x",10,
24,"L","P","f","r","r","f",,"x",10,
25,"L","P","f","r","r","a",,"x",10,
26,"L","P","f","r","r","r",,"x",10,
27,"L","P","a","f","f","f",,"-",11,
28,"L","P","a","f","f","a",,"-",12,
29,"L","P","a","f","f","r",,"p",12,
30,"L","P","a","f","a","f",,"-",13,
31,"L","P","a","f","a","a",,"-",14,
32,"L","P","a","f","a","r",,"p",14,
33,"L","P","a","f","r","f",,"p",14,
34,"L","P","a","f","r","a",,"p",14,
35,"L","P","a","f","r","r",,"x",14,
36,"L","P","a","a","f","f",,"-",15,
37,"L","P","a","a","f","a",,"-",16,
38,"L","P","a","a","f","r",,"p",16,
39,"L","P","a","a","a","f",,"-",17,
40,"L","P","a","a","a","a",,"-",18,"permissive"
41,"L","P","a","a","a","r",,"p",18,
42,"L","P","a","a","r","f",,"p",18,
43,"L","P","a","a","r","a",,"p",18,
44,"L","P","a","a","r","r",,"x",18,
45,"L","P","a","r","f","f",,"p",18,
46,"L","P","a","r","f","a",,"p",18,
47,"L","P","a","r","f","r",,"x",18,
48,"L","P","a","r","a","f",,"p",18,
49,"L","P","a","r","a","a",,"p",18,
50,"L","P","a","r","a","r",,"x",18,
51,"L","P","a","r","r","f",,"x",18,
52,"L","P","a","r","r","a",,"x",18,
53,"L","P","a","r","r","r",,"x",18,
54,"L","P","r","f","f","f",,"-",19,
55,"L","P","r","f","f","a",,"p",19,
56,"L","P","r","f","f","r",,"x",19,
57,"L","P","r","f","a","f",,"p",19,
58,"L","P","r","f","a","a",,"p",19,
59,"L","P","r","f","a","r",,"x",19,
60,"L","P","r","f","r","f",,"x",19,
61,"L","P","r","f","r","a",,"x",19,
62,"L","P","r","f","r","r",,"x",19,
63,"L","P","r","a","f","f",,"p",19,
64,"L","P","r","a","f","a",,"p",19,
65,"L","P","r","a","f","r",,"x",19,
66,"L","P","r","a","a","f",,"p",19,
67,"L","P","r","a","a","a",,"p",19,
68,"L","P","r","a","a","r",,"x",19,
69,"L","P","r","a","r","f",,"x",19,
70,"L","P","r","a","r","a",,"x",19,
71,"L","P","r","a","r","r",,"x",19,
72,"L","P","r","r","f","f",,"x",19,
73,"L","P","r","r","f","a",,"x",19,
74,"L","P","r","r","f","r",,"x",19,
75,"L","P","r","r","a","f",,"x",19,
76,"L","P","r","r","a","a",,"x",19,
77,"L","P","r","r","a","r",,"x",19,
78,"L","P","r","r","r","f",,"x",19,
79,"L","P","r","r","r","a",,"x",19,
80,"L","P","r","r","r","r",,"x",19,
81,"L","U","f","f","f","f",,"-",20,"final"
82,"L","U","f","f","f","a",,"-",21,
83,"L","U","f","f","f","r",,"-",22,"obligatory local unique"
84,"L","U","f","f","a","f",,"-",23,
85,"L","U","f","f","a","a",,"-",24,"currently supported by Postgresql"
86,"L","U","f","f","a","r",,"p",24,
87,"L","U","f","f","r","f",,"-",25,
88,"L","U","f","f","r","a",,"p",25,
89,"L","U","f","f","r","r",,"x",25,
90,"L","U","f","a","f","f",,"-",26,
91,"L","U","f","a","f","a",,"-",27,
92,"L","U","f","a","f","r",,"p",27,
93,"L","U","f","a","a","f",,"-",28,
94,"L","U","f","a","a","a",,"-",29,
95,"L","U","f","a","a","r",,"p",29,
96,"L","U","f","a","r","f",,"p",29,
97,"L","U","f","a","r","a",,"p",29,
98,"L","U","f","a","r","r",,"x",29,
99,"L","U","f","r","f","f",,"-",30,
100,"L","U","f","r","f","a",,"p",30,
101,"L","U","f","r","f","r",,"x",30,
102,"L","U","f","r","a","f",,"p",30,
103,"L","U","f","r","a","a",,"p",30,
104,"L","U","f","r","a","r",,"x",30,
105,"L","U","f","r","r","f",,"x",30,
106,"L","U","f","r","r","a",,"x",30,
107,"L","U","f","r","r","r",,"x",30,
108,"L","U","a","f","f","f",,"-",31,
109,"L","U","a","f","f","a",,"-",32,
110,"L","U","a","f","f","r",,"p",32,
111,"L","U","a","f","a","f",,"-",33,
112,"L","U","a","f","a","a",,"-",34,
113,"L","U","a","f","a","r",,"p",34,
114,"L","U","a","f","r","f",,"p",34,
115,"L","U","a","f","r","a",,"p",34,
116,"L","U","a","f","r","r",,"x",34,
117,"L","U","a","a","f","f",,"-",35,
118,"L","U","a","a","f","a",,"-",36,
119,"L","U","a","a","f","r",,"p",36,
120,"L","U","a","a","a","f",,"-",37,
121,"L","U","a","a","a","a",,"-",38,"permissive"
122,"L","U","a","a","a","r",,"p",38,
123,"L","U","a","a","r","f",,"p",38,
124,"L","U","a","a","r","a",,"p",38,
125,"L","U","a","a","r","r",,"x",38,
126,"L","U","a","r","f","f",,"p",38,
127,"L","U","a","r","f","a",,"p",38,
128,"L","U","a","r","f","r",,"x",38,
129,"L","U","a","r","a","f",,"p",38,
130,"L","U","a","r","a","a",,"p",38,
131,"L","U","a","r","a","r",,"x",38,
132,"L","U","a","r","r","f",,"x",38,
133,"L","U","a","r","r","a",,"x",38,
134,"L","U","a","r","r","r",,"x",38,
135,"L","U","r","f","f","f",,"-",39,
136,"L","U","r","f","f","a",,"p",39,
137,"L","U","r","f","f","r",,"x",39,
138,"L","U","r","f","a","f",,"p",39,
139,"L","U","r","f","a","a",,"p",39,
140,"L","U","r","f","a","r",,"x",39,
141,"L","U","r","f","r","f",,"x",39,
142,"L","U","r","f","r","a",,"x",39,
143,"L","U","r","f","r","r",,"x",39,
144,"L","U","r","a","f","f",,"p",39,
145,"L","U","r","a","f","a",,"p",39,
146,"L","U","r","a","f","r",,"x",39,
147,"L","U","r","a","a","f",,"p",39,
148,"L","U","r","a","a","a",,"p",39,
149,"L","U","r","a","a","r",,"x",39,
150,"L","U","r","a","r","f",,"x",39,
151,"L","U","r","a","r","a",,"x",39,
152,"L","U","r","a","r","r",,"x",39,
153,"L","U","r","r","f","f",,"x",39,
154,"L","U","r","r","f","a",,"x",39,
155,"L","U","r","r","f","r",,"x",39,
156,"L","U","r","r","a","f",,"x",39,
157,"L","U","r","r","a","a",,"x",39,
158,"L","U","r","r","a","r",,"x",39,
159,"L","U","r","r","r","f",,"x",39,
160,"L","U","r","r","r","a",,"x",39,
161,"L","U","r","r","r","r",,"x",39,
162,"C","P","f","f","f","f",,"-",40,"final"
163,"C","P","f","f","f","a",,"-",41,
164,"C","P","f","f","f","r",,"-",42,
165,"C","P","f","f","a","f",,"-",43,
166,"C","P","f","f","a","a",,"-",44,
167,"C","P","f","f","a","r",,"p",44,
168,"C","P","f","f","r","f",,"-",45,
169,"C","P","f","f","r","a",,"p",45,
170,"C","P","f","f","r","r",,"x",45,
171,"C","P","f","a","f","f",,"-",46,
172,"C","P","f","a","f","a",,"-",47,
173,"C","P","f","a","f","r",,"p",47,
174,"C","P","f","a","a","f",,"-",48,
175,"C","P","f","a","a","a",,"-",49,
176,"C","P","f","a","a","r",,"p",49,
177,"C","P","f","a","r","f",,"p",49,
178,"C","P","f","a","r","a",,"p",49,
179,"C","P","f","a","r","r",,"x",49,
180,"C","P","f","r","f","f",,"-",50,
181,"C","P","f","r","f","a",,"p",50,
182,"C","P","f","r","f","r",,"x",50,
183,"C","P","f","r","a","f",,"p",50,
184,"C","P","f","r","a","a",,"p",50,
185,"C","P","f","r","a","r",,"x",50,
186,"C","P","f","r","r","f",,"x",50,
187,"C","P","f","r","r","a",,"x",50,
188,"C","P","f","r","r","r",,"x",50,
189,"C","P","a","f","f","f",,"-",51,
190,"C","P","a","f","f","a",,"-",52,
191,"C","P","a","f","f","r",,"p",52,
192,"C","P","a","f","a","f",,"-",53,
193,"C","P","a","f","a","a",,"-",54,
194,"C","P","a","f","a","r",,"p",54,
195,"C","P","a","f","r","f",,"p",54,
196,"C","P","a","f","r","a",,"p",54,
197,"C","P","a","f","r","r",,"x",54,
198,"C","P","a","a","f","f",,"-",55,
199,"C","P","a","a","f","a",,"-",56,
200,"C","P","a","a","f","r",,"p",56,
201,"C","P","a","a","a","f",,"-",57,
202,"C","P","a","a","a","a",,"-",58,"permissive"
203,"C","P","a","a","a","r",,"p",58,
204,"C","P","a","a","r","f",,"p",58,
205,"C","P","a","a","r","a",,"p",58,
206,"C","P","a","a","r","r",,"x",58,
207,"C","P","a","r","f","f",,"p",58,
208,"C","P","a","r","f","a",,"p",58,
209,"C","P","a","r","f","r",,"x",58,
210,"C","P","a","r","a","f",,"p",58,
211,"C","P","a","r","a","a",,"p",58,
212,"C","P","a","r","a","r",,"x",58,
213,"C","P","a","r","r","f",,"x",58,
214,"C","P","a","r","r","a",,"x",58,
215,"C","P","a","r","r","r",,"x",58,
216,"C","P","r","f","f","f",,"-",59,"attribute is obligatory class-wide
plural"
217,"C","P","r","f","f","a",,"p",59,
218,"C","P","r","f","f","r",,"x",59,
219,"C","P","r","f","a","f",,"p",59,
220,"C","P","r","f","a","a",,"p",59,
221,"C","P","r","f","a","r",,"x",59,
222,"C","P","r","f","r","f",,"x",59,
223,"C","P","r","f","r","a",,"x",59,
224,"C","P","r","f","r","r",,"x",59,
225,"C","P","r","a","f","f",,"p",59,
226,"C","P","r","a","f","a",,"p",59,
227,"C","P","r","a","f","r",,"x",59,
228,"C","P","r","a","a","f",,"p",59,
229,"C","P","r","a","a","a",,"p",59,
230,"C","P","r","a","a","r",,"x",59,
231,"C","P","r","a","r","f",,"x",59,
232,"C","P","r","a","r","a",,"x",59,
233,"C","P","r","a","r","r",,"x",59,
234,"C","P","r","r","f","f",,"x",59,
235,"C","P","r","r","f","a",,"x",59,
236,"C","P","r","r","f","r",,"x",59,
237,"C","P","r","r","a","f",,"x",59,
238,"C","P","r","r","a","a",,"x",59,
239,"C","P","r","r","a","r",,"x",59,
240,"C","P","r","r","r","f",,"x",59,
241,"C","P","r","r","r","a",,"x",59,
242,"C","P","r","r","r","r",,"x",59,
243,"C","U","f","f","f","f",,"-",60,"final"
244,"C","U","f","f","f","a",,"-",61,
245,"C","U","f","f","f","r",,"-",62,
246,"C","U","f","f","a","f",,"-",63,
247,"C","U","f","f","a","a",,"-",64,
248,"C","U","f","f","a","r",,"p",64,
249,"C","U","f","f","r","f",,"-",65,
250,"C","U","f","f","r","a",,"p",65,
251,"C","U","f","f","r","r",,"x",65,
252,"C","U","f","a","f","f",,"-",66,
253,"C","U","f","a","f","a",,"-",67,
254,"C","U","f","a","f","r",,"p",67,
255,"C","U","f","a","a","f",,"-",68,
256,"C","U","f","a","a","a",,"-",69,
257,"C","U","f","a","a","r",,"p",69,
258,"C","U","f","a","r","f",,"p",69,
259,"C","U","f","a","r","a",,"p",69,
260,"C","U","f","a","r","r",,"x",69,
261,"C","U","f","r","f","f",,"-",70,"attribute is obligatory class-wide
unique!"
262,"C","U","f","r","f","a",,"p",70,
263,"C","U","f","r","f","r",,"x",70,
264,"C","U","f","r","a","f",,"p",70,
265,"C","U","f","r","a","a",,"p",70,
266,"C","U","f","r","a","r",,"x",70,
267,"C","U","f","r","r","f",,"x",70,
268,"C","U","f","r","r","a",,"x",70,
269,"C","U","f","r","r","r",,"x",70,
270,"C","U","a","f","f","f",,"-",71,
271,"C","U","a","f","f","a",,"-",72,
272,"C","U","a","f","f","r",,"p",72,
273,"C","U","a","f","a","f",,"-",73,
274,"C","U","a","f","a","a",,"-",74,
275,"C","U","a","f","a","r",,"p",74,
276,"C","U","a","f","r","f",,"p",74,
277,"C","U","a","f","r","a",,"p",74,
278,"C","U","a","f","r","r",,"x",74,
279,"C","U","a","a","f","f",,"-",75,
280,"C","U","a","a","f","a",,"-",76,
281,"C","U","a","a","f","r",,"p",76,
282,"C","U","a","a","a","f",,"-",77,
283,"C","U","a","a","a","a",,"-",78,"permissive"
284,"C","U","a","a","a","r",,"p",78,
285,"C","U","a","a","r","f",,"p",78,
286,"C","U","a","a","r","a",,"p",78,
287,"C","U","a","a","r","r",,"x",78,
288,"C","U","a","r","f","f",,"p",78,
289,"C","U","a","r","f","a",,"p",78,
290,"C","U","a","r","f","r",,"x",78,
291,"C","U","a","r","a","f",,"p",78,
292,"C","U","a","r","a","a",,"p",78,
293,"C","U","a","r","a","r",,"x",78,
294,"C","U","a","r","r","f",,"x",78,
295,"C","U","a","r","r","a",,"x",78,
296,"C","U","a","r","r","r",,"x",78,
297,"C","U","r","f","f","f",,"-",79,
298,"C","U","r","f","f","a",,"p",79,
299,"C","U","r","f","f","r",,"x",79,
300,"C","U","r","f","a","f",,"p",79,
301,"C","U","r","f","a","a",,"p",79,
302,"C","U","r","f","a","r",,"x",79,
303,"C","U","r","f","r","f",,"x",79,
304,"C","U","r","f","r","a",,"x",79,
305,"C","U","r","f","r","r",,"x",79,
306,"C","U","r","a","f","f",,"p",79,
307,"C","U","r","a","f","a",,"p",79,
308,"C","U","r","a","f","r",,"x",79,
309,"C","U","r","a","a","f",,"p",79,
310,"C","U","r","a","a","a",,"p",79,
311,"C","U","r","a","a","r",,"x",79,
312,"C","U","r","a","r","f",,"x",79,
313,"C","U","r","a","r","a",,"x",79,
314,"C","U","r","a","r","r",,"x",79,
315,"C","U","r","r","f","f",,"x",79,
316,"C","U","r","r","f","a",,"x",79,
317,"C","U","r","r","f","r",,"x",79,
318,"C","U","r","r","a","f",,"x",79,
319,"C","U","r","r","a","a",,"x",79,
320,"C","U","r","r","a","r",,"x",79,
321,"C","U","r","r","r","f",,"x",79,
322,"C","U","r","r","r","a",,"x",79,
323,"C","U","r","r","r","r",,"x",79,


Re: Inheritance Algebra

From
Karsten Hilbert
Date:
Trent,

although I cannot contribute much of anything to your line
of thought I'd encourage you to keep on with it as it'd be
highly desirable (for GNUmed at least) to have a stronger/
more encompassing inheritance solution in PostgreSQL.

Karsten,
GNUmed developer
--
GPG key ID E4071346 @ wwwkeys.pgp.net
E167 67FD A291 2BEA 73BD  4537 78B9 A9F9 E407 1346

Re: Inheritance Algebra

From
Martijn van Oosterhout
Date:
On Sun, Dec 04, 2005 at 10:59:10PM -0700, Trent Shipley wrote:
> Relational Constraint Inheritance Algebra
> With regard to class and attribute uniqueness

<snip>

It's taken a while to digest this and sorry for the delay. While I find
the ideas intreguing there is a little voice in the back of my head
asking: practical applications?

For programming, inheritance provides a way of reusing code in a way
that encapsulates changes. But I have yet to find a lot of data that
really needs this kind of encapsulation. I think one of the reason
inheritance hasn't had a lot of work done in PostgreSQL is because the
use-cases aren't compelling enough to make someone want to put the
effort in.

Indeed, most data is structured such that you have a unique key and
various attributes associated with that. What SQL excels at it joining
tables on those keys. The uniqueness or otherwise of non-key fields is
not generally important.

The only situation I've come across inheitence being truly useful would
be where you have several different "services" which are associated
with a customer but each require different services. But even then, the
inheritence would only be useful if code utilizing it is within the
backend. As soon as the data is transferred to the application, *that*
is where the inheritence hierarchy is and it no longer cares if the
inheritence is present in the database itself.

That's my 2c anyway...
--
Martijn van Oosterhout   <kleptog@svana.org>   http://svana.org/kleptog/
> Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a
> tool for doing 5% of the work and then sitting around waiting for someone
> else to do the other 95% so you can sue them.

Attachment

Re: Inheritance Algebra

From
Karsten Hilbert
Date:
On Wed, Dec 21, 2005 at 01:52:34PM +0100, Martijn van Oosterhout wrote:

> On Sun, Dec 04, 2005 at 10:59:10PM -0700, Trent Shipley wrote:
> > Relational Constraint Inheritance Algebra
> > With regard to class and attribute uniqueness
>
> It's taken a while to digest this and sorry for the delay. While I find
> the ideas intreguing there is a little voice in the back of my head
> asking: practical applications?
I would assume quite a few people would use table
inheritance in a simple way were it available in a more
convenient fashion: to transport fields, primary and foreign
keys to child tables.

In GNUmed (a medical practice application)
 http://salaam.homeunix.com/twiki/bin/view/Gnumed/WebHome
we use inheritance to make tables inherit

a) audit fields
b) common clinical fields such as a pointer to the patient

We overcome the primary/foreign key problem by a) letting
child tables have their own primary key which is quite
useful anyways and b) re-declaring foreign keys on child
tables.

While using inheritance isn't strictly necessary it is quite
convenient and makes the schema more intuitive.

There's also one major gain: since all clinical child tables
store their unstructured narrative in a field provided by
the clin_root_item parent table doing a search across the
entire narrative of the medical record is a simple query
against one table.

http://cvs.savannah.gnu.org/viewcvs/gnumed/gnumed/server/sql/?root=gnumed

(see gmAudit.sql and gmclinical.sql)

> The only situation I've come across inheitence being truly useful would
> be where you have several different "services" which are associated
> with a customer but each require different services.
Yes, this is similar to what we do.

Karsten
--
GPG key ID E4071346 @ wwwkeys.pgp.net
E167 67FD A291 2BEA 73BD  4537 78B9 A9F9 E407 1346

Re: Inheritance Algebra

From
Trent Shipley
Date:
On Wednesday 2005-12-21 07:50, Karsten Hilbert wrote:
> On Wed, Dec 21, 2005 at 01:52:34PM +0100, Martijn van Oosterhout wrote:
> > On Sun, Dec 04, 2005 at 10:59:10PM -0700, Trent Shipley wrote:
> > > Relational Constraint Inheritance Algebra
> > > With regard to class and attribute uniqueness
> >
> > It's taken a while to digest this and sorry for the delay. While I find
> > the ideas intreguing there is a little voice in the back of my head
> > asking: practical applications?
>
> I would assume quite a few people would use table
> inheritance in a simple way were it available in a more
> convenient fashion: to transport fields, primary and foreign
> keys to child tables.

I am not clear on why this sort of scenario benefits more from CREATE TABLE's
"INHERITS" clause than the "LIKE" clause (assuming that LIKE copied the
appropriate table properties).  Indeed, the recursive SELECT associated with
INHERITS might be undesirable.

If I understand you [Karsten] correctly then the really elegant way to do this
is with a "DECLARE" or
"DEFINE TABLE|INDEX|FOREIGN KEY|... definition_name (definition_clause)"

(The choice of DECLARE or DEFINE would depend on the SQL list of reserved
words.)

Then instantiate the declared object with something like:
CREATE TABLE|INDEX|... object_name USING definition_name.

Changes in definition (ALTER DEFINITION)should optionally cascade to
instantiated objects.  Use ALTER TABLE to create variant tables.  Very useful
for creating things that often get quashed and re-created, like temporary
tables and indexes.  Also very useful for things that should be uniform but
get attached to many tables, like annoying ubiquitous check constraints,
indexes, or foreign keys.

Re: Inheritance Algebra

From
Karsten Hilbert
Date:
On Thu, Dec 22, 2005 at 05:05:49PM -0700, Trent Shipley wrote:

> On Wednesday 2005-12-21 07:50, Karsten Hilbert wrote:

> > I would assume quite a few people would use table
> > inheritance in a simple way were it available in a more
> > convenient fashion: to transport fields, primary and foreign
> > keys to child tables.
>
> I am not clear on why this sort of scenario benefits more from CREATE TABLE's
> "INHERITS" clause than the "LIKE" clause
Because the inherited fields are aggregated in the parent
table.

Imagine a database:

create table narrative_base (
    narrative text
);

create table memo (
    author text default CURRENT_USER
) inherits (narrative_base);

create table ads (
    fk_campaign integer references campaigns(pk)
) inherits (narrative_base);

... more child tables

... even more child tables

Then we go on merrily inserting all sorts of stuff into the
narrative_base child tables for two years.

Now the boss asks me: "Has anyone ever written anything with
'PostgreSQL' in it in our company ?"

So I go

 select tableoid, * from narrative_base where narrative ilike '%postgresql';

et voila. I don't have to remember all the tables
potentially containing narrative and join them.

Now, if this properly transporter primary and foreign keys
to child tables I could add

    pk serial primary key

to narrative_base and be done with primary keys for all
children.

Get the drift ?

Karsten
--
GPG key ID E4071346 @ wwwkeys.pgp.net
E167 67FD A291 2BEA 73BD  4537 78B9 A9F9 E407 1346

Re: Inheritance Algebra

From
Mike Rylander
Date:
On 12/23/05, Karsten Hilbert <Karsten.Hilbert@gmx.net> wrote:
> On Thu, Dec 22, 2005 at 05:05:49PM -0700, Trent Shipley wrote:
>
> > On Wednesday 2005-12-21 07:50, Karsten Hilbert wrote:
>
> > > I would assume quite a few people would use table
> > > inheritance in a simple way were it available in a more
> > > convenient fashion: to transport fields, primary and foreign
> > > keys to child tables.
> >
> > I am not clear on why this sort of scenario benefits more from CREATE TABLE's
> > "INHERITS" clause than the "LIKE" clause
> Because the inherited fields are aggregated in the parent
> table.
>
> Imagine a database:
>
> create table narrative_base (
>         narrative text
> );
>
> create table memo (
>         author text default CURRENT_USER
> ) inherits (narrative_base);
>
> create table ads (
>         fk_campaign integer references campaigns(pk)
> ) inherits (narrative_base);
>
> ... more child tables
>
> ... even more child tables

We use something very similar to this to track user transactions
(circulation of material, billings, etc.) in our (developing) ILS
(Integrated Library System), OpenILS.  But we take it even further
with multiple levels of inheritance (simplified):

CREATE TABLE payment (
   pid serial,
   xact bigint,
   ptime timestamptz,
   pamount numeric(10,2)
);

CREATE TABLE bnm_payment ( -- "brick-n-mortar"
   accepting_user int
) INHERITS (payment);

CREATE TABLE bnm_desk_payment (
   cash_drawer_id text
) INHERITS (bnm_payment);

CREATE TABLE check_payment (
   check_number text
) INHERITS (bnm_desk_payment);

... and so on ...

>
> Then we go on merrily inserting all sorts of stuff into the
> narrative_base child tables for two years.
>
> Now the boss asks me: "Has anyone ever written anything with
> 'PostgreSQL' in it in our company ?"
>
> So I go
>
>  select tableoid, * from narrative_base where narrative ilike '%postgresql';
>
> et voila. I don't have to remember all the tables
> potentially containing narrative and join them.


Precisely.  We can report on daily payments at each of the "levels"
all the way down to payment type, or just get a total for the cash
drawers, or a grand total.  Billing line items are structured
similarly, so it's also very easy to grab a summary bill for a user
and "explode" it for a detailed view using tableoid.

>
> Now, if this properly transporter primary and foreign keys
> to child tables I could add
>
>         pk serial primary key
>
> to narrative_base and be done with primary keys for all
> children.
>
> Get the drift ?

While I originally wanted this as well, by using a serial for the
"pid" field in the root table you've essentially go that.  While
cross-table unique indexes aren't available now, I know that some
smart people are thinking about them.  Most of the time it comes up in
relation to O*'s "global indexes" on partitioned tables, and in that
sense is not of much use due to performance implications, but I think
/our/ use makes a strong case for such a beast.

That said, I believe I have a workaround that may suffice if you
absolutely require constraint enforced globally unique PKEYs.  This
example uses the pid field from the root table (that is inherited
everywhere) to track uniqueness.

CREATE TABLE payment_entities (
  id bigint primary key,
  toid oid  -- tableoid
);

CREATE FUNCTION global_unique_payment_entity RETURNS TRIGGER AS $$
  BEGIN
    BEGIN
      insert into entities (id, toid) values (NEW.pid, TG_RELID);
    EXCEPTION
      WHEN UNIQUE_VIOLATION THEN
        RAISE EXCEPTION 'Ack!  Key % already exists as a payment ID', NEW.pid;
      END;
    RETURN NEW;
  END;
$$ LANGUAGE 'plpgsql';

CREATE TRIGGER global_unique_entity_payment_trig
  BEFORE INSERT ON cash_payment
    FOR EACH ROW EXECUTE PROCEDURE global_unique_payment_entity();

CREATE TRIGGER global_unique_entity_payment_trig
  BEFORE INSERT ON check_payment
    FOR EACH ROW EXECUTE PROCEDURE global_unique_payment_entity();

CREATE TRIGGER global_unique_entity_payment_trig
  BEFORE INSERT ON credit_card_payment
    FOR EACH ROW EXECUTE PROCEDURE global_unique_payment_entity();

etc...

That doesn't cover UPDATEs of course, but that should be easy enough
to do. It does, however, give you a simple "type" lookup table if you
happen to have a pid in hand and want to know what it is.

Thoughts?

>
> Karsten
> --
> GPG key ID E4071346 @ wwwkeys.pgp.net
> E167 67FD A291 2BEA 73BD  4537 78B9 A9F9 E407 1346
>
> ---------------------------(end of broadcast)---------------------------
> TIP 5: don't forget to increase your free space map settings
>


--
Mike Rylander
mrylander@gmail.com
GPLS -- PINES Development
Database Developer
http://open-ils.org