This research is developing languages and mechanisms for restructuring and merging information from disparate databases, and is studying the theoretical foundations of such languages.The research uses the PI's formally defined ILOG languages, which permit the declarative specification of database restructuring. Certain technical properties of these languagesprovide a strong connection to logic programming. The research is also developing extensions to ILOG for data merging; a central problem here involves determining when object identifiers (OIDs) in two or more distinct databases refer to the same object "in the world", and developing appropriate mechanisms for "merging" the OIDs in this case. Specific theoretical questions under study include: attempting to characterize when two (restructuring or merging) programs are equivalent; exploring algebraic properties of programs (e.g., associativity, distributivity);developing algorithms for the translation of queries against restructured, merged databases; and for incrementally updating such databases if they are materialized. Experimental work will be performed to test the algorithms and view update methodologiesunder realistic conditions. The results obtained by the researchwill provide a crucial component for all database applications which involve data sharing.
