Help with a table having fixed number of self-referencing columns

Normalization is based on functional dependencies. Functional dependencies have to do with semantics; they have to do with what the data means. When you simplify a real-world problem to the level of "parent_id, child_id, date", and you don't include any sample data, you really limit how much help a conscientious database designer can give you.

The fact that you have a key {child_id, parent_id, date} in one table, and that you have (it seems) a unique pair {child_id, parent_id} in the child table doesn't necessarily mean that part of the combination is redundant. It might mean that in the table that has {child_id, parent_id, date} as the primary key, the pair of attributes {child_id, parent_id} ought to reference the child table in the first place.

If that's the case, you might use FOREIGN KEY (child_id, parent_id) REFERENCES child (child_id, parent_id). To do that, you need a UNIQUE constraint on the pair of columns (child_id, parent_id) in the table "child", which shouldn't be a problem if child_id is its primary key.

But there's no way to tell without knowing what the data means, and you're the only one in this thread who knows that. (But we'd be happy to let you explain it to us.)

As far as the original table is concerned, you seem to be saying that child_id -> parent_id. If that's the case, why is parent_id in the original table in the first place? Why isn't the key just (child_id, date), with a foreign key reference to the "child" table? It looks to me like the kind of redundancy you're talking about might be resolved by dropping the column "parent_id".

SQL DDL and sample data in the form of INSERT statements helps us help you. DDL and INSERT statements are more precise than descriptions.

Using an intermediate table is the proper way to do this. With proper indexes and good maintenance it won't hurt performance much at all.

Avoid the multi-column solution (refid1, refid2 etc.) - that's repeating groups and not properly normalised. Plus your queries will degenerate into a dog's breakfast of OR clauses and CASE statements, which will hurt performance.

You may get some benefit from subtyping your data rows so most use your current arrangement but those with multiple reference use a different one. Your queries will UNION ALL the two sets to get the total. I really doubt the overhead from this will compensate for the mostly-redundant join to data_reference.

The subtyped schema would look like this:

create table data (
    id int identity not null,
    ref int not null,       -- set to a standard value for rows with >1 reference.
    is_single_reference bit not null
);

create table reference (
    refid int not null
);

create table data_reference (
     dataid int not null,
     refid int not null
);

The query would be something like:

select
    <whatever>
from data as d
inner join reference as r
    on d.ref = r.refid
where d.is_single_reference = 1

union all

select
    <whatever>
from data as d
inner join data_reference as dr
    on dr.dataid= d.id
inner join reference as r
    on r.refid = dr.refid
where d.is_single_reference = 0;

This is fairly ugly. You'd be lucky to avoid two scans of data. Ideally you'd want filtered indexes but IIRC these aren't availble until SQL Server 2008. The applicaiton would have to know how many reference rows there were per data, set flags accordingly and maintain those if the number changed. Just use the n:m approach.