Heterogeneous ordered list of value

Question

I have the following object model:

class A {
    List<Thing> orderedListOfThings;
}

interface Thing {        
}
class X implements Thing {
   int attr;
}
class Y implements Thing {
   String value;
}
class Z implements Thing {
   B b;
}
class B {
   ...
}

The order of the list orderedListOfThings must be preserved. This list can contains X, Y, Z instances. There isn't other Thing implementations.

1. how this model could be design in a relational database ?

2. Is there any No-SQL database (key-value, columnar, graph, triple store) that fits better for this kind of model ?

Answer 1

As others have mentioned, this can be done rather easily via a SubClass / Inheritance model. I would advocate something closer to what Pieter Geerkens suggested than what VDohnal suggested as I prefer not having lots of NULL fields per row, depending on the "type" that the row represents (i.e. the [Value] field has to be NULL on an X row as X does not have that property, Y does but does not have the [attr] field so [attr] has to be NULL on rows representing Y objects). I just feel that is harder to maintain over time as someone needs to be VERY familiar with the app layer object model to know if the NULL field is a valid data point for that row or to be ignored for that row. Even if you have CHECK constraints to enforce NULL, that is yet something else to maintain as you add properties to objects over time and it is still not easily visible when writing queries against these tables. Please note that the issue, in the past, would have also been a needless waste of space related to fixed-length data types at the data layer, but that has been mostly alleviated by the SPARSE option which was introduced in SQL Server 2008 (well, assuming you are using SQL Server).

Notes:

• The essential aspect of this model is that the [Thing] table is the "base" table for your "Thing" object.
• The [Thing] table has a [ThingType_ID] field which is not a functional requirement but is a data-dictionary / lookup-table so that you can associate meaningful information for people doing ad hoc queries or reports, etc. It also helps to determine in which subclass table to look for the extension properties, assuming there is a reason why you don't already know and are first looking in the [Thing] table for general info.
• The [Thing] table has a [A_ID] field which is an FK back to the [A] table. This maps to your structure of having an A class that contains a collection of Thing.
• The subclass tables of [ThingX], [ThingY], and [ThingZ] have the same PK as the base class table [Thing] (i.e. [Thing_ID]). The reason to not have separate IDENTITY values is that the subclass tables are not an entity by themselves but are merely an extension of the base [Thing]. Their identity IS the identity (the concept of identity, not the SQL keyword IDENTITY) of [Thing].
• Going along with the prior point, the PK field of the subclass tables [ThingX], [ThingY], and [ThingZ] is also an FK back to the [Thing] table.
• There is no need for a separate [B] table as those properties are all 1 to 1 with the definition of the [ThingZ] class / sub-table.
• All 4 of the base-class and sub-class tables have a [ModifiedDate] audit field as it is possible to update the properties of either the base [Thing] table OR a subclass table but not both in the same operation (e.g. updating the [ThingX].[Attr] field doesn't require updating the [Thing] table).
• Only the base class table--[Thing]--has the [CreatedDate] audit field because rows in the subclass tables cannot be created independently (because it is only the combination of the [Thing] table and one of the subclass tables that make up an object). I suppose it is possible to create a row in the [Thing] table only (i.e. no INSERT into any subclass tables) and later come back to INSERT into one of the subclass tables, but that is just silly ;-).

Example SQL using Microsoft T-SQL syntax (but no features highly-specific to SQL Server):

CREATE TABLE A
(
   A_ID  INT NOT NULL IDENTITY(1, 1) PRIMARY KEY,
   -- other fields?
   CreatedDate DATETIME NOT NULL DEFAULT (GETUTCDATE()),
   ModifiedDate DATETIME NULL
);

CREATE TABLE ThingType
(
   ThingType_ID TINYINT NOT NULL PRIMARY KEY,
   ThingType NVARCHAR(100) NOT NULL
);

CREATE TABLE Thing
(
   Thing_ID INT NOT NULL IDENTITY(1, 1) PRIMARY KEY,
   ThingType_ID TINYINT NOT NULL REFERENCES ThingType (ThingType_ID), -- FK to ThingType
   A_ID INT NOT NULL REFERENCES A (A_ID), -- FK to A
   -- other fields?
   CreatedDate DATETIME NOT NULL DEFAULT (GETUTCDATE()),
   ModifiedDate DATETIME NULL
);

CREATE TABLE ThingX
(
   Thing_ID INT NOT NULL PRIMARY KEY REFERENCES Thing (Thing_ID), -- FK to Thing
   Attr INT,
   -- other fields?
   ModifiedDate DATETIME NULL
);

