Page 179 - DCAP402_DCAO204_DATABASE MANAGEMENT SYSTEM_MANAGING DATABASE

Database Management Systems/Managing Database

Notes
Figure 10.4: Two Fixpoints for the Big/Small Program

The root of the problem is the use of not. When we apply the first rule, some inferences are
disallowed because of the presence of tuples in Small. Parts that satisfy the other conditions in
the body of the rule are candidates for addition to Big, and we remove the parts in Small from
this set of candidates. Thus, some inferences that are possible if Small is empty (as it is before the
second rule is applied) are disallowed if Small contains tuples (generated by applying the
second rule before the first rule). Here is the difficulty: If not is used, the addition of tuples to a
relation can disallow the inference of other tuples. Without not, this situation can never arise;
the addition of tuples to a relation can never disallow the inference of other tuples.

Task “Each application of a Datalog rule can be understood in terms of relational
algebra”. Discuss.

Range-Restriction and Negation

If rules are allowed to contain not in the body, the definition of range-restriction must be
extended in order to ensure that all range-restricted programs are safe. If a relation appears in
the body of a rule preceded by not, we call this a negated occurrence. Relation occurrences in the
body that are not negated are called positive occurrences. A program is range-restricted if every
variable in the head of the rule appears in some positive relation occurrence in the body.

10.4 Modeling Complex Data Semantics

Data modelling, using a specific data model type, and as a unique activity during information
system design, is commonly attributed to Charles Bachman (1969) who presented the Data
Structure Diagram as one of the first, widely used data models for network database design.
Several alternative data model types were proposed shortly thereafter, perhaps the best known
of which are shown in Figure 10.5.

172 LOVELY PROFESSIONAL UNIVERSITY