Both conventional and stratified datalog are considered. Under the extension, a datalog program may not be consistent, because a derived function symbol may evaluate to something which is not a function.
Consistency is shown to be undecidable, and is decidable in a number of restricted cases.
A syntactic restriction, pairwise consistency , is shown to guarantee consistency. There is a natural correspondence between the extended datalog introduced here, and the usual datalog with functional dependencies. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation. A Logic-Based Language for Complex Objects. Update Semantics for Incomplete Databases.