توضیحات

بهینه سازی زبان یکپارچه ساز بر روی شبکه اطلاعاتی ناهمگون

چکیده
امروزه XML به یکی از قالب‌های مهم برای ذخیره و تبادل داده‌ها تبدیل شده است. انعطاف ساختار XML موجب گسترش استفاده از آن گردیده و حجم اسناد XML روز به روز در حال افزایش است. در نتیجه به منظور مدیریت اسناد XML نیاز به یک سیستم مدیریت جامع می‌باشد؛ زیرا سیستم مدیریت فایلی توانایی مدیریت چنین حجمی از داده‌ها را ندارد. با رشد چشمگیر این پایگاه‌های ‌داده نیاز به تسریع در عملیات اجرای کوئریها حس میشود.

بیشتر محققان به این جنبه XML پرداخته‌اند و روشهای زیادی در این زمینه ارائه شده است. اما از آن‌جایی که ساختار XML با ساختار رابطهای قدیمی بسیار متفاوت است، اصولا این روشها ناکارآمد هستند و به‌صورت یک استاندارد پذیرفته نشده‌اند، از این رو تلاش محققان برای حل این مشکل دو چندان

شده است. تاکنون روش‌های زیادی برای حل این مشکل در دنیای XML ارائه شده‌اند، اما هر روش تنها به جنبه‌ای از نواقص پرداخته و تنها برای دسته کوچکی از کوئریها کارایی دارد در نتیجه برای قسمت عمده کوئری‌ها ناکارامد است. در نتیجه هنوز روش خاصی به عنوان یک استاندارد، مانند SQL در

پایگاه داده‌های رابطه‌ای سنتی، وجود ندارد و می توان گفت هنوز استفاده از XML به مرحله بلوغ و بهره‌برداری کامل نرسیده است.

دراین پایان نامه ما به دنبال روشی هستیم که برای دسته بزرگی از کوئریها کارایی لازم را داشته باشد. روشی که در مقایسه با روش‌های مشابه تعداد گره‌های کمتری را مورد دستیابی قرار داده و در زمان کمتری به پاسخ برسد. روشی که قابلیت تلفیق با شاخص‌ روش‌های مشابه را داشته و بتواند از

آن‌ها برای تسریع کوئریها استفاده نماید. ما به دنبال روشی هستیم که قابلیت پرش از روی گره‌های بی‌فایده را داشته باشد و داده‌های میانی کمتری در مقایسه با روش‌های مشابه تولید نماید. روشی که با استفاده از یک راهنمای تطابق الگو، به طور مستقیم و کورکورانه به پردازش گره‌ها در سند نپردازد.

 ۱۳۰صفحه فایل ورد (Word) فونت ۱۴ منابع دارد

پس از پرداخت آنلاین میتوانید فایل کامل بهینه سازی زبان یکپارچه ساز بر روی شبکه اطلاعاتی ناهمگون را دانلود کنید

مقدمه
۱ مفاهیم پایه ۱
۱-۱ XML چیست ۲
۱-۱-۱ معرفی اجزاء اصلی XML 3
۱-۱-۲ مدل درختی XML 3 1-1-3 مفهوم شما در XML 5
۱-۱-۴ انواع زبان‌های کوئری در XML 6
۱-۲ رابطه XML و پایگاه داده‌ها ۶
۱-۳ پایگاه‌داده‌های مبتنی بر XML‌ ۷
۱-۴ پایگاه‌داده‌های پشتیبان XML 7
۱-۵ مقدمه ای بر نحوه پردازش پرس وجوها ۸
۲ مروری بر کارهای انجام شده ۱۰
۲-۱ روش حلقه های تودرتو ۱۲
۲-۲ روش Structural Join 13
۲-۳ روش StairCase Join 17
۲-۴ روش Holistic Twig Join 21
۲-۵ روش TJFast 29
۲-۶ روشهایی مبتنی بر شاخصهای مسیری ۳۱

بهینه سازی زبان یکپارچه ساز بر روی شبکه اطلاعاتی ناهمگون

