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.
Your self-reference could introduce a hierarchy of divisions within divisions. You need code (usually a trigger) to ensure that no divisions allow this.
The original schema using encoding is broken too. You have no enforceable FK
Personally, I'd consider this with a check constraint to ensure than only one of DepartmentID and DivisionID per row is populated
Article
-------
ArticleID (PK) int NOT NULL
DepartmentID (FK) int NULL
DivisionID (FK) int NULL
ArticleName varchar(50) NOT NULL
Why?
- no code needed
- no nested divisions
- full DRI via FKs to parent table
- enforced "multiple parent, only one at a time"
You could also use computed columns to add a column that says "department" or "division"
Another way: mandate that each department has at least one division...
Best Answer
The solution I would choose depends on a few things. If the number of these columns is relatively low (and not subject of frequent changes) then I would go with the solution you suggested, ie. one table for each attribute and foreign keys on these. This way you have to define a new table and add a column for every new attribute and modify your queries accordingly.
If this is not your case than EAV suggested by @Zachariha should be considered, but it's worth reading this answer before. It is very easy to extend (just add a new row to a table) but can go very difficult to maintain - in my opinion mostly because it's hard to follow that who plays in which team.
The scenario you see in your current schema can be the result of either not normalizing data or denormalizing later in order to speed up queries. Normally, I keep heavily denormalized tables separate from base tables to keep my data safe from violations of referential integrity.