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

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

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

حجم فایل : ۸۰۵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.

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

چکیده

توجه اخیر به مدیریت ابهام و عدم قطعیت در یکپارچه سازی دیتا منجر به عرضه نقشه برداریهای الگوی احتمالی گردیده تا بتوان به جستجوهای انجام شده در میان چندین بانک اطلاعاتی با استفاده از دو تکنیک جدولی و مجموعه ای از داده های تشکیل دهنده یک رکورد در بانک اطلاعاتی (چند تایی ها)، پاسخ داد. در این مقاله ما سه روش معنایی احتمالی را برای جستجوهای دسته جمعی و گروهی توسعه می دهیم که عبارتند از روشهای معنای ارزش مورد انتظار، توزیع و دامنه و نشان می دهیم که این سه روش به شش طریق با تکنیکهای جدول و مجموعه متغیرها یا داده های چند تایی ترکیب می گردند. الگوریتمهایی را برای پردازش جستجوهای COUNT, AVG, SUM, MIN, MAX تحت تمامی این شرایط معنایی ارائه خواهیم کرد و نتایج را براساس پیچیدگی پردازش چنین جُستارهایی در تمامی این شش شرایط توسعه می دهیم.

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

نشان می دهیم که محاسبه COUNT برای هر شش روش معناشناسی، در PTIME قرار دارد و محاسبه SUM نیز برای همه شش روش معناشناسی بجز معناشناسی توزیعی/ چندتایی در PTIME قرار دارد. در نهایت نشان می دهیم که AVG, MIN, MAX هم PTIME قابل محاسبه برای تمامی روشهای معناشناسی براساس جدول و برای همه روشهای معناشناسی مبتنی بر چندتایی و یا دامنه  می باشد.

یک الگوی اولیه از اجرا را توسعه داده ایم و آن را با استفاده از هر دوی آثار دنیای واقعی و داده های شبیه سازی شده تست کرده ایم. نشان می دهیم که طبق انتظار پردازش خام توده های انبوه در مقیاسی فراتر از پایگاههای دیتای کوچک با تعداد کمی نقشه برداری نمی باشد. نتایج همچنین نشان می دهند که الگوریتمهای زمانی چند جمله ای را می توان تا چند میلیون چندتایی مقیاس بندی کرد و از تعداد زیادی نقشه برداری (مسیردهی) استفاده نمود.