۲-۷ کاستی‌های موجود در روش‌های پردازش کوئری ۳۴
۳ روش پیشنهادی ۳۹
۳-۱ طرح مسئله ۴۰
۳-۲ روش‌ شماره گذاری سند ۴۰
۳-۳ مدل سه مرحله طرح جدول شاخص ۴۲
۳-۳-۱ راهنمای پرس وجو ۴۴
۳-۳-۲ انتخاب شاخص مسیری ۴۵
۳-۳-۳ نقطه اتصال ۴۶
۳-۳-۴ تجزیه پرس وجو ۴۷
۳-۳-۵ مرحله اول: اجرای کوئری بر روی راهنمای تطابق الگو ۴۸
۳-۳-۶ مرحله دوم: تولید جدول شاخص ۴۹
۳-۳-۷ مرحله سوم: تولید نتایج نهایی ۵۲
۳-۴ کاربرد جدول شاخص در کوئریهای پیچیده ۵۵
۳-۴-۱ نقاط اتصالی با بیش از دو زیر شاخه ۵۵
۳-۴-۲ کوئریهایی با بیش از دو نقطه اتصال ۵۷
۳-۴-۳ کوئریهایی با عملگرهای مختلف ۶۰
۳-۵ نمایش سمبولیک جدول شاخص ۶۰

بهینه سازی زبان یکپارچه ساز بر روی شبکه اطلاعاتی ناهمگون

۳-۶ بهینه سازی جدول شاخص از روی شمای سند ۶۱
۳-۷ ارزیابی روش جدول شاخص ۶۴
۳-۸ توسعه روش جدول شاخص ۶۶
۳-۸-۱ کاربرد روش در پاسخ به عملگرهای نقیض ۶۶
۳-۸-۲ کاربرد جدول شاخص در پرش از روی گرههای بیفایده ۷۷
۳-۸-۳ کاربرد جدول شاخص روی برگهای شاخص شده ۸۵
۴ پیاده سازی و ارزیابی ۱۰۲
۴-۱ محیط پیاده سازی و معیارهای مقایسه ۱۰۳
۴-۲ مقایسه با روشهای مشابه ۱۰۶
۵ نتیجه گیری و کارهای آینده ۱۲۸
۵-۱ نتیجه گیری ۱۲۹
۵-۲ کارهای آینده ۱۳۰
منابع ۱۳۲

شکل ۱-۱) ساختار درختی یک سند ۱۲
شکل۱-۲) یک نمونه TPQ 17
شکل ۱-۳) نمونه‌ای از یک سند داده ۱۸
شکل۲-۱) مقایسه دو لیست برای پی بردن به رابطه مابین گره‌‌ها ۲۳
شکل ۲-۲) نحوه شماره گذاری درخت ۲۴
شکل۲-۳) شبه کد الگوریتم Tree- Merge-Anc 25
شکل ۲-۴) روش شماره گذاری پسوندی و پیشوندی ۲۸
شکل ۲-۵) پیوند پلکانی ۲۹
شکل ۲-۶) روش شماره گذاری در TJFast 30
شکل ۲-۷) یک نمونه FST 31
شکل ۳-۱)نمونه‌ای از کد گذاری Dewey 41
شکل ۳-۲) روش سه مرحله ای جدول شاخص ۴۳
شکل ۳-۳) یک نمونه نقطه اتصال ۴۶
شکل ۳-۴) یک نمونه جدول شاخص ۵۰
شکل ۳-۵) مراحل حذف پیچیدگی پرس وجوهای چند شاخهای ۵۸
شکل ۳-۶) یک نمونه IT_Model 58
شکل ۳-۷) یک نمونه از نقطه استخراج ۶۲
شکل ۳-۸) عملگر AND میان گره‌های یک نمونه TPQ 67
شکل ۳-۹) یک نمونه عملگر NOT 67
شکل ۳-۱۰) یک نمونه کوئریی دو شاخهایQ4 72

بهینه سازی زبان یکپارچه ساز بر روی شبکه اطلاعاتی ناهمگون

