Methods and apparatus for propagating functional dependencies with conditions

A system for computing propagation covers of conditional functional dependencies using an SPC view of a dataset, wherein said SPC view comprises one or more of selection, projection and Cartesian product (SPC) operations, comprising:

• a memory;
• and at least one processor, coupled to the memory, operative to:
• obtain a plurality of said conditional functional dependencies defined over a schema for said dataset, wherein said conditional functional dependencies comprise one or more constraints that data in said SPC view must satisfy;
• process one or more of said selection operations in said SPC view to extract one or more equivalence classes;
• process one or more of said Cartesian product operations in said SPC view to obtain a renamed set of said plurality of conditional functional dependencies, wherein said renamed set comprise conditional functional dependencies having attributes appearing in said SPC view;
• apply one or more domain constraints from said one or more equivalence classes to said renamed set to remove one or more attributes not in said SPC view;
• process one or more of said projection operations in said SPC view using a reduction by resolution procedure to identify one or more inferences that is propagated to said SPC view from said one or more conditional functional dependencies having attributes that do not appear in said SPC view;
• convert one or more domain constraints of said equivalence classes to conditional functional dependencies;
• and
• determine a cover of said SPC view, wherein said cover comprises a set of conditional functional dependencies propagated from a set of said obtained conditional functional dependencies using said SPC view.

An article of manufacture for computing propagation covers of conditional functional dependencies using an SPC view of a dataset, wherein said SPC view comprises one or more of selection, projection and Cartesian product (SPC) operations, comprising a non-transitory computer-readable storage medium containing one or more programs which when executed implement the steps of:

• obtaining a plurality of said conditional functional dependencies defined over a schema for said dataset, wherein said conditional functional dependencies comprise one or more constraints that data in said SPC view must satisfy;
• processing one or more of said selection operations in said SPC view to extract one or more equivalence classes;
• processing one or more of said Cartesian product operations in said SPC view to obtain a renamed set of said plurality of conditional functional dependencies, wherein said renamed set comprise conditional functional dependencies having attributes appearing in said SPC view;
• applying one or more domain constraints from said one or more equivalence classes to said renamed set to remove one or more attributes not in said SPC view;
• processing one or more of said projection operations in said SPC view using a reduction by resolution procedure to identify one or more inferences that is propagated to said SPC view from said one or more conditional functional dependencies having attributes that do not appear in said SPC view;
• converting one or more domain constraints of said equivalence classes to conditional functional dependencies;
• and
• determining a cover of said SPC view, wherein said cover comprises a set of conditional functional dependencies propagated from a set of said obtained conditional functional dependencies using said SPC view.