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.