شکل ۳-۱۱) عملگر NOT در کوئری‌های دو شاخه ای ۷۳
شکل ۳-۱۲) حذف داده‌ها در کوئریهای دوشاخه‌ای با عملگر NOT 76
شکل ۴-۱) تعداد گره‌های خوانده شده ۱۱۰
شکل ۴-۲) مقدار فضای برده شده در حافظه اصلی ۱۱۱
شکل ۴-۳) زمان اجرا ۱۱۲
شکل ۴-۵) تعداد گره‌های پردازش شده ۱۱۴
شکل ۴-۶) کوئریهای تک شاخه‌ای ۱۱۶
شکل ۴-۷)کوئری‌های چند شاخه‌ای ۱۱۷
شکل ۴-۸) کوئریهایی با عملگر نقیض ۱۱۸
جدول ۴-۱) مشخصات دیتاست‌ها معروف ۱۰۴
جدول ۴-۲) مشخصات جدول رندوم دیتاست ۱۰۵
جدول ۴-۳) اندازه کد گذاری Dewey 107
جدول ۴-۴) کوئریهای اجرا شده روی IT و TJFast 109
جدول ۴-۵) کوئری‌های اجرا شده روی T2S 125

بهینه سازی زبان یکپارچه ساز بر روی شبکه اطلاعاتی ناهمگون

مقدمه
از آنجایی که در دنیای XML هنوز به روش استانداردی، مانند SQL در پایگاه داده‌های رابطه‌ای دست نیافته‌ایم، بحث و بررسی برای افزایش کارایی کوئریهای XML همچنان ادامه دارد. روش‌های زیادی در این زمینه مطرح هستند که ما را مهمترین ایرادات آن‌ها را در زیر آورده‌ایم:
۱٫ تولید داده‌های میانی(داده‌هایی که تنها برای تولید پاسخ کاربر تولید می‌شوند و کاربرد دیگری ندارند)
۲٫ افزایش زمان پاسخ با افزایش طول کوئری

۳٫ دخالت دادن تمام گره‌های کوئری در رسیدن به پاسخ
۴٫ کاربرد برای دسته کوچکی از کوئریها و عملگرها
۵٫ عدم سازگاری با روش‌هایی که برای شاخص کردن سند به کار می‌روند
بسیاری از محققین نیز سعی در اعمال روش‌های سنتی رابطه‌ای برای مدیریت سندهای XML داشته‌اند. اما ساختار یک سند XML در قالب یک درخت، متفاوت از ساختار رابطه‌ای و قدیمی، است. به عنوان مثال در مدل رابطه‌ای داده‌های یک جدول در یک سطح قرار داشته و رابطه مابین جداول نیز به صورت پیوند به راحتی قابل پیاده سازی است. ولی در یک سند XML روابط دیگری مانند پدر-فرزندی، جدی-نسلی و همنیایی نیز وجود دارند. بنابراین

بهینه سازی زبان یکپارچه ساز بر روی شبکه اطلاعاتی ناهمگون

پیچیدگی‌ کوئریهای کاربر نیز بیش از پیش شده است و محدوده جواب‌ها نیز تغییر کرده است. از طرف دیگر اعمال عملگرهای ساده مانند NOT نیز به سادگی گذشته امکان پذیر نمی‌باشند.
در نتیجه ارائه روشی برای این ساختار متفاوت، باید توانایی‌های زیر را داشته باشد:
• توانایی پاسخ به کوئریها در حداقل زمان ممکن
• کارایی یکسان برای تمامی کوئریهای موجود در XML
• عدم نیاز به آماده سازی طولانی سند
• سازگاری با تمامی شاخص‌های موجود
• عدم تولید داده‌های بی فایده

بهینه سازی زبان یکپارچه ساز بر روی شبکه اطلاعاتی ناهمگون

• وجود پیوستگی میان پاسخ و کوئری
ما در این پایان نامه در فصل اول با توضیحی بر مقدمات XML و کاربرد آن به عنوان داده صحبت کرده‌ایم. در انتهای همین فصل یک مروری بر نحوه پردازش کوئریها و مشکلات موجود در این راستا داشته‌ایم. در فصل دوم به دسته بندی راه‌کارهای ارائه شده پرداخته و نقاط قوت و ضعف هرکدام را بررسی کرده و

در انتها به یک جمع بندی کلی رسیده‌ایم. در فصل سوم با توضیح روش سه مرحلهای جدول راهنما[۱] به صورت مقدماتی شروع کرده و کاربرد آن را برای کوئریهای پیچیده نیز بیان کرده‌ایم[۲]. در ادامه این روش را طوری بسط داده‌ایم که برای دسته بزرگی از کوئریها یعنی کوئریهایی با عملگر نقیض نیز کارایی داشته باشد[۳]. توسعه این روش را با معرفی‌………..  بهینه سازی زبان یکپارچه ساز بر روی شبکه اطلاعاتی ناهمگون

