Extending datalog for federated databases

In this thesis I propose a model for querying federated databases within the datalog tradition. The proposed system encodes the information in the local databases of the federation using a first order rule syntax ${\cal L}\sb\*$. I assign a logical semantics to ${\cal L}\sb\*$ via a specialized model theory which incorporates assumptions appropriate to the database context, such as the unique name assumption, but does not include assumptions inappropriate to the federated database context, such as an open or closed world assumption. The questions of interdatabase consistency and the correctness of an answer to a query are then identified with a logical inference problem defined over ${\cal L}\sb\*$. The range of answers generated by the system include the possibilities of open and closed world answers but also include a wide range of partial information alternatives in between these two extremes. The solution to the inference problem generalizes the relational algebra and datalog under the program completion semantics and is tractable in a technical sense. The language of rules provides a basis for a deductive federated query language F scED