CREATE TABLE ThingY
(
   Thing_ID INT NOT NULL PRIMARY KEY REFERENCES Thing (Thing_ID), -- FK to Thing
   Value NVARCHAR(500),
   -- other fields?
   ModifiedDate DATETIME NULL
);

CREATE TABLE ThingZ
(
   Thing_ID INT NOT NULL PRIMARY KEY REFERENCES Thing (Thing_ID), -- FK to Thing
   Something DATETIME,
   -- other fields?
   ModifiedDate DATETIME NULL
);

Side Notes:
Just to be clear about differences between this suggestion and Pieter's (since they are very similar):

1. I have no Table Type for [B] as I don't see a need for it
2. My interpretation of your structure (i.e. class A having List<Thing>) is such that both of the other answers have misconstrued that relationship:
   1. Pieter's does not allow for having singular (i.e. non-repeated) properties of A while at the same time having multiple instances of Thing.
   2. VDohnal's has the relationship backwards such that a single Thing will have multiple A s. (this has since been corrected).

3. On a practical level, I cannot see a case for doing the LEFT JOIN query at the bottom of Pieter's answer, but maybe on occasion there is. In such a case I have opted instead to query each type individually via INNER JOIN and then combining via UNION ALL (fields in one table that aren't in the other subclass table(s) need to be given literal values):

    SELECT base.field, subclass.field, subclass.[Attr]
    FROM [Thing] base
    INNER JOIN [ThingX] subclass
            ON subclass.Thing_ID = base.Thing_ID
    UNION ALL  
    SELECT base.field, subclass.field, CONVERT(INT, NULL) AS [Attr]
    FROM [Thing] base
    INNER JOIN [ThingY] subclass
            ON subclass.Thing_ID = base.Thing_ID
   

EDIT:
Here are two more notes that I thought of:

• One benefit of this broken out design, as opposed to the single table model, is that it allows for parts of the object model to change (as business needs change over time) without impacting the parts that aren't changing. For example, adding a new property to the X object does not impact either of the [ThingY] or [ThingZ] tables nor the queries that make use of [ThingY] and [ThingZ].
• For simplicity of getting data that represents the full X, Y, or Z objects, you can create Views that are a simple CREATE VIEW [X] AS SELECT * FROM [Thing] base INNER JOIN [ThingX] sub ON base.Thing_ID = sub.Thing_ID and so on for the Y and Z objects.

EDIT 2:
Renamed the [X], [Y], and [Z] tables to be [ThingX], [ThingY], and [ThingZ] respectively. This naming convention for the subclass tables is more representative of them being extensions and not complete objects / entities by themselves. This should also make the model (and working with the tables) conceptually clearer in that [X] (the View suggested directly above) = [Thing] + [ThingX], and so on with [Y] and [Z].

Also, the tables will be grouped together in SSMS, queries against sys.tables / sys.objects / INFORMATION_SCHEMA.TABLES and hopefully in your source control system where you have individual SQL scripts for each table :-).

Answer 2

This type of structure is termed a Sub-Type relationship and is usually built in an RDBMS thus (using SQL Server T_SQL syntax):

create type B as table (
    StringValue    varchar(max)  not null,
    IntValue       int           not null,
    FloatValue     float         not null
);

create table ThingTypes (
    ThingCode      varchar(6)    not null primary key
);
insert ThingTypes(ThingCode) 
values ('X'),('Y'),('Z');

create table A (
    ID        int identity not null primary key,
    TypeCode  varchar(6)   not null references ThingTypes (ThingCode)
);

create table X (
    A_ID      int    not null references A(ID),
    Value     int    not null
);
create table Y (
    A_ID      int          not null references A(ID),
    Value     varchar(max) not null
);
create table Z (
    A_ID           int           not null references A(ID),
    StringValue    varchar(max)  not null,
    IntValue       int           not null,
    FloatValue     float         not null
);

select 
    a.*,
    x.Value         as X_Value,
    y.Value         as Y_Value,
    Z.StringValue   as Z_StringValue,
    Z.FloatValue    as Z_FloatValue,
    Z.IntValue      as Z_IntValue

from dbo.A
left join dbo.X  on x.A_ID = a.ID
left join dbo.Y  on y.A_ID = a.ID
left join dbo.Z  on z.A_ID = a.ID

The polymorphism is not directly supported but can be worked around for the most part.

Answer 3

