The idea where there are sub-tables in RDBMS that "inherit" the schema of the parent(s) table. Often found in the context of OODBMS products.
More specifically,
table inheritance occurs when you have a table
A that contains tuples with a certain schema. In addition, there is a second table
B containing tables with an "inherited" schema--usually one with additional attributes in the tuples. Furthermore,
A and
B are constrained such that for every element in
B, the projection of said element that excludes the extra attributes, is found in
A. When this occurs,
B is said to be a
subtable of
A.
This occurs when relations in a database are mapped to classes in an OO language (for a class with a given set of data members; there's a table whose schema defines an equivalent set of attributes), and there is a correspondence between class instances (objects) in an application and tuples in the equivalent table. When subclasses (and subclass instances) of the class appear (often adding additional data members), a corresponding relation containing instances of the subclass (and a schema matching the subclass definition) is made. But since instances of the subclass are also valid instances of the base class; every tuple in the subtable must correspond with a (sliced) tuple in the supertable.
DateAndDarwen thoroughly trash the idea in
TheThirdManifesto.
Many, perhaps most relational proponents don't find this concept very useful, generally because they believe that over the longer run variations of a concept don't really stay in a "tree shape" (
LimitsOfHierarchies). Schemas are more fragile than application OOP classes, and thus refactoring the inheritance hierarchy to deal with changes could be problematic. Unlike OOP inheritance, attributes are the preferred way to classify rows at the sub-entity level, not pedigree.
Of course, there's no reason that TableInheritance need be "tree-shaped", though certain OODBMS products and OO-relational mapping products that do it may be limited to single table inheritance. Multiple table inheritance would remove the "tree" limit.
I have never seen a proposed usage scenario for multiple schema inheritance. Single inheritance has been proposed for the Party Pattern (
ContactAndAddressModels). Generally, something that complex would be better managed via the
SetTheory built into relational rather than dealing with potentially overlapping hierarchies. Of course, this risks turning into another multi-trees versus sets
HolyWar.
What holy war? I don't know what you mean by a "multi-tree"; if you mean what I think you mean, the proper name for such a creature is a DirectedAcyclicGraph. That's what the "inheritance tree" in system with MultipleInheritance looks like. And guess-what? That's also what the "inheritance tree" in a SetTheory based type system looks like. Such a HolyWar would be a civil war, it seems.
- No no; if he is using it in a standard sense, "multi-tree" is a forest: a set of trees not connected to each other, and in particular not sharing a common root. Inheritance in languages in which everything inherits from a single root (such as Object) form trees or DAGs, but languages which do not have a single such root form forests (or sets of DAGs).
What keeps it from having cycles? Recursive definitions certainly seem possible if the compiler/interpreter does not check against it. Also, I consider sets simpler, or at least better understood, than
DirectedAcyclicGraph.
- That's like saying that addition is simpler and better understood than multiplication. You should view both things as utterly fundamental.
- No because sets can represent anything that MI can, and is not necessarily more complicated, such as doing multiplication via repeated addition. -- top
- Correct; furthermore defining multiplication in terms of addition is (in general) not possible. It happens to be true when when the algebraic ring in question is the integers; and the ring operators + and * correspond to ordinary arithmetic. Likewise for rings which are isomorphic to the integers, with a little bit of handwaving. But for arbitrary rings, defining multiplication in terms of repeated addition is nonsense.
- Just the other day I was trying to remember what the term is if * can be defined in terms of + in an algebra, versus if it can't, but nothing is coming to mind. Do you remember? It's an important distinction for some purposes other than the question of isomorphism to integers, and * = f(repeated +) can arise where there's no such isomorphism, too.
- You can always define an operation * in terms of the operation + on a set S (you just let 2*n be n+n, etc.), but unless S contains at least the positive integers, the * operation won't be a binary operation on S, nor on a subset of S.
- How to define * in terms of + was absolutely not the question. The question was what you call the one versus the other. It is also much too limited to focus on concrete entities like integers. I'm interested in more abstract domains, and in rather different concrete domains, too, such as division algebras over semigroups as generators of formal grammars, which are typically set up such that * is repeated +, and * and + are binary, but the domain does not include integers, it's over tokens and sequences thereof (see for instance John Baez's comments on http://math.ucr.edu/home/baez/week108.html, with a shorter note from me at the bottom). -- DougMerritt
- Are you saying you can define m*n, where m,n are elements of S in terms of + (another binary operation on S), where S does not contain the positive integers? Even if you did, why would you call it multiplication?
- Yes, you can, and whether a particular operator is called "multiplication" or not depends on all sorts of things, but it is in fact traditional in mathematics to refer to "multiplication" over sets that do not include integers. I am actually flabbergasted that you ask; for some reason I thought you had studied so-called "higher math". So, I don't know what your background is, and therefore don't know what else to say or what precisely to refer you to, to expand on these topics appropriately for you.
- So give a really simple example, where your * is distributive over + (but not vice versa) and has at least one other property obviously similar to some property of integer multiplication.
- Diagonal matrices. But it doesn't actually matter; we might be exploring a problem in abstract algebra where we don't yet know what sort of representation will turn out to be appropriate. That's the whole trend of mathematics, to generalize to higher and higher levels of abstractions. We might use the same algebra on a certain set of functors. It depends on what one is doing. If the algebra comes first, it doesn't necessarily matter what representations can be used.
- How is * for diagonal matrices defined in terms of + for diagonal matrices? If you have the matrix elements being integers, isn't a subset of those matrices isomorphic to the positive integers?
- One can often create a (useful) isomorphism between the integers, and the set of identity matrices of a given rank, multiplied by an integer. However, I'm not aware of any isomorphisms between the integers and arbitrary matrices, which hold under the usual properties of addition and multiplication. At any rate, abstract algebra is a very interesting (and illuminating subject)--there are many fine books on the topic. And it is a subject that has many applications in programming.
- Neither can one define * in terms of + for arbitrary matrices.
- You're confusing yourself. Skip that, and use a different example: formal (symbolic, not numeric) polynomials or power series. The algebra of adding and multiplying polynomials is essentially the same as that used for integers, but the range and domain is over symbols, not integers. (If anyone contradicts that, they are badly confused. Integers != symbols.)
- You then have symbols 1, 2, etc., which are isomorphic to the corresponding integers (at least for finite expressions).
- Uh, no. For two sets to be isomorphic with regard to some property; they have to be memberwise equivalent, other than via name. Even though the set of polynomials with integer coefficients is countable (and thus the same "size" as the set of integers), there is no isomorphism between the two which preserves the meaning of addition and multiplication. This has been proven; and the proof is the subject of undergraduate math courses. For an isomorphism to exist; one must be able to equate ALL the polynomials with ALL the integers; not just the subset of polynomials with degree zero. Not to be rude, but perhaps you might consider studying abstract algebra? I'm no expert at it (my knowledge of the topic is limited), but I do grok the basics. You seem to not know what terms like "algebraic structure", "group", "ring", "field", and "isomorphism" mean. -- sj
- I know what those terms mean. I didn't specify the set of polynomials with integer coefficients. I was referring to the subset of them containing 1, 2, 3, etc. -- by
- You wouldn't be arguing the position of a HostileStudent if you actually grokked the subject, for which I will give up on you, but a parting thought: I can require the algebra to be over the cyclotomic polynomials with constant part zero (e.g. x^5 + x^4 + x^3 + x^2 + x), in which case your tedious insistence that the integers are always a subset is clearly false; there's nothing but x's in them there polynomials, no integers (aside from the exponents, which I really hope you realize is quite aside from the point). Now go finish your HostileStudent thing in private -- or better yet, review your abstract algebra, since you insist you know it. Still better yet, read up on CategoryTheory. -- Doug
- Any set of polynomials where the constant term is always zero (I put it that way because I don't recall any such cyclotomic polynomials) leaves you unable to define * in terms of +, so it doesn't falsify what I wrote. You could do + and * "mod k", but then you simply find the integers "mod k".
- I would give you partial credit for remembering or googling and seeing that there are no cyclotomic polynomials with constant part 0 by definition, but you lose that partial credit, and more, for (a) not recognizing that the only constants that appear in cyclotomics are +1 and -1, not the integers!, and (b) for not recognizing that cyclotomic polynomials are in fact governed purely by multiplicative relationships that are isomorphic to those over integers, so that unfortunately you are incorrect, cyclotomic polynomial multiplication is trivially definable in terms of cyclotomic addition (when approached carefully... extra credit if you can recognize the necessary approach), and...
- ..and (c) for not giving me a reason to do other than give up on you as a HostileStudent who claims to know everything and is not at all fun to talk to. I still see no reason to believe that you have studied higher mathematics; you remind me of the people who claim that "irrationals don't exist". What part of "Abstract" in "AbstractAlgebra?" do you fail to understand? -- Doug
- P.S. You consistently fail to recognize the import of that last point. Why should anyone talk to you? Answer: if it might be interesting. But you do nothing but NitPick. If you in fact know anything at all, on any topic, you carefully avoid sharing your knowledge, unless you can use it to NitPick what someone else said. That sucks. That is no fun. If you want me, or anyone, to talk to you, share your knowledge (if any!), don't just NitPick us to death. Doing so is no fun at all. And since I'm tired of your NitPick'ing, and since you don't contribute beyond NitPick'ing, I'll just go away from you and talk to someone else. And maybe that's fine with you. Whatever. Who cares. -- Doug
- I didn't claim to know everything. You simply invented that because you prefer to adopt a mocking attitude. You were asked to provide a simple example, with suitable definitions of + and *, where * is distributive over + and has at least one other property obviously similar to some property of integer multiplication. It's up to you to provide the definitions, not me, so that your example is accessible to all, not just mathematicians. BTW "governed purely by multiplicative relationships" falls far short of stating how you would define * for cyclotomic polynomials. Moreover, if you managed to produce a definition of * in terms of + for some definition of +, how could the "purely by multiplicative relationships" assertion possibly be justified?
- You may be right, you may be wrong, but you are not at all fun nor interesting to talk to, and I'm not being paid to talk to you. Bye bye. (P.S. I was trying to encourage you to become interesting rather than tedious, but either that's outside of your range, or I suck at encouraging such things. Same result either way.) -- Doug
- You were trying to dismiss what I wrote as trivially and obviously wrong, using various examples which didn't seem to work, whilst peppering your replies with deliberate impoliteness, such as "you're confusing yourself... badly confused... seem to not know what terms like "algebraic structure", "group", "ring", "field" mean (none of which I'd mentioned)... hostile student... tedious... constantly fail", etc. Instead of all those unjustified AdHominem asides, you could simply have written "I'm inclined to disagree, but I can't produce and justify any simple counter-example at this time."
- However, it's not a good idea to allow cycles in inheritance relationships (NitPick: unless one introduces some mechanism to give a termination condition for the infinite recursion, and that still leaves open the question of what one is trying to accomplish by doing such a thing)
- No because sets can represent anything that MI can, and is not necessarily more complicated, such as doing multiplication via repeated addition.
Returning to the subject at hand, and ignoring the foray into AbstractAlgebra
? above, there is one problem with sets, when sets are expressed as relations (or as enumerations):
They are
finite.
Relational tables have no way of encoding infinite sets. Suppose I wanted to represent the set of all pairs of integers (we'll ignore the issue of finite-precision math). Using a struct/class definition, it's easy:
struct PairOfInts? { int x, y; };
In C/C++, this gives us two things: First, a means to
construct an arbitrary pair of ints, and second; the concept of the
type of a pair of ints - in other words, a set of which every pair of ints is a member.
{
But how do you populate the struct with your int values? You would make an array of that struct right? If you use an array then you have to populate the array, just like you have to populate the table! So I'm not understanding what your point is; can you please clarify? Also, a table could have a column type that supports two ints (a struct type) in one cell, but current databases do not have such a rich type systems.}
Switching to relational, we can easily write an equivalent schema. In SQL:
CREATE TABLE pair_of_ints
(
x INT,
y INT
)
One can create a table of that type, and populate it with as many pairs as one likes. HOWEVER, since tables are enumerated sets; only a finite number of pairs (those inserted into the table) can be so populated. The relational algebra doesn't provide a way, inductive or deductive, to build up a set with an infinite number of members.
Now, there are tools and theories to overcome this problem. The combination of relations and logic programming, wherein relations can contain ground cases for a logic language (such as Datalog), augmented with Prolog-style rules, is capable of inductively describing infinite sets. However, this is still an area of research; and certain queries in logic languages (like trying to disprove a proposition), can be dicey.
Inevitably, if you want to encode something infinite, you first devise some finite representation of it.
What would be a real world manifestation of this (alleged) gap? I want a tool that helps people get work done, not so much a better theoretical notation.
{The relational model was theoretical with a theoretical notation and helped people get work done...}
I meant a practical need to have a set with infinite members.
{I don't even understand what he is getting at with the infinite member idea, because a struct doesn't say you can have infinite members... you would have to make an ARRAY of STRUCT first, or pointers to the struct, or a list of the struct... a struct is just a single data item, not infinite. But as for finding a practical need for things, my point is that Top disses theory too much when in fact theory and practice are bridged - they are not separate like you think.}
Then show it, not just claim it. "Here's a practical scenario where lack of feature X causes real-world difficulties." If that's too much to ask, then I guess I just view the world all wrong and stupidly and am fucked in the head.
See Also:
ObjectsAreFromMarsTablesAreFromVenus,
FirstGreatBlunder,
SetsAndPolymorphism
JanuaryZeroSix