فصل اول

مفاهیم پایه

۱-۱ XML چیست
XML – اگر معنای اولیه آن را به درستی برگردانیم- یک زبان نشانه گذاری یا علامت گذاری است، که می توان به کمک آن زبان‌های جدید و علامت دار را به وجود آورد به طور معمول برای ساختن نشانه‌های جدید و پردازش ساختمان داده‌های یک متن و نحوه نمایش آن متن به کار می‌رود. اما می‌تواند برای

شرح٬ مدیریت و انتقال داده‌هایی متفاوت به کار گرفته شود. از جمله متون ٬ عکس‌ها٬ صدا٬ فرم ها٬ فایل‌های چندرسانه‌ای و غیره. همچنین در انتقال اطلاعات و تغییر آن‌ها از یک نوع داده به یک نوع دیگر هم استفاده می‌شود.

بر خلاف HTML که یک زبان برای نمایش‌ اطلاعات در یک مرورگر است و کنترل نحوه نمایش داده‌ها را به عهده دارد. XML یک استاندارد باز می‌باشد.

یک استاندارد پایه است که وابستگی به رسانه‌ها٬ سیستم عامل‌ها و دیگر سیستم‌ها ندارد. قابل توسعه است به این دلیل که سازمان‌ها یا افراد می‌توانند دستورهای خود – تگ‌ها – را تعریف کنند که معنای خاص خودشان را دارند و این نام‌های خاص خیلی بهتر ازمدل‌های HTML هستند به دلیل

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

۱-۱-۱ معرفی اجزاء اصلی XML
در سندهایXML سه المان اصلی وجود دارد:
• عنصر(Element): سند‌ها اصولا از عناصر تشکیل می‌شوند. خود عناصر نیز از صفت‌ها و متن‌ها و حتی از عناصر دیگر می‌توانند ساخته شوند.

• صفت(attribute) : ویژگی است که عناصر را از هم متمایز می‌کند. صفت قبل از تمامی موارد داخل عنصر تعریف می‌شود. صفتی که یکتا باشد و به عنوان کلید برای یک عنصر در نظر گرفته می‌شود و به آنID گفته ………………….
………………………..

بهینه سازی زبان یکپارچه ساز بر روی شبکه اطلاعاتی ناهمگون

فصل دوم

مروری بر کارهای انجام شده

۲-۱ روش حلقه های تودرتو
همانگونه که در قسمت قبلی گفته شد یک سند به‌صورت مجموعه‌ای از گره‌‌ها و به‌صورت درخت نمایش داده می‌شود. از طرف دیگر تمامی زبان‌های کوئری در XML به انطباق مابین گره‌‌های کوئری و سند نیاز دارند. برای مثال فرض کنید که ما کوئریی زیر را صادر کردیم:
BOOK // title;
یعنی تمام عنوان‌ کتاب‌ها را می‌خواهیم. روش‌های زیادی در این مورد وجود دارند که هیچ کدام از پشتوانه تئوریک قوی برای بهینه بودن برخوردار نیستند بلکه فقط با داده‌های آماری روش خود را ارائه کرده‌اند.
یکی از این روش ها به ” حلقه های تودرتو ” معروف است. در این روش ابتدا تمامی کتاب‌ها را پیدا میکنیم و سپس برای هر گره‌ تست میکنیم که اولادی بنام title دارد یا خیر. این روش اولین روشی است که به کار برده شده است[۸].

همانگونه که مشخص است این روش ایرادات اساسی زیادی دارد که ما در زیر به دو مورد اصلی،که آن را غیر قابل پیاده سازی برای اسناد بزرگ میکند ، اشاره میکنیم:

• در این روش به ازای هر گره‌ یک حلقه For باید اجرا شود، برای مثال اگر بخواهیم کوئریی a/b//c/d را اجرا کنیم نیاز به ۴ حلقه تودرتو خواهیم داشت. پس پیچیدگی زمانی این روش O(nn) که n تعداد گره‌های کوئری میباشد خواهد بود.

• در این روش تعداد نتایج میانی که تولید میشود بسیار زیاد بوده و علاوه بر تلف کردن زمان برای پردازش این گره‌های بیفایده، نیاز به حافظه بسیار بزرگی برای نگهداری برای این گره‌‌ها خواهیم داشت.