Your problem can be modelled in UML - see the picture bellow... (I have made few edits inspired by srutzky's answer to show where the UML composition should be)

The class TypeOfThing is optional but it is a good habit to include it. It basicaly enables you to distinguish the type of Thing in a collection. The SerialNo attribute represents the order of Things in the collection in Class A.

There are several ways how to implement this model in SQL relational database. One of them showed Pieter Geerkens in his answer - to create a table for every particular class X, Y and Z.

There is also another option - to create a table that mixes the classes X, Y and Z together. Here is the database diagram:

And here is the code in SQL Server t-sql. Mark that optional fields are nullable - e.g. the class X stored in the table Things will allways have the field [value] = NULL. The table/class AItem in this model encapsulates only the functionality of ordered list, as you required.

CREATE TABLE [dbo].[TypeOfThing](
    [TypeOfThingID] [int] NOT NULL,
    [TypeOfThing] [nvarchar](50) NOT NULL,
 CONSTRAINT [PK_TypeOfThing] PRIMARY KEY CLUSTERED 
(
    [TypeOfThingID] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]

CREATE TABLE [dbo].[B](
    [BId] [int] NOT NULL,
 CONSTRAINT [PK_B] PRIMARY KEY CLUSTERED 
(
    [BId] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]


CREATE TABLE [dbo].[A](
    [AId] [int] NOT NULL,
    [AName] [nvarchar](50) NOT NULL,
 CONSTRAINT [PK_A] PRIMARY KEY CLUSTERED 
(
    [AId] ASC
) WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]

CREATE TABLE [dbo].[AItem](
    [AItemId] [int] NOT NULL,
    [AId] [int] NOT NULL,
    [ThingID] [int] NOT NULL,
    [SerialNo] [int] NOT NULL,
 CONSTRAINT [PK_AItem] PRIMARY KEY CLUSTERED 
(
    [AItemId] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]

ALTER TABLE [dbo].[AItem]  WITH CHECK ADD  CONSTRAINT [FK_A_Things] FOREIGN KEY([ThingID])
REFERENCES [dbo].[Thing] ([ThingId])

ALTER TABLE [dbo].[AItem] CHECK CONSTRAINT [FK_A_Things]

ALTER TABLE [dbo].[AItem]  WITH CHECK ADD  CONSTRAINT [FK_AItem_A] FOREIGN KEY([AId])
REFERENCES [dbo].[A] ([AId])

ALTER TABLE [dbo].[AItem] CHECK CONSTRAINT [FK_AItem_A]

CREATE TABLE [dbo].[Thing](
    [ThingId] [int] NOT NULL,
    [TypeOfThingId] [int] NOT NULL,
 -- OR ThingCode char(1) NOT NULL,
    [Attr] [int] NULL,
    [Value] [nvarchar](100) NULL,
    [BId] [int] NULL,
 CONSTRAINT [PK_Things] PRIMARY KEY CLUSTERED 
(
    [ThingId] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]

ALTER TABLE [dbo].[Thing]  WITH CHECK ADD  CONSTRAINT [FK_Things_B] FOREIGN KEY([BId])
REFERENCES [dbo].[B] ([BId])

ALTER TABLE [dbo].[Thing] CHECK CONSTRAINT [FK_Things_B]

ALTER TABLE [dbo].[Thing]  WITH CHECK ADD  CONSTRAINT [FK_Things_TypeOfThing] FOREIGN KEY([TypeOfThingId])
REFERENCES [dbo].[TypeOfThing] ([TypeOfThingID])

ALTER TABLE [dbo].[Thing] CHECK CONSTRAINT [FK_Things_TypeOfThing]

You can replace the table TypeOfThing with just one TypeOfThing char(1) NOT NULL column in the table Things, that would allways contain either 'X', 'Y' or 'Z' - this could be for example ensured using check constrains.

This approach is called Single table inheritance, see: http://www.martinfowler.com/eaaCatalog/singleTableInheritance.html This approach is useful when your inherited classes have many attributes (columns, properties...) in common and there is only relatively small difference between them.

Peter's answer copies the approach called Concrete table inheritance http://www.martinfowler.com/eaaCatalog/concreteTableInheritance.html. There is also Class table inheritance which is something between them.

The select to get the ordered list of things contained in A class would be like this:

SELECT * FROM A 
INNER JOIN AItem  ON A.AId=AItem.AId 
INNER JOIN Thing ON AItem.ThingID=Thing.ThingId
INNER JOIN TypeOfThing ON Thing.TypeOfThingId=TypeOfThing.TypeOfThingId
WHERE A.AName = 'Some instance of class A'
ORDER BY AItem.SerialNo ASC

This is quite common problem and usually this is not the reason to look for another non-relational type of database - this is my answer to the question 2.