Inheritance Algebra - Mailing list pgsql-general

[
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,