بهینه سازی زبان یکپارچه ساز بر روی شبکه اطلاعاتی ناهمگون

۲-۲ روش Structural Join
در این روش ابتدا تمامی روابط دودویی گره‌ها به دست میآید. برای مثال کوئریی a//b/c//d به سه رابطه a//b ،b/c و c//d تبدیل می‌شود. سپس هر کوئری به‌صورت جداگانه اجرا شده و در نهایت نتایج با هم ادغام می‌شوند. در ادامه همراه با یک مثال نحوه بدست آوردن یکی از این کوئریهای دودوئی را توضیح می‌دهیم.
به پرس جوی Book//Title دقت کنید. در این روش به طور جداگانه دو لیست، یکی برای کتاب و دیگری برای عنوان، برای این دو گره‌ ایجاد خواهیم کرد. حال تمامی گره‌های Title را با تمام گره‌های Book مقایسه می‌کنیم هر ……………………. بهینه سازی زبان یکپارچه ساز بر روی شبکه اطلاعاتی ناهمگون

فصل چهارم

پیاده سازی و ارزیابی

۴-۱ محیط پیاده سازی
در این قسمت ارزیابی روش جدول راهنما آورده شده است. ما این روش را با دو روش مطرح TJFast [56] به عنوان نماینده گروه C و Twig2Stack [28] به عنوان نماینده گروه B مقایسه می‌کنیم. اما قبل از آن سیستمی که برای مقایسه انتخاب شده است را به طور شفاف شرح دهیم.

شاخص مسیری منتخب: در مرحله اول روش خود، ما نیاز به یکی از شاخص‌ها مسیری داریم تا کوئریهای تک شاخه‌ای را به مسیرهای مطلق گره‌های جواب درSS تبدیل کند. شاخص‌های مسیری زیادی برای انتخاب وجود دارند ولی هرکدام سعی دارند به تنهایی به کوئری‌های پیچیده پاسخ دهند، در

نتیجه برای بسیاری از پرس وجو ها نیاز به دسترسی به داده های اصلی سند دارند و در نتیجه کارایی لازم را ندارند. در حالی که شاخص مسیری که ما

بهینه سازی زبان یکپارچه ساز بر روی شبکه اطلاعاتی ناهمگون

برای طرح خود انتخاب می کنیم‌، تنها برای جستجو روی SS و برای پاسخ به کوئریهای تک شاخه‌ای است، در نتیجه تنها باید دویژگی زیر را داشته باشد:
۱٫ SS آن کوچک بوده و پاسخ دهی به کوئریهای تک شاخه ای را سریع انجام دهد.

۲٫ برای تمامی عملگرهای(* , ? , //) ممکن برای کوئریهای تک شاخه‌ای کاربرد داشته باشد.
در میان تمامی شاخص های مسیری بهترین گزینه که تنها دو مورد بالا را فراهم کندYAPI است که برای پاسخ به کوئری های تک شاخهای سریع ترین و کم هزینه ترین روش است.

مجموعه داده‌های انتخابی: ما از چهار دیتاست به‌نام‌های DBLP , TreeBank و XMark استفاده می‌کنیم. هرکدام از این دیتاست‌ها در دنیای XML برای محققان در این زمینه کاملا شناخته شده هستند.
DBLP : یک سند حجیم XML است که ارتفاع بسیاری کمی را دارد. شمای این سند بسیار ساده و تکرار به مراتب در این سند دیده می‌شود.
TreeBank: بر خلاف DBLP این سند دارای شمای بسیار پیچیده و کم حجمی است و شمای آن بیشتر شبیه به گراف می باشد تا یک درخت.

XMark: به عنوان سومین دیتاست برای داده های آزمایش ما مطرح می‌باشد. این سند فاقد شما می باشد. ما از آنجایی این سند را انتخاب کرده ایم تا نشان دهیم که روش جدول راهنما برای اینگونه اسناد نیز کاربرد دارد. اما این اسناد تنها برای اجرای پرس و جو اول خود نیازمند تولید شما هستند. ما برای اینگونه اسناد مجبوریم……………………….. بهینه سازی زبان یکپارچه ساز بر روی شبکه اطلاعاتی ناهمگون