Pages

Thursday, March 17, 2011

Evaluating The DBQ Formulae

Our algorithm for evaluating DBQ formulae will not actually provide truth values directly for a formula, but will produce a set of substitutions reflecting possible values for variables appearing in the formula that yield true propositions. It is simplest to see this for formulae of the first type (involving simple predicates). Imagine that we have a database about car parts which includes information about which firms supply which parts. We will assume that a relation supplies is represented in the database by a long list of entries specifying exhaustively who supplies what, as follows:
Who            What

smith_corp     radiators

jones_inc      spark_plugs

morgan_bros    radiators

jones_inc      batteries

smith_corp     tyres

morgan_bros    pumps

Questions about this relation can be phrased in DBQ by using the predicate supplies. We will use the first (arg0) argument position associated with supplies to indicate the supplying firm and the second (arg1) position to indicate the type of part. Then, the following are possible DBQ formulae involving this relation:

(supplies _x radiators)

(supplies _x _y)
The result of evaluating the first of these formulae will be the set of possible values for _x which would result in the formula matching something in the database. So what we get is:
(((_x smith_corp))

((_x morgan_bros)))
The result of evaluating the second of the formulae will be the set of pairs of values for _x and _y that result in the formula matching something in the database.

No comments:

Post a Comment