RSS      English

ایندکس گذاری

نیاز به یک روش سریعتر برای جستجوی مجموعه بزرگتری از اسناد است. ساده ترین راه برای جستجوی اسناد جستجوی پشت سر هم آنها و جستجوی عبارات مورد نظر است. این روش برای تعداد زیادی سند جوابگو نیست. برای جستجوی سریع در مجموعه بزرگی از اسناد، ابتدا باید آنها را به فرمتی تبدیل کنیم که امکان جستجوی سریع روی آنها فراهم باشد. این فرآیند تبدیل ایندکس گذاری نامیده می شود. ایندکس چیزی جز یک ساختار داده خاص که امکان جستجوی سریع روی آن فراهم است، نیست.

 

 

روشهای موجود برای مدیریت داده های RDF
روشهای معمول :
معماریهای زیادی برای ذخیره و پرس وجو از حجم زیادی از داده های RDF ارائه شده است از جمله FORTH RDF suit[....] که همگی از پایگاه داده رابطه ای به عنوان انبار داده استفاده کرده اند. در اکثر این سیستم ها داده های RDF ،به تعداد زیادی سه تایی تجزیه شده اند که مستقیما در جدول های رابطه ای یا جداول هش ذخیره می شوند. بنابراین پرس و جوها بر اساس سه تایی طرح می شوند(یعنی یک یا دو بخش از سه تایی نامعلوم است و جواب منابعی است که کامل کننده بخشهای حذف شده هستند) و توسط سیستم پردازش می شوند. ولی پرس و جوها بر اساس سه تایی جز روشهای معمول برای پرس وجو از داده های RDF نیستند. به همین دلیل سیستمهایی مثل jena سعی در ایجاد جدول شبه رابطه ای ویژگیها دارند که هدف گردآوری اطلاعاتی راجع به چندین ویژگی روی لیستی از subject هاست.این روش همچنین برای پرسشهایی که نمیتوانند تنها از یک جدول ویژگی استخراج شوند، نامناسب است و باید داده ها از چندین جدول ترکیب شوند. با این وجود این جداول ساختار شبه رابطه ای را روی داده های rdf شبه ساخت یافته اعمال میکنند. اعمال ساختار در جایی که واقعا ساختاری وجود ندارد منجر به نمایشهای پراکنده با مقادیر زیادی null در جداول ویژگی تشکیل یافته میشوند. و مدیریت این جداول پراکنده در مقابل جداول فشرده تر نیاز به بار محاسباتی زیادی دارد.
روشهای دیگر:
ذخیره داده های rdf بصورت گراف:
تحقیقات زیادی امکان ذخیره داده های RDF بصورت گراف را بررسی کرده اند. ولی مشکل مقیاس پذیری هنوز در این روشها حل نشده است. یک روش دیگر بر اساس مسیر داده های RDF را ذخیره میکند ولی این روش در نهایت بر اساس یک پایگاه داده رابطه ای کار میکند: آنها زیر گرافها را در جداول رابطه ای مجزا ذخیره میکنند و باز هم برای حجم زیادی از داده ها مقیاس پذیر نیست. سایر تحقیقات روی اندازه گیری شباهت در وب معنایی متمرکز شده اند و مشکل مقیاس پذیری هنوز وجود دارد.
روشهای چندین ایندکسی:
اگر داده های RDF بر اساس چندین اندیس ذخیره شوند و در عین حال اطلاعات زمینه هم ذخیره شوند، میتوان با ایجاد 6 اندیس همه ی 16 الگوی دسترسی لازم برای چهارگانه ها را پوشش داد. در این روش میتوان چهارگانه های متناظر با یک الگوی دسترسی را سریعا بازیابی کرد. این روش متمایل به پرس و جو های ساده بر اساس سه تایی است و امکان پردازش کارای پرس و جوهای پیچیده تر را نمیدهد. یک روش چند ایندکسی مشابه نیز برای چهارگانه ها پیشنهاد شده است که سه گانه های rdf را همراه با المان زمینه، بصورت چهارگانه ذخیره میکند.6 ترتیب متفاوت برای ترتیب 4 نوع نود وجود دارد طوریکه هر مجموعه ای از 1 تا 4 نود بتوانند برای یافتن یک عبارت یا مجموعه ای از عبارات استفاده شوند. هر کدام از این ترکیبها یک ایندکس مرکب را ایجاد می کنند و مستقلا شامل همه عبارات انبار rdf میشوند.در این روش از درختان AVL برای ذخیره و سازماندهی المانهای این ایندکسها استفاده شده است و هدف پاسخگویی به پرسشهای ساده بر اساس عبارت است. 6 ترتیبی که در این روش لحاظ می شوند همگی یک ترتیب چرخشی دارند و تمام 4!=24 جایگشت ممکن چهارگانه ها و 3!=6 جایگشت ممکن سه گانه ها لحاظ نشده اند. بنابراین اگر نود زمینه را لحاظ نکنیم تعداد اندیس های مورد نیاز همان سه ترتیب چرخشی {s,p,o},{p,o,s},{o,s,p} هستند. این اندیس ها یک لیست مرتب از subject های تعریف شده برای یک property خاص را نمیتوانند ارائه کنند. و بنابراین این روش نمیتواند پرسش های پیچیده را بصورت مناسب پاسخگو باشد.
روش دسته بندی افقی :
اخیرا این روش توسط
[1].D.J.Abadi,A.Marcus,S.R.Madden,and K.Hollenbach.Scalable Semantic Web Data Management using vertical partitioning . In VLDB,2007
پیشنهاد شده است. در این روش جدول سه گانه ها به n جدول 2 ستونی تجزیه میشود،برای هر ویژگی یک جدول، که n تعداد ویژگیهاست. هر جدول شامل ستونهای فاعل و مفعول است. فاعلهای چند مقداری ،فاعلهایی که برای یک ویژگی چندین مفعول دارند، توسط چندین سطر در جدول با مقادیر فاعلهای یکسان مشاهده می شوند. هر جدول بر اساس فاعل مرتب شده است و بنابراین فاعلهای خاص به سادگی قابل بازیابی هستند. برای بازیابی اطلاعات چندین ویژگی یک مجموعه از فاعلها میتوان از آن استفاده کرد.پیاده سازی با یک DBMS ستون گرا انجام شده است(این DBMS برای مورد خاص دسته بندی عمودی طراحی شده و در مقابل DBMS سطر گرا وجود دارد که در مورد فشرده سازی و کارایی کاراست.) برای پردازش مواردی که ویژگیها بصورت متغیرهایی با مقادیر مشخص هستند، مزایای زیادی دارند. در [1] پیشنهاد شده است که ستون مفعول نیز میتواند ایندکس گذاری شود (مثلا با استفاده از درخت B+ کلاستر بندی نشده) و یا اینکه یک کپی جدید از جدول ایجاد کرد که روی ستون مفعول کلاستربندی شده است. بنابراین یک روش چند ایندکسی در یک معماری ویژگی گرا برای مدیریت داده در وب معنایی ارائه شده است . در اصل این معماری برای پاسخ به پرس وجوهایی است که مقدار ویژگی مشخص است یا اینکه جستجو به یک سری ویژگی خاص محدود شده است. در حقیقت مهمترین نوآوری [1] یکپارچه سازی جدولهای دوستونی ویژگیها در یک DBMS ستون گرا است. عدم کارایی جدول ویژگیها در پرس وجوهایی که مقدار ویژگی نامشخص است یا در زمان اجرا مشخص می شود، اثبات شده است. برای اجرای پرسشهایی که مقدار ویژگی آنها مشخص نیست ، همه جدولهای 2 ستونی باید در پرسش بررسی شوند و و نتایج با هم مجتمع شوند (با عبارتهای اجتماع پیچیده یا الحاق). بررسی های انجام شده در [1]، بر اساس این فرضیه است که برای پرسشهایی که ویژگی آنها مشخص نیست ، تنها روی 28 ویژگی خاص از 221 ویژگی اجرا می شود! و این فرضیه در دنیای واقعی غیرمحتمل است. به عنوان یک مثال داده های خام جدول 1 را در نظر بگیرید که شامل اطلاعات دانشگاهی 4 فرد خاص است و همه ویژگیها برای همه فاعلها تعریف نشده اند. یک پرسش روی این مجموعه "یک فرد خاص چه روابطی با MIT دارد؟" است. یک پرسش دیگر "یافتن افرادی است که همان ارتباطی را با stanford دارند که یک فرد خاص با Yale دارد."در این پرسشها ویژگی مشخص نیست و باید اطلاعاتی راجع به چندین ویژگی را جمع آوری کرد. علاوه براین بعضی مواقع نیاز به الحاقهای پیچیده روی لیست فاعلهای مرتبط با یک مفعول خاص از طریق چندین ویژگی است. در این موارد مقید سازی نه با ویژگی و نه با فاعل است بلکه از مفعول است.
انگیزش:
پرسشهای معمول در وب معنایی ضرورتا بر اساس ویژگی نیستند بلکه در بعضی مواقع افراد بدنبال روابط بین افراد هستند و اصلا اینکه روابط از چه نوعی ممکن است باشند مشخص نشده است. روشهای ذخیره RDF، با هدف پاسخ گویی به چنین سوالاتی طراحی نشده اند. بلکه معمولا با هدف گردآوری سه تایی هایی که دارای یک ویژگی خاص هستند یا یا فاعل خاصی دارند است. در بعضی موارد کلید subject-object hash وجود دارد که برای شناسایی ویژگیها بکار میرود. بهرحال روشی برای ارائه مستقیم قابلیتهایی مثل ارائه لیست فاعلها یا ویژگیهای مربوط به یک مفعول خاص وجود ندارد. نشان خواهیم داد که چنین کاربردهای فقط خواستنی نیستند بلکه میتوان آنها را پیاده سازی کرد. برای مثال یک مجموعه از 6 اندیس همه الگوهای دسترسی که در یک rdf query ممکن است وجود داشته باشد را پوشش میدهد . بنابراین هرچند ایندکس گذاری چندگانه ممکن است برای یک جدول پیچیدگی ترکیبیاتی اایجاد کند ولی در مورد داده های RDF عملی است. در ادامه HEXASTore که یک روش برای پیاده سازی این روش ایندکس گذاری است ارائه شده است.
تعریف HEXASTORE:
راه حل جدید نباید هیچ تفاوتی بین المانهای RDF قائل شود و فاعل و مفعول و ویژگی را به یک دید نگاه کند. بنابراین هر کدام یک ایندکس خواهند داشت. علاوه براین هر ترتیبی از این سه المان مهم است. انبار داده ای که همه 6 اندیس فوق را ذخیره کند HEXASTORE نامیده می شود. هر ساختار ایندکس در hexastore پیرامون یک المان rdf است و یک الویت برای 2 المان دیگر تعریف میکند. سه گانه های RDF در دنیایی که همه چیز بر اساس property است نیستند بلکه باید سه گانه ها را بر اساس فاعل و مفعول نیز در نظر گرفت. در حالت اول برای یک فاعل خاص یک بردار ویژگیها وجود دارد و برای هر المان بردار ویژگی یک بردار از مقادیر مفعولها وجود دارد. برای یک فاعل و یک ویژگی خاص لیست مفعولها در اندیس گذاری بر اساس فاعل و در اندیس گذاری بر اساس ویژگی یکی است. بنابراین تنها یک کپی از چنین لیستهایی در معماری ایندکس ها لازم است. بنابراین در ایجاد آخرین ایندکس بر اساس مفعول برای هر فاعل خاص لیست از قبل موجود است و برای هر ویژگی خاص نیز لیست از قبل موجود است. بنابراین 6 نوع ایندکس گذاری داریم مثلا ایندکس SPo، ابتدا بر اساس فاعل دسته بندی صورت میگیرد و برای هر فاعل لیستی از ویژگیهایش داریم و برای هر ویژگی لیستی از مفعولها داریم. روش ارائه شده در [1] نوعی ایندکس گذاری بر اساس pso است. همچنین به جای ذخیره سازی کل رشته یا URI از کلید آنها استفاده میکنیم. بنابراین علاوه بر 6 اندیس با استفاده از شناسه ها ی هر المان rdf ، یک جدول نگاشت داریم که هرکلید را به المان متناظرش نگاشت میکند. همانطور که گفتیم 3 جفت از ایندکس ها در این روش 6 تایی لیست نهایی یکسانی دارند بنابراین اندیس spo,pso لیست مفعول نهایی یکسانی دارند. و ....در اصل بدترین حالت فضای اشغال شده در hexastore 6 برابر فضای لازم برای ذخیره سه گانه ها در یک جدول سه گانه نیست. به این دلیل که کلید هرکدام از منابع 2 بار در لیست اول و 2 بار در بردار و 1 بار در لیست ظاهر می شود. در بدترین حالت فرض کنید که در سه گانه ، هر تنها یکبار در دیتاست rdf آمده باشند، آنگاه کلید هر کدام از منابع 5 بار در ایندکس hexastore ظاهر می شود. بنابراین در بدترین حالت فضای hexastore پنج برابر فضای مورد نیاز برای ذخیره سازی کلیدها در جدول سه گانه هاست. در عمل فضا کمتر است چون هر المان بیشتر از یکبار در کل دیتاست ظاهر می شود.