Navigational Plans for Data Integration

Sixteenth National Conference on Artificial Intelligence (AAAI 1999), Orlando, Florida, July 18-22, 1999.
Marc Friedman, Alon Halevy, Todd Millstein
We consider the problem of building data integration systems when the data sources are webs of data, rather than sets of relations. Previous approaches to modeling data sources are inappropriate in this context because they do not capture the relationships between linked data and the need to navigate through paths in the data source in order to obtain the data. We describe a language for modeling data sources in this new context. We show that our language has the required expressive power, and that minor extensions to it would make query answering intractable. We provide a sound and complete algorithm for reformulating a user query into a query over the data sources, and we show how to create query execution plans that both query and navigate the data sources.