پاسخگویی دسته جمعی تحت شرایط نقشه برداریهای الگوی نامعین

پاسخگویی دسته جمعی تحت شرایط نقشه برداریهای الگوی نامعین

پاسخگویی دسته جمعی تحت شرایط نقشه برداریهای الگوی نامعین

حجم فایل : ۴۵۱KB

تعداد صفحه : ۱۲ صفحه

فرمت فایل : PDF

قیمت فایل : رایگان

در صورت دانلود فایل ترجمه اینجا کلیک کنید.

پاسخگویی دسته جمعی تحت شرایط نقشه برداریهای الگوی نامعین

Aggregate Query Answering under Uncertain
Schema Mappings

Abstract

Recent interest in managing uncertainty in data integration has led to the introduction of probabilistic schema mappings and the use of probabilistic methods to answer queries across multiple databases using two semantics: by-table and bytuple. In this paper, we develop three possible semantics for aggregate queries: the range, distribution, and expected value semantics, and show that these three semantics combine with the by-table and by-tuple semantics in six ways.We present algorithms to process COUNT, AVG, SUM, MIN, and MAX queries under all six semantics and develop results on the complexity of processing such queries under all six semantics.

We show that computing COUNT is in PTIME for all six semantics and computing SUM is in PTIME for all but the by-tuple/distribution semantics. Finally, we show that AVG, MIN, and MAX are PTIME computable for all by-table semantics and for the by-tuple/range semantics.We developed a prototype implementation and experimented with both real-world traces and simulated data. We show that, as expected, naive processing of aggregates does not scale beyond small databases with a small number of mappings. The results also show that the polynomial time algorithms are scalable
up to several million tuples as well as with a large number of mappings.

I. INTRODUCTION

There has been intense work during the last few years on schema matching in order to answer queries over multiple databases [1], [2], [3], [4], [5], [6], [7], [8], [9], [10]. More recently, there has been a realization that methods to automatically match schemas are uncertain — when an algorithm for
schema matching is executed, it might say that there are many possible mappings between one schema and another, and that a probability distribution over this set of mappings specifies the
probability that a specific mapping is the correct one [11].

پاسخگویی دسته جمعی تحت شرایط نقشه برداریهای الگوی نامعین