حالت تاریک
فصل ۲ — مدلهای داده و زبانهای پرسوجو
محدودیتهای زبان من، محدودیتهای دنیای من را معنا میدهد.
— Ludwig Wittgenstein، Tractatus Logico-Philosophicus (۱۹۲۲)
مدلهای داده شاید مهمترین بخش توسعهٔ نرمافزار باشند، چون تأثیر عمیقی دارند: نهتنها بر نحوهٔ نوشتن نرمافزار، بلکه بر نحوهٔ فکر کردن ما دربارهٔ مسئلهای که حل میکنیم.
بیشتر برنامهها با لایهگذاری یک مدل داده روی مدل دیگر ساخته میشوند. برای هر لایه، پرسش کلیدی این است: چگونه بر حسب لایهٔ پایینتر نمایش داده میشود؟ مثلاً:
- بهعنوان توسعهدهندهٔ برنامه، به دنیای واقعی (که در آن مردم، سازمانها، کالاها، کنشها، جریانهای پول، حسگرها و غیره وجود دارند) نگاه میکنید و آن را بر حسب اشیاء یا ساختارهای داده و APIهایی که آن ساختارها را دستکاری میکنند مدل میکنید. آن ساختارها اغلب مختص برنامهٔ شما هستند.
- وقتی میخواهید آن ساختارهای داده را ذخیره کنید، آنها را بر حسب یک مدل دادهٔ عمومی — مانند سندهای JSON یا XML، جداول در پایگاه دادهٔ رابطهای، یا مدل گراف — بیان میکنید.
- مهندسانی که نرمافزار پایگاه دادهٔ شما را ساختند، روشی برای نمایش آن دادهٔ JSON/XML/رابطهای/گراف بر حسب بایتها در حافظه، روی دیسک یا در شبکه انتخاب کردند. آن نمایش ممکن است امکان پرسوجو، جستجو، دستکاری و پردازش داده به روشهای مختلف را فراهم کند.
- در لایههای پایینتر، مهندسان سختافزار کشف کردهاند چگونه بایتها را بر حسب جریانهای الکتریکی، پالسهای نور، میدانهای مغناطیسی و موارد دیگر نمایش دهند.
در یک برنامهٔ پیچیده ممکن است لایههای واسط بیشتری وجود داشته باشد، مانند APIهایی که روی APIهای دیگر ساخته شدهاند، اما ایدهٔ اصلی همچنان یکسان است: هر لایه پیچیدگی لایههای زیرین را با ارائهٔ یک مدل دادهٔ تمیز پنهان میکند. این انتزاعها به گروههای مختلف — مثلاً مهندسان فروشندهٔ پایگاه داده و توسعهدهندگان برنامه که از پایگاه دادهٔ آنها استفاده میکنند — امکان همکاری مؤثر میدهد.
انواع مختلفی از مدلهای داده وجود دارد و هر مدل داده فرضهایی دربارهٔ نحوهٔ استفاده از آن در خود دارد. برخی کاربردها آسان و برخی پشتیبانی نمیشوند؛ برخی عملیات سریع و برخی عملکرد ضعیفی دارند؛ برخی تبدیلهای داده طبیعی به نظر میرسند و برخی ناجورند.
تسلط بر حتی یک مدل داده ممکن است تلاش زیادی ببرد (به تعداد کتابهای مدلسازی دادهٔ رابطهای فکر کنید). ساخت نرمافزار بهتنهایی سخت است، حتی وقتی با یک مدل داده کار میکنید و نگران جزئیات درونی آن نیستید. اما چون مدل داده تأثیر عمیقی بر آنچه نرمافزار بالای آن میتواند و نمیتواند انجام دهد دارد، انتخاب مدلی مناسب برای برنامه مهم است.
در این فصل به مجموعهای از مدلهای دادهٔ عمومی برای ذخیرهسازی و پرسوجوی داده (نکتهٔ ۲ در فهرست بالا) میپردازیم. بهویژه مدل رابطهای، مدل سندی و چند مدل دادهٔ مبتنی بر گراف را مقایسه میکنیم. همچنین زبانهای پرسوجوی مختلف و موارد استفادهٔ آنها را بررسی میکنیم. در فصل ۳ نحوهٔ کار موتورهای ذخیرهسازی — یعنی چگونگی پیادهسازی واقعی این مدلهای داده (نکتهٔ ۳ در فهرست) — را بحث میکنیم.
مدل رابطهای در برابر مدل سندی
شناختهشدهترین مدل دادهٔ امروز احتمالاً مدل SQL است که بر پایهٔ مدل رابطهای پیشنهادی Edgar Codd در ۱۹۷۰ [1] است: داده در روابط (در SQL جدول نامیده میشوند) سازماندهی میشود، که هر رابطه مجموعهای نامرتب از تاپلها (سطرها در SQL) است.
مدل رابطهای یک پیشنهاد نظری بود و بسیاری در آن زمان در پیادهسازی کارآمد آن تردید داشتند. با این حال، تا اواسط دههٔ ۱۹۸۰، سیستمهای مدیریت پایگاه دادهٔ رابطهای (RDBMS) و SQL ابزار انتخاب اکثر کسانی شد که نیاز به ذخیره و پرسوجوی داده با ساختار منظم داشتند. سلطهٔ پایگاههای دادهٔ رابطهای حدود ۲۵ تا ۳۰ سال دوام آورد — ابدیت در تاریخ محاسبات.
ریشههای پایگاههای دادهٔ رابطهای در پردازش دادهٔ کسبوکار نهفته است که در دهههای ۱۹۶۰ و ۱۹۷۰ روی رایانههای mainframe انجام میشد. موارد استفاده از دیدگاه امروز عادی به نظر میرسند: معمولاً پردازش تراکنش (ثبت فروش یا تراکنشهای بانکی، رزرو پرواز، نگهداری موجودی انبار) و پردازش دستهای (صدور فاکتور مشتری، حقوق و دستمزد، گزارشدهی).
پایگاههای دادهٔ دیگر در آن زمان توسعهدهندگان برنامه را وادار میکردند زیاد دربارهٔ نمایش درونی داده در پایگاه داده فکر کنند. هدف مدل رابطهای پنهان کردن آن جزئیات پیادهسازی پشت رابط تمیزتر بود.
در طول سالها رویکردهای رقیب زیادی برای ذخیرهسازی و پرسوجوی داده وجود داشت. در دهههای ۱۹۷۰ و اوایل ۱۹۸۰، مدل شبکهای و مدل سلسلهمراتبی جایگزینهای اصلی بودند، اما مدل رابطهای بر آنها غلبه کرد. پایگاههای دادهٔ شیء در اواخر دههٔ ۱۹۸۰ و اوایل ۱۹۹۰ آمدند و رفتند. پایگاههای دادهٔ XML در اوایل دههٔ ۲۰۰۰ ظاهر شدند، اما فقط پذیرش niche داشتند. هر رقیب مدل رابطهای در زمان خود هیاهوی زیادی ایجاد کرد، اما دوام نیاورد [2].
با قدرتمندتر شدن چشمگیر رایانهها و شبکهای شدن آنها، برای اهداف فزایندهای به کار گرفته شدند. و قابل توجه است که پایگاههای دادهٔ رابطهای بسیار خوب فراتر از دامنهٔ اصلی پردازش دادهٔ کسبوکار تعمیم یافتند و طیف گستردهای از موارد استفاده را پوشش دادند. بخش زیادی از آنچه امروز در وب میبینید هنوز با پایگاههای دادهٔ رابطهای کار میکند، چه انتشار آنلاین، بحث، شبکههای اجتماعی، تجارت الکترونیک، بازیها، برنامههای بهرهوری software-as-a-service یا موارد دیگر.
تولد NoSQL
اکنون در دههٔ ۲۰۱۰، NoSQL تازهترین تلاش برای براندازی سلطهٔ مدل رابطهای است. نام «NoSQL» بدبختانه است، چون واقعاً به فناوری خاصی اشاره نمیکند — در اصل فقط بهعنوان هشتگ جذاب Twitter برای یک meetup دربارهٔ پایگاههای دادهٔ متنباز، توزیعشده و غیررابطهای در ۲۰۰۹ [3] در نظر گرفته شده بود. با این حال، اصطلاح به اعصاب زد و بهسرعت در جامعهٔ startupهای وب و فراتر از آن گسترش یافت. چندین سیستم پایگاه دادهٔ جالب اکنون با هشتگ #NoSQL مرتبطاند و بهصورت پسگیرانه بهعنوان Not Only SQL [4] تفسیر شده است.
چند نیروی محرک پشت پذیرش پایگاههای دادهٔ NoSQL وجود دارد، از جمله:
- نیاز به مقیاسپذیری بیشتر از آنچه پایگاههای دادهٔ رابطهای بهراحتی میتوانند دست یابند، از جمله مجموعهدادههای بسیار بزرگ یا throughput نوشتن بسیار بالا
- ترجیح گستردهٔ نرمافزار آزاد و متنباز بر محصولات تجاری پایگاه داده
- عملیات پرسوجوی تخصصی که مدل رابطهای بهخوبی پشتیبانی نمیکند
- ناامیدی از محدودیتهای schemaهای رابطهای و تمایل به مدل دادهٔ پویا و بیانگرتر [5]
برنامههای مختلف نیازمندیهای متفاوتی دارند و بهترین انتخاب فناوری برای یک مورد استفاده ممکن است با بهترین انتخاب برای مورد دیگر متفاوت باشد. بنابراین به نظر میرسد در آیندهٔ نزدیک، پایگاههای دادهٔ رابطهای همچنان در کنار انواع گستردهای از datastoreهای غیررابطهای استفاده شوند — ایدهای که گاهی polyglot persistence [3] نامیده میشود.
ناهماهنگی شیء-رابطهای
بیشتر توسعهٔ برنامهٔ امروز با زبانهای برنامهنویسی شیءگرا انجام میشود که به انتقاد رایجی از مدل دادهٔ SQL منجر میشود: اگر داده در جداول رابطهای ذخیره شود، لایهٔ ترجمهٔ ناجوری بین اشیاء در کد برنامه و مدل جداول، سطرها و ستونهای پایگاه داده لازم است. ناهماهنگی بین مدلها گاهی impedance mismatch نامیده میشود.i
چارچوبهای Object-Relational Mapping (ORM) مانند ActiveRecord و Hibernate مقدار کد boilerplate لازم برای این لایهٔ ترجمه را کاهش میدهند، اما نمیتوانند تفاوتهای بین دو مدل را کاملاً پنهان کنند.
مثلاً، شکل ۲-۱ نشان میدهد چگونه یک رزومه (پروفایل LinkedIn) میتواند در یک schema رابطهای بیان شود. پروفایل بهطور کلی با شناسهٔ یکتا user_id شناسایی میشود. فیلدهایی مانند first_name و last_name دقیقاً یکبار برای هر کاربر ظاهر میشوند، پس میتوان آنها را بهعنوان ستونهای جدول users مدل کرد. با این حال، بیشتر مردم بیش از یک شغل در دوران حرفهای خود داشتهاند (positions)، و ممکن است تعداد متفاوتی دورهٔ تحصیلی و هر تعداد اطلاعات تماس داشته باشند. رابطهٔ یک-به-چند از کاربر به این موارد وجود دارد که میتوان به روشهای مختلف نمایش داد:
- در مدل سنتی SQL (قبل از SQL:1999)، رایجترین نمایش نرمالشده این است که positions، education و contact information در جداول جداگانه با ارجاع foreign key به جدول users قرار گیرند، همانطور که در شکل ۲-۱ است.
- نسخههای بعدی استاندارد SQL از datatypeهای ساختاریافته و دادهٔ XML پشتیبانی افزودند؛ این امکان ذخیرهٔ دادهٔ چندمقداری در یک سطر واحد با پشتیبانی پرسوجو و نمایهگذاری درون آن سندها را داد. این قابلیتها تا حد متفاوتی توسط Oracle، IBM DB2، MS SQL Server و PostgreSQL [6, 7] پشتیبانی میشوند. datatype JSON نیز توسط چند پایگاه داده از جمله IBM DB2، MySQL و PostgreSQL [8] پشتیبانی میشود.
- گزینهٔ سوم این است که jobs، education و contact info را بهصورت سند JSON یا XML رمزگذاری کنید، در ستون متنی پایگاه داده ذخیره کنید و بگذارید برنامه ساختار و محتوای آن را تفسیر کند. در این چیدمان، معمولاً نمیتوانید از پایگاه داده برای پرسوجوی مقادیر درون آن ستون رمزگذاریشده استفاده کنید.
i. اصطلاحی وامگرفته از الکترونیک. هر مدار الکتریکی امپدانس مشخصی (مقاومت در برابر جریان متناوب) در ورودیها و خروجیهایش دارد. وقتی خروجی یک مدار را به ورودی مدار دیگر وصل میکنید، انتقال توان در اتصال اگر امپدانس ورودی و خروجی دو مدار همخوان باشد بیشینه میشود. ناهماهنگی امپدانس میتواند به بازتاب سیگنال و مشکلات دیگر منجر شود.
شکل ۲-۱. نمایش پروفایل LinkedIn با schema رابطهای. عکس Bill Gates با اجازهٔ Wikimedia Commons، Ricardo Stuckert، Agência Brasil.
برای ساختار دادهای مانند رزومه که عمدتاً سند خودکفاست، نمایش JSON میتواند کاملاً مناسب باشد: مثال ۲-۱ را ببینید. JSON جذابیت سادگی بسیار بیشتر نسبت به XML را دارد. پایگاههای دادهٔ سند-محور مانند MongoDB [9]، RethinkDB [10]، CouchDB [11] و Espresso [12] از این مدل داده پشتیبانی میکنند.
مثال ۲-۱. نمایش پروفایل LinkedIn بهصورت سند JSON
json
{
"user_id": 251,
"first_name": "Bill",
"last_name": "Gates",
"summary": "Co-chair of the Bill & Melinda Gates... Active blogger.",
"region_id": "us:91",
"industry_id": 131,
"photo_url": "/p/7/000/253/05b/308dd6e.jpg",
"positions": [
{"job_title": "Co-chair", "organization": "Bill & Melinda Gates Foundation"},
{"job_title": "Co-founder, Chairman", "organization": "Microsoft"}
],
"education": [
{"school_name": "Harvard University", "start": 1973, "end": 1975},
{"school_name": "Lakeside School, Seattle", "start": null, "end": null}
],
"contact_info": {
"blog": "http://thegatesnotes.com",
"twitter": "http://twitter.com/BillGates"
}
}برخی توسعهدهندگان احساس میکنند مدل JSON ناهماهنگی impedance بین کد برنامه و لایهٔ ذخیرهسازی را کاهش میدهد. با این حال، همانطور که در فصل ۴ خواهیم دید، مشکلاتی با JSON بهعنوان قالب رمزگذاری داده نیز وجود دارد. فقدان schema اغلب بهعنوان مزیت ذکر میشود؛ این را در «انعطاف schema در مدل سندی» در صفحه ۳۹ بحث میکنیم.
نمایش JSON locality بهتری نسبت به schema چندجدولی در شکل ۲-۱ دارد. اگر بخواهید در مثال رابطهای یک پروفایل را واکشی کنید، باید یا چند پرسوجو انجام دهید (هر جدول را با user_id پرسوجو کنید) یا join چندطرفهٔ پیچیدهای بین جدول users و جداول فرعی آن انجام دهید. در نمایش JSON، همهٔ اطلاعات مرتبط در یک جا هستند و یک پرسوجو کافی است.
رابطههای یک-به-چند از پروفایل کاربر به positions، سابقهٔ تحصیلی و اطلاعات تماس، ساختار درختی در داده را القا میکنند و نمایش JSON این ساختار درختی را صریح میکند (شکل ۲-۲ را ببینید).
شکل ۲-۲. رابطههای یک-به-چند که ساختار درختی تشکیل میدهند.
رابطههای چند-به-یک و چند-به-چند
در مثال ۲-۱ در بخش قبل، region_id و industry_id بهصورت ID داده شدهاند، نه رشتههای متنی ساده «Greater Seattle Area» و «Philanthropy». چرا؟
اگر رابط کاربری فیلدهای متنی آزاد برای وارد کردن region و industry دارد، منطقی است آنها را بهصورت رشتهٔ متنی ساده ذخیره کنید. اما مزایایی در داشتن فهرستهای استاندارد مناطق جغرافیایی و صنایع و اجازه دادن به کاربر برای انتخاب از drop-down یا autocompleter وجود دارد:
- سبک و املای یکنواخت در پروفایلها
- اجتناب از ابهام (مثلاً اگر چند شهر با نام یکسان وجود داشته باشد)
- سهولت بهروزرسانی — نام فقط در یک جا ذخیره میشود، پس بهروزرسانی سراسری در صورت نیاز (مثلاً تغییر نام شهر بهدلیل رویدادهای سیاسی) آسان است
- پشتیبانی localization — وقتی سایت به زبانهای دیگر ترجمه میشود، فهرستهای استاندارد میتوانند localized شوند تا region و industry به زبان بیننده نمایش داده شوند
- جستجوی بهتر — مثلاً جستجوی philanthropistها در ایالت Washington میتواند این پروفایل را match کند، چون فهرست regionها میتواند واقعیت «Seattle در Washington است» را رمزگذاری کند (که از رشتهٔ «Greater Seattle Area» آشکار نیست)
ذخیرهٔ ID یا رشتهٔ متنی پرسشی از تکرار است. وقتی ID استفاده میکنید، اطلاعاتی که برای انسان معنا دارد (مانند کلمهٔ Philanthropy) فقط در یک جا ذخیره میشود و هر چیزی که به آن ارجاع میدهد از ID استفاده میکند (که فقط درون پایگاه داده معنا دارد). وقتی متن را مستقیماً ذخیره میکنید، اطلاعات معنادار برای انسان را در هر رکوردی که از آن استفاده میکند تکرار میکنید.
مزیت استفاده از ID این است که چون برای انسان معنا ندارد، هرگز نیازی به تغییر ندارد: ID میتواند ثابت بماند، حتی اگر اطلاعاتی که شناسایی میکند تغییر کند. هر چیزی که برای انسان معنادار است ممکن است در آینده نیاز به تغییر داشته باشد — و اگر آن اطلاعات تکرار شده باشد، همهٔ نسخههای اضافی باید بهروز شوند. این overhead نوشتن ایجاد میکند و ریسک ناسازگاری (که برخی نسخهها بهروز شوند و برخی نه) را به همراه دارد. حذف چنین تکراری ایدهٔ کلیدی پشت normalization در پایگاههای داده است.ii
ii. ادبیات مدل رابطهای چند normal form مختلف را از هم تمایز میدهد، اما تمایزها از نظر عملی اهمیت کمی دارند. بهعنوان قاعدهٔ سرانگشتی، اگر مقادیری را تکرار میکنید که میتوانستند فقط در یک جا ذخیره شوند، schema نرمالشده نیست.
مدیران پایگاه داده و توسعهدهندگان عاشق بحث دربارهٔ normalization و denormalization هستند، اما فعلاً قضاوت را معلق میگذاریم. در بخش سوم این کتاب به این موضوع برمیگردیم و روشهای سیستماتیک برخورد با caching، denormalization و دادهٔ مشتق را بررسی میکنیم.
متأسفانه، نرمالسازی این داده به رابطههای چند-به-یک (بسیاری از مردم در یک region خاص زندگی میکنند، بسیاری در یک industry خاص کار میکنند) نیاز دارد که بهخوبی در مدل سندی جا نمیگیرند. در پایگاههای دادهٔ رابطهای، ارجاع به سطرهای جداول دیگر با ID عادی است، چون joinها آساناند. در پایگاههای دادهٔ سندی، join برای ساختارهای درختی یک-به-چند لازم نیست و پشتیبانی از join اغلب ضعیف است.iii
اگر پایگاه داده خود join را پشتیبانی نکند، باید join را در کد برنامه با انجام چند پرسوجو به پایگاه داده شبیهسازی کنید. (در این مورد، فهرست regionها و industryها احتمالاً کوچک و با تغییر آهستهاند که برنامه بتواند آنها را در حافظه نگه دارد. اما با این حال، کار انجام join از پایگاه داده به کد برنامه منتقل میشود.)
علاوه بر این، حتی اگر نسخهٔ اولیهٔ برنامه بهخوبی در مدل سندی بدون join جا شود، داده تمایل دارد با افزودن قابلیتها به برنامهها بیشتر به هم متصل شود. مثلاً تغییراتی که میتوانیم در مثال رزومه اعمال کنیم را در نظر بگیرید:
سازمانها و مدارس بهعنوان entity
در توضیح قبلی، organization (شرکتی که کاربر در آن کار کرده) و school_name (جایی که تحصیل کرده) فقط رشته هستند. شاید باید به entity ارجاع دهند؟ آنگاه هر سازمان، مدرسه یا دانشگاه میتواند صفحهٔ وب خود (با logo، news feed و غیره) داشته باشد؛ هر رزومه میتواند به سازمانها و مدارسی که ذکر میکند لینک دهد و logo و اطلاعات دیگر آنها را شامل شود (مثالی از LinkedIn در شکل ۲-۳).
توصیهنامهها
فرض کنید میخواهید قابلیت جدید اضافه کنید: یک کاربر میتواند برای کاربر دیگر توصیهنامه بنویسد. توصیهنامه در رزومهٔ کاربر توصیهشده، همراه با نام و عکس کاربر توصیهکننده نمایش داده میشود. اگر توصیهکننده عکسش را بهروز کند، هر توصیهنامهای که نوشته باید عکس جدید را منعکس کند. بنابراین، توصیهنامه باید ارجاعی به پروفایل نویسنده داشته باشد.
iii. در زمان نگارش، join در RethinkDB پشتیبانی میشود، در MongoDB پشتیبانی نمیشود، و در CouchDB فقط در viewهای از پیش اعلامشده پشتیبانی میشود.
شکل ۲-۳. نام شرکت فقط رشته نیست، بلکه لینکی به entity شرکت است. Screenshot از linkedin.com.
شکل ۲-۴ نشان میدهد این قابلیتهای جدید به رابطههای چند-به-چند نیاز دارند. داده در هر مستطیل نقطهچین میتواند در یک سند گروهبندی شود، اما ارجاعها به سازمانها، مدارس و کاربران دیگر باید بهصورت reference نمایش داده شوند و هنگام پرسوجو به join نیاز دارند.
شکل ۲-۴. گسترش رزومهها با رابطههای چند-به-چند.
آیا پایگاههای دادهٔ سندی تاریخ را تکرار میکنند؟
در حالی که رابطههای چند-به-چند و joinها بهطور معمول در پایگاههای دادهٔ رابطهای استفاده میشوند، پایگاههای دادهٔ سندی و NoSQL بحث دربارهٔ بهترین نمایش چنین رابطههایی در پایگاه داده را دوباره باز کردند. این بحث از NoSQL قدیمیتر است — در واقع به اولین سیستمهای پایگاه دادهٔ کامپیوتری برمیگردد.
محبوبترین پایگاه داده برای پردازش دادهٔ کسبوکار در دههٔ ۱۹۷۰ IBM Information Management System (IMS) بود که در اصل برای نگهداری موجودی در برنامهٔ فضایی Apollo توسعه یافت و نخستین بار در ۱۹۶۸ بهصورت تجاری منتشر شد [13]. هنوز در حال استفاده و نگهداری است و روی OS/390 روی mainframeهای IBM اجرا میشود [14].
طراحی IMS از مدل دادهٔ نسبتاً سادهای به نام مدل سلسلهمراتبی استفاده میکرد که شباهتهای قابل توجهی با مدل JSON مورد استفادهٔ پایگاههای دادهٔ سندی دارد [2]. همهٔ داده را بهصورت درختی از رکوردها تودرتو در رکوردها نمایش میداد، بسیار شبیه ساختار JSON شکل ۲-۲.
مانند پایگاههای دادهٔ سندی، IMS برای رابطههای یک-به-چند خوب کار میکرد، اما رابطههای چند-به-چند را دشوار میکرد و join را پشتیبانی نمیکرد. توسعهدهندگان باید تصمیم میگرفتند داده را تکرار (denormalize) کنند یا ارجاعها از یک رکورد به رکورد دیگر را دستی resolve کنند. این مشکلات دهههای ۱۹۶۰ و ۱۹۷۰ بسیار شبیه مشکلاتی بود که توسعهدهندگان امروز با پایگاههای دادهٔ سندی با آن مواجه میشوند [15].
راهحلهای مختلفی برای حل محدودیتهای مدل سلسلهمراتبی پیشنهاد شد. دو مورد برجسته مدل رابطهای (که SQL شد و جهان را فتح کرد) و مدل شبکهای (که در ابتدا پیروان زیادی داشت اما در نهایت به فراموشی رفت) بودند. «بحث بزرگ» بین این دو اردوگاه بخش زیادی از دههٔ ۱۹۷۰ را در بر گرفت [2].
چون مسئلهای که دو مدل حل میکردند هنوز امروز بسیار مرتبط است، ارزش دارد این بحث را بهاختصار در نور امروز مرور کنیم.
مدل شبکهای
مدل شبکهای توسط کمیتهای به نام Conference on Data Systems Languages (CODASYL) استاندارد شد و توسط چند فروشندهٔ پایگاه داده پیادهسازی شد؛ CODASYL model [16] هم نامیده میشود.
مدل CODASYL تعمیمی از مدل سلسلهمراتبی بود. در ساختار درختی مدل سلسلهمراتبی، هر رکورد دقیقاً یک parent دارد؛ در مدل شبکهای، یک رکورد میتوانست چند parent داشته باشد. مثلاً میتوانست یک رکورد برای region «Greater Seattle Area» وجود داشته باشد و هر کاربری که در آن region زندگی میکرد به آن لینک شود. این امکان مدلسازی رابطههای چند-به-یک و چند-به-چند را میداد.
پیوندها بین رکوردها در مدل شبکهای foreign key نبودند، بلکه بیشتر شبیه pointer در زبان برنامهنویسی بودند (در حالی که روی دیسک ذخیره میشدند). تنها راه دسترسی به رکورد، دنبال کردن مسیری از رکورد root در امتداد این زنجیرههای پیوند بود. access path نامیده میشد.
در سادهترین حالت، access path میتوانست مانند پیمایش linked list باشد: از سر لیست شروع کنید و یکبهیک رکوردها را ببینید تا آنچه میخواهید را پیدا کنید. اما در دنیای رابطههای چند-به-چند، چند مسیر مختلف میتواند به همان رکورد منجر شود و برنامهنویس کار با مدل شبکهای باید این access pathهای مختلف را در ذهن نگه میداشت.
پرسوجو در CODASYL با حرکت cursor در پایگاه داده با تکرار روی فهرست رکوردها و دنبال کردن access pathها انجام میشد. اگر رکوردی چند parent داشت (یعنی چند pointer ورودی از رکوردهای دیگر)، کد برنامه باید همهٔ رابطههای مختلف را ردیابی میکرد. حتی اعضای کمیتهٔ CODASYL اعتراف میکردند این مانند پیمایش در فضای دادهٔ n-بعدی است [17].
اگرچه انتخاب دستی access path میتوانست کارآمدترین استفاده از قابلیتهای بسیار محدود سختافزار دههٔ ۱۹۷۰ (مانند tape drive که seekهایش بسیار کند است) باشد، مشکل این بود که کد پرسوجو و بهروزرسانی پایگاه داده را پیچیده و انعطافناپذیر میکرد. در هر دو مدل سلسلهمراتبی و شبکهای، اگر مسیری به دادهٔ مورد نظر نداشتید، در وضعیت دشواری بودید. میتوانستید access pathها را تغییر دهید، اما باید کد پرسوجوی دستنویس زیادی را بازنویسی میکردید تا access pathهای جدید را handle کند. تغییر مدل دادهٔ برنامه دشوار بود.
مدل رابطهای
در مقابل، آنچه مدل رابطهای انجام داد این بود که همهٔ داده را آشکار چید: یک relation (جدول) فقط مجموعهای از tupleها (سطرها) است و بس. ساختارهای تودرتوی پیچیدهای نیست، access path پیچیدهای برای دیدن داده نیست. میتوانید هر یا همهٔ سطرهای یک جدول را بخوانید و آنهایی را که شرط دلخواهی را برآورند انتخاب کنید. میتوانید سطر خاصی را با تعیین برخی ستونها بهعنوان key و match روی آنها بخوانید. میتوانید سطر جدیدی در هر جدول درج کنید بدون نگرانی دربارهٔ رابطههای foreign key به و از جداول دیگر.iv
در پایگاه دادهٔ رابطهای، query optimizer بهطور خودکار تصمیم میگیرد کدام بخشهای پرسوجو را به چه ترتیبی اجرا کند و از کدام indexها استفاده کند. این انتخابها در عمل «access path» هستند، اما تفاوت بزرگ این است که توسط query optimizer انتخاب میشوند، نه توسعهدهندهٔ برنامه، پس بهندرت نیاز داریم به آنها فکر کنیم.
iv. محدودیتهای foreign key امکان محدود کردن تغییرات را میدهند، اما چنین محدودیتهایی توسط مدل رابطهای الزامی نیستند. حتی با محدودیتها، join روی foreign keyها در زمان پرسوجو انجام میشود، در حالی که در CODASYL، join در عمل در زمان insert انجام میشد.
اگر بخواهید داده را به روشهای جدید پرسوجو کنید، کافی است index جدید اعلام کنید و پرسوجوها بهطور خودکار از مناسبترین indexها استفاده میکنند. نیازی نیست پرسوجوها را تغییر دهید تا از index جدید بهره ببرید. (همچنین «زبانهای پرسوجو برای داده» در صفحه ۴۲ را ببینید.) مدل رابطهای بنابراین افزودن قابلیتهای جدید به برنامهها را بسیار آسانتر کرد.
query optimizerهای پایگاههای دادهٔ رابطهای موجودات پیچیدهای هستند و سالها تلاش تحقیق و توسعه مصرف کردهاند [18]. اما بینش کلیدی مدل رابطهای این بود: فقط یکبار query optimizer بسازید و سپس همهٔ برنامههایی که از پایگاه داده استفاده میکنند از آن بهره میبرند. اگر query optimizer ندارید، handcode کردن access path برای پرسوجوی خاص از نوشتن optimizer عمومی آسانتر است — اما راهحل عمومی در درازمدت برنده میشود.
مقایسه با پایگاههای دادهٔ سندی
پایگاههای دادهٔ سندی در یک جنبه به مدل سلسلهمراتبی برگشتند: ذخیرهٔ رکوردهای تودرتو (رابطههای یک-به-چند، مانند positions، education و contact_info در شکل ۲-۱) درون رکورد parent بهجای جدول جداگانه.
با این حال، وقتی نوبت به نمایش رابطههای چند-به-یک و چند-به-چند میرسد، پایگاههای دادهٔ رابطهای و سندی از نظر بنیادی متفاوت نیستند: در هر دو، مورد مرتبط با شناسهٔ یکتا ارجاع داده میشود که در مدل رابطهای foreign key و در مدل سندی document reference [9] نامیده میشود. آن شناسه در زمان خواندن با join یا پرسوجوهای follow-up resolve میشود. تا امروز، پایگاههای دادهٔ سندی مسیر CODASYL را دنبال نکردهاند.
پایگاههای دادهٔ رابطهای در برابر سندی امروز
تفاوتهای زیادی برای مقایسهٔ پایگاههای دادهٔ رابطهای و سندی وجود دارد، از جمله ویژگیهای تحمل خطا (فصل ۵ را ببینید) و مدیریت concurrency (فصل ۷ را ببینید). در این فصل فقط روی تفاوتهای مدل داده تمرکز میکنیم.
استدلالهای اصلی به نفع مدل دادهٔ سندی انعطاف schema، عملکرد بهتر بهدلیل locality، و برای برخی برنامهها نزدیکتر بودن به ساختارهای دادهای است که برنامه استفاده میکند. مدل رابطهای با پشتیبانی بهتر از join و رابطههای چند-به-یک و چند-به-چند پاسخ میدهد.
کدام مدل داده به کد برنامهٔ سادهتر منجر میشود؟
اگر داده در برنامهٔ شما ساختار سند-مانند دارد (یعنی درختی از رابطههای یک-به-چند، که معمولاً کل درخت یکجا بارگذاری میشود)، احتمالاً استفاده از مدل سندی ایدهٔ خوبی است. تکنیک shredding رابطهای — تقسیم ساختار سند-مانند به چند جدول (مانند positions، education و contact_info در شکل ۲-۱) — میتواند به schemaهای دستوپاگیر و کد برنامهٔ غیرضروری پیچیده منجر شود.
مدل سندی محدودیتهایی دارد: مثلاً نمیتوانید مستقیماً به آیتم تودرتو درون سند ارجاع دهید، بلکه باید چیزی مانند «آیتم دوم در فهرست positions برای user 251» بگویید (بسیار شبیه access path در مدل سلسلهمراتبی). اما تا وقتی سندها خیلی عمیق تودرتو نباشند، معمولاً مشکل نیست.
پشتیبانی ضعیف join در پایگاههای دادهٔ سندی ممکن است مشکل باشد یا نباشد، بسته به برنامه. مثلاً رابطههای چند-به-چند ممکن است هرگز در برنامهٔ analytics که از پایگاه دادهٔ سندی برای ثبت رویدادهای رخداده در زمانهای مختلف استفاده میکند لازم نباشند [19].
با این حال، اگر برنامهٔ شما از رابطههای چند-به-چند استفاده میکند، مدل سندی کمتر جذاب میشود. میتوان نیاز به join را با denormalization کاهش داد، اما آنگاه کد برنامه باید کار اضافی برای حفظ consistency دادهٔ denormalized انجام دهد. joinها را میتوان در کد برنامه با چند درخواست به پایگاه داده شبیهسازی کرد، اما پیچیدگی را به برنامه منتقل میکند و معمولاً از join انجامشده توسط کد تخصصی درون پایگاه داده کندتر است. در چنین مواردی، استفاده از مدل سندی میتواند به کد برنامهٔ بهمراتب پیچیدهتر و عملکرد بدتر منجر شود [15].
بهطور کلی نمیتوان گفت کدام مدل داده به کد برنامهٔ سادهتر منجر میشود؛ به انواع رابطههای بین آیتمهای داده بستگی دارد. برای دادهٔ بسیار بههمپیوندخورده، مدل سندی ناجور است، مدل رابطهای قابل قبول است، و مدلهای گراف (بخش «مدلهای دادهٔ شبیه گراف» در صفحه ۴۹ را ببینید) طبیعیتریناند.
انعطاف schema در مدل سندی
بیشتر پایگاههای دادهٔ سندی و پشتیبانی JSON در پایگاههای دادهٔ رابطهای هیچ schemaای روی داده در سندها enforce نمیکنند. پشتیبانی XML در پایگاههای دادهٔ رابطهای معمولاً با اعتبارسنجی schema اختیاری همراه است. فقدان schema یعنی key و value دلخواه میتواند به سند اضافه شود، و هنگام خواندن، client تضمینی دربارهٔ فیلدهایی که سندها ممکن است داشته باشند ندارد.
پایگاههای دادهٔ سندی گاهی schemaless نامیده میشوند، اما گمراهکننده است، چون کدی که داده را میخواند معمولاً نوعی ساختار را فرض میکند — یعنی schema ضمنی وجود دارد، اما توسط پایگاه داده enforce نمیشود [20]. اصطلاح دقیقتر schema-on-read (ساختار داده ضمنی است و فقط هنگام خواندن تفسیر میشود) است، در مقابل schema-on-write (رویکرد سنتی پایگاههای دادهٔ رابطهای، که schema صریح است و پایگاه داده اطمینان میدهد همهٔ دادهٔ نوشتهشده با آن مطابقت دارد) [21].
schema-on-read شبیه type checking پویا (runtime) در زبانهای برنامهنویسی است، در حالی که schema-on-write شبیه type checking ایستا (compile-time) است. همانطور که طرفداران type checking ایستا و پویا دربارهٔ مزایای نسبیشان بحثهای بزرگی دارند [22]، enforce کردن schema در پایگاه داده موضوع بحثبرانگیز است و بهطور کلی پاسخ درست یا غلطی وجود ندارد.
تفاوت بین رویکردها بهویژه در موقعیتهایی که برنامه میخواهد قالب داده را تغییر دهد آشکار است. مثلاً فرض کنید اکنون نام کامل هر کاربر را در یک فیلد ذخیره میکنید و میخواهید first name و last name را جداگانه ذخیره کنید [23]. در پایگاه دادهٔ سندی، فقط شروع به نوشتن سندهای جدید با فیلدهای جدید میکنید و کدی در برنامه دارید که هنگام خواندن سندهای قدیمی handle میکند. مثلاً:
javascript
if (user && user.name && !user.first_name) {
// Documents written before Dec 8, 2013 don't have first_name
user.first_name = user.name.split(" ")[0];
}از سوی دیگر، در schema پایگاه داده «type-checked ایستا»، معمولاً migrationی مانند این انجام میدهید:
sql
ALTER TABLE users ADD COLUMN first_name text;
UPDATE users SET first_name = split_part(name, ' ', 1); -- PostgreSQL
UPDATE users SET first_name = substring_index(name, ' ', 1); -- MySQLتغییرات schema شهرت بد کندی و نیاز به downtime دارند. این شهرت کاملاً مستحق نیست: بیشتر سیستمهای پایگاه دادهٔ رابطهای ALTER TABLE را در چند میلیثانیه اجرا میکنند. MySQL استثنای قابل توجه است — کل جدول را در ALTER TABLE کپی میکند که میتواند به معنی دقایق یا حتی ساعت downtime هنگام تغییر جدول بزرگ باشد — اگرچه ابزارهای مختلفی برای دور زدن این محدودیت وجود دارد [24, 25, 26].
اجرای UPDATE روی جدول بزرگ در هر پایگاه داده احتمالاً کند است، چون هر سطر باید بازنویسی شود. اگر قابل قبول نیست، برنامه میتواند first_name را روی پیشفرض NULL بگذارد و هنگام خواندن پر کند، مانند پایگاه دادهٔ سندی.
رویکرد schema-on-read وقتی آیتمهای مجموعه بهدلیلی ساختار یکسان ندارند (یعنی داده heterogeneous است) مزیت دارد — مثلاً بهدلیل:
- انواع مختلفی از اشیاء وجود دارد و عملی نیست هر نوع را در جدول خود قرار دهید.
- ساختار داده توسط سیستمهای خارجی تعیین میشود که کنترلی روی آنها ندارید و ممکن است هر زمان تغییر کنند.
در چنین موقعیتهایی، schema ممکن است بیشتر از کمک آسیب بزند و سندهای schemaless مدل دادهٔ بسیار طبیعیتری باشند. اما وقتی انتظار میرود همهٔ رکوردها ساختار یکسان داشته باشند، schema مکانیزم مفیدی برای مستندسازی و enforce کردن آن ساختار است. schema و schema evolution را در فصل ۴ با جزئیات بیشتر بحث میکنیم.
locality داده برای پرسوجوها
سند معمولاً بهصورت یک رشتهٔ پیوسته ذخیره میشود، با رمزگذاری JSON، XML یا variant باینری آن (مانند BSON MongoDB). اگر برنامهٔ شما اغلب به کل سند نیاز دارد (مثلاً برای render روی صفحهٔ وب)، مزیت عملکردی در این locality ذخیرهسازی وجود دارد. اگر داده در چند جدول تقسیم شده باشد، مانند شکل ۲-۱، برای واکشی همهٔ آن چند index lookup لازم است که ممکن است disk seek بیشتری نیاز داشته باشد و زمان بیشتری ببرد.
مزیت locality فقط وقتی اعمال میشود که به بخشهای بزرگ سند همزمان نیاز داشته باشید. پایگاه داده معمولاً باید کل سند را بارگذاری کند، حتی اگر فقط بخش کوچکی از آن را دسترسی کنید، که روی سندهای بزرگ اتلافگر است. در بهروزرسانی سند، معمولاً کل سند باید بازنویسی شود — فقط تغییراتی که اندازهٔ رمزگذاریشدهٔ سند را تغییر نمیدهند بهراحتی in-place انجام میشوند [19]. به همین دلایل، معمولاً توصیه میشود سندها نسبتاً کوچک بمانند و از نوشتنهایی که اندازهٔ سند را افزایش میدهند اجتناب کنید [9].
این محدودیتهای عملکرد بهطور قابل توجهی مجموعهٔ موقعیتهایی که پایگاههای دادهٔ سندی مفیدند را کاهش میدهند.
ارزش دارد اشاره کنیم ایدهٔ گروهبندی دادهٔ مرتب برای locality محدود به مدل سندی نیست. مثلاً پایگاه دادهٔ Spanner گوگل همان ویژگیهای locality را در مدل دادهٔ رابطهای ارائه میدهد، با اجازه دادن به schema برای اعلام اینکه سطرهای یک جدول باید interleaved (تودرتو) در جدول parent باشند [27]. Oracle با feature به نام multi-table index cluster tables [28] همین کار را میکند. مفهوم column-family در مدل دادهٔ Bigtable (مورد استفاده در Cassandra و HBase) هدف مشابه مدیریت locality را دارد [29].
در فصل ۳ دربارهٔ locality بیشتر میبینیم.
همگرایی پایگاههای دادهٔ سندی و رابطهای
بیشتر سیستمهای پایگاه دادهٔ رابطهای (بهجز MySQL) از اواسط دههٔ ۲۰۰۰ XML را پشتیبانی کردهاند. این شامل توابعی برای تغییر محلی سندهای XML و امکان index و پرسوجو درون سندهای XML است که به برنامهها اجازه میدهد از مدلهای داده بسیار شبیه پایگاه دادهٔ سندی استفاده کنند.
PostgreSQL از نسخهٔ ۹.۳ [8]، MySQL از نسخهٔ ۵.۷، و IBM DB2 از نسخهٔ ۱۰.۵ [30] سطح مشابهی از پشتیبانی سند JSON دارند. با توجه به محبوبیت JSON برای web API، محتمل است پایگاههای دادهٔ رابطهای دیگر هم JSON را اضافه کنند.
در سمت پایگاه دادهٔ سندی، RethinkDB joinهای شبیه رابطهای در زبان پرسوجویش پشتیبانی میکند، و برخی driverهای MongoDB بهطور خودکار database referenceها را resolve میکنند (در عمل client-side join انجام میدهند، اگرچه احتمالاً از join درون پایگاه داده کندتر است چون round-trip شبکهٔ اضافی نیاز دارد و کمتر بهینه است).
به نظر میرسد پایگاههای دادهٔ رابطهای و سندی با گذشت زمان شبیهتر میشوند و این خوب است: مدلهای داده یکدیگر را تکمیل میکنند.v اگر پایگاه داده بتواند دادهٔ سند-مانند را handle کند و همچنین پرسوجوهای رابطهای روی آن انجام دهد، برنامهها میتوانند از ترکیبی از قابلیتها که بهترین تناسب با نیازشان را دارد استفاده کنند.
ترکیب مدل رابطهای و سندی مسیر خوبی برای آیندهٔ پایگاههای داده است.
v. توصیف اصلی Codd از مدل رابطهای [1] در واقع چیزی بسیار شبیه سندهای JSON درون schema رابطهای را مجاز میکرد. آن را nonsimple domains نامید. ایده این بود که مقدار در سطر فقط datatype ابتدایی مانند عدد یا رشته نباشد، بلکه relation تودرتو (جدول) هم باشد — پس میتوانید ساختار درختی بهطور دلخواه تودرتو بهعنوان مقدار داشته باشید، بسیار شبیه پشتیبانی JSON یا XML که بیش از ۳۰ سال بعد به SQL اضافه شد.
زبانهای پرسوجو برای داده
وقتی مدل رابطهای معرفی شد، روش جدیدی برای پرسوجوی داده شامل شد: SQL زبان پرسوجوی declarative است، در حالی که IMS و CODASYL پایگاه داده را با کد imperative پرسوجو میکردند. این یعنی چه؟
بسیاری از زبانهای برنامهنویسی رایج imperative هستند. مثلاً اگر فهرستی از گونههای حیوانات دارید، ممکن است چیزی مانند این بنویسید تا فقط کوسهها را برگرداند:
javascript
function getSharks() {
var sharks = [];
for (var i = 0; i < animals.length; i++) {
if (animals[i].family === "Sharks") {
sharks.push(animals[i]);
}
}
return sharks;
}در جبر رابطهای، بهجای آن مینویسید:
sharks = σfamily = "Sharks" (animals)که در آن σ (حرف یونانی sigma) عملگر انتخاب است و فقط حیواناتی را برمیگرداند که شرط family = "Sharks" را برآورند.
وقتی SQL تعریف شد، ساختار جبر رابطهای را تا حد زیادی دنبال کرد:
sql
SELECT * FROM animals WHERE family = 'Sharks';زبان imperative به رایانه میگوید عملیات مشخصی را به ترتیب مشخص انجام دهد. میتوانید تصور کنید خطبهخط کد را طی میکنید، شرایط را ارزیابی میکنید، متغیرها را بهروز میکنید و تصمیم میگیرید آیا یک دور دیگر حلقه بزنید.
در زبان پرسوجوی declarative، مانند SQL یا جبر رابطهای، فقط الگوی دادهای که میخواهید را مشخص میکنید — نتایج باید چه شرایطی را برآورند و داده چگونه تبدیل شود (مثلاً مرتب، گروهبندی و aggregate) — اما نه چگونه به آن هدف برسید. تصمیم دربارهٔ indexها، روشهای join و ترتیب اجرای بخشهای مختلف پرسوجو بر عهدهٔ query optimizer سیستم پایگاه داده است.
زبان پرسوجوی declarative جذاب است چون معمولاً از API imperative مختصرتر و آسانتر کار کردن است. اما مهمتر، جزئیات پیادهسازی موتور پایگاه داده را پنهان میکند که امکان بهبود عملکرد بدون نیاز به تغییر پرسوجوها را میدهد.
مثلاً در کد imperative نشاندادهشده در ابتدای این بخش، فهرست حیوانات به ترتیب خاصی ظاهر میشود. اگر پایگاه داده بخواهد فضای دیسک استفادهنشده را پشت صحنه reclaim کند، ممکن است نیاز باشد رکوردها را جابهجا کند و ترتیب ظاهر حیوانات را تغییر دهد. آیا پایگاه داده میتواند این کار را بدون شکستن پرسوجوها انجام دهد؟ مثال SQL ترتیب خاصی را تضمین نمیکند و پس از تغییر ترتیب ناراحت نیست. اما اگر پرسوجو بهصورت کد imperative نوشته شده باشد، پایگاه داده هرگز نمیتواند مطمئن باشد کد به ترتیب متکی است یا نه. اینکه SQL در عملکرد محدودتر است به پایگاه داده فضای بیشتری برای بهینهسازی خودکار میدهد.
در نهایت، زبانهای declarative اغلب به اجرای موازی مناسبترند. امروز CPUها با افزودن هستهٔ بیشتر سریعتر میشوند، نه با clock speed بهمراتب بالاتر از قبل [31]. کد imperative موازیسازی روی چند هسته و چند ماشین بسیار سخت است، چون دستوراتی را مشخص میکند که باید به ترتیب خاص انجام شوند. زبانهای declarative شانس بیشتری برای سریعتر شدن در اجرای موازی دارند چون فقط الگوی نتایج را مشخص میکنند، نه الگوریتمی که نتایج را تعیین میکند. پایگاه داده آزاد است اگر مناسب باشد پیادهسازی موازی زبان پرسوجو را به کار بگیرد [32].
پرسوجوهای declarative در وب
مزایای زبانهای پرسوجوی declarative محدود به پایگاههای داده نیست. برای نشان دادن، رویکردهای declarative و imperative را در محیطی کاملاً متفاوت مقایسه کنیم: مرورگر وب.
فرض کنید وبسایتی دربارهٔ حیوانات اقیانوس دارید. کاربر در حال مشاهدهٔ صفحهٔ کوسههاست، پس آیتم ناوبری «Sharks» را بهعنوان انتخابشده علامت میزنید:
html
<ul>
<li class="selected">
<p>Sharks</p>
<ul>
<li>Great White Shark</li>
<li>Tiger Shark</li>
<li>Hammerhead Shark</li>
</ul>
</li>
<li>
<p>Whales</p>
<ul>
<li>Blue Whale</li>
<li>Humpback Whale</li>
<li>Fin Whale</li>
</ul>
</li>
</ul>آیتم انتخابشده با CSS class «selected» علامتگذاری شده.
Sharks عنوان صفحهٔ انتخابشدهٔ فعلی است.
حالا فرض کنید میخواهید عنوان صفحهٔ انتخابشده پسزمینهٔ آبی داشته باشد تا بصری برجسته شود. با CSS آسان است:
css
li.selected > p {
background-color: blue;
}selector CSS li.selected > p الگوی عناصری را که میخواهیم استایل آبی اعمال شود اعلام میکند: همهٔ عناصر p که parent مستقیمشان li با CSS class برابر selected است. عنصر Sharks در مثال با این الگو match میکند، اما Whales match نمیکند چون li parent آن class="selected" ندارد.
اگر بهجای CSS از XSL استفاده میکردید، میتوانستید کار مشابهی انجام دهید:
xml
<xsl:template match="li[@class='selected']/p">
<fo:block background-color="blue">
<xsl:apply-templates/>
</fo:block>
</xsl:template>expression XPath li[@class='selected']/p معادل selector CSS li.selected > p در مثال قبل است. مشترک CSS و XSL این است که هر دو زبان declarative برای مشخص کردن استایل سند هستند.
تصور کنید اگر باید رویکرد imperative استفاده میکردید چه میشد. در JavaScript، با API اصلی Document Object Model (DOM)، نتیجه ممکن است چیزی شبیه این باشد:
javascript
var liElements = document.getElementsByTagName("li");
for (var i = 0; i < liElements.length; i++) {
if (liElements[i].className === "selected") {
var children = liElements[i].childNodes;
for (var j = 0; j < children.length; j++) {
var child = children[j];
if (child.nodeType === Node.ELEMENT_NODE && child.tagName === "P") {
child.setAttribute("style", "background-color: blue");
}
}
}
}این JavaScript بهصورت imperative عنصر Sharks را پسزمینهٔ آبی میدهد، اما کد وحشتناک است. نهتنها بسیار طولانیتر و سختتر از معادل CSS و XSL است، بلکه مشکلات جدی هم دارد:
- اگر class selected حذف شود (مثلاً کاربر صفحهٔ دیگری کلیک کند)، رنگ آبی حذف نمیشود، حتی اگر کد دوباره اجرا شود — و آیتم تا reload کامل صفحه برجسته میماند. با CSS، مرورگر بهطور خودکار تشخیص میدهد وقتی rule
li.selected > pدیگر اعمال نمیشود و بهمحض حذف class selected پسزمینهٔ آبی را حذف میکند. - اگر بخواهید از API جدیدی مانند
document.getElementsByClassName("selected")یا حتیdocument.evaluate()— که ممکن است عملکرد را بهبود دهد — بهره ببرید، باید کد را بازنویسی کنید. از سوی دیگر، فروشندگان مرورگر میتوانند عملکرد CSS و XPath را بدون شکستن سازگاری بهبود دهند.
در مرورگر وب، استفاده از استایل declarative CSS بسیار بهتر از دستکاری imperative استایلها در JavaScript است. بهطور مشابه، در پایگاههای داده، زبانهای پرسوجوی declarative مانند SQL بسیار بهتر از APIهای پرسوجوی imperative از آب درآمدند.vi
vi. IMS و CODASYL هر دو از APIهای پرسوجوی imperative استفاده میکردند. برنامهها معمولاً با کد COBOL رکوردهای پایگاه داده را یکبهیک iterate میکردند [2, 16].
پرسوجوی MapReduce
MapReduce مدل برنامهنویسی برای پردازش حجم زیاد داده بهصورت bulk روی بسیاری ماشین است که توسط گوگل محبوب شد [33]. شکل محدودی از MapReduce توسط برخی datastoreهای NoSQL از جمله MongoDB و CouchDB بهعنوان مکانیزم انجام پرسوجوهای read-only روی بسیاری سند پشتیبانی میشود.
MapReduce بهطور کلی در فصل ۱۰ با جزئیات بیشتر توصیف میشود. فعلاً بهاختصار استفادهٔ MongoDB از این مدل را بحث میکنیم.
MapReduce نه زبان پرسوجوی declarative است و نه API پرسوجوی کاملاً imperative، بلکه جایی بین آنها: منطق پرسوجو با snippetهای کد بیان میشود که توسط framework پردازش مکرراً فراخوانی میشوند. بر پایهٔ توابع map (که collect هم نامیده میشود) و reduce (که fold یا inject هم نامیده میشود) است که در بسیاری زبانهای برنامهنویسی تابعی وجود دارند.
برای مثال، فرض کنید زیستشناس دریایی هستید و هر بار که حیوانات در اقیانوس میبینید یک رکورد observation به پایگاه داده اضافه میکنید. حالا میخواهید گزارشی بسازید که بگوید هر ماه چند کوسه دیدهاید.
در PostgreSQL ممکن است پرسوجو را اینطور بیان کنید:
sql
SELECT date_trunc('month', observation_timestamp) AS observation_month,
sum(num_animals) AS total_animals
FROM observations
WHERE family = 'Sharks'
GROUP BY observation_month;تابع date_trunc('month', timestamp) ماه تقویمی حاوی timestamp را تعیین میکند و timestamp دیگری برمیگرداند که ابتدای آن ماه را نشان میدهد. به عبارت دیگر، timestamp را به نزدیکترین ماه گرد میکند.
این پرسوجو ابتدا observationها را فیلتر میکند تا فقط گونههای خانواده Sharks نمایش داده شوند، سپس observationها را بر حسب ماه تقویمی که در آن رخ دادهاند گروهبندی میکند، و در نهایت تعداد حیوانات دیدهشده در همهٔ observationهای آن ماه را جمع میزند.
همین را میتوان با قابلیت MapReduce MongoDB اینطور بیان کرد:
javascript
db.observations.mapReduce(
function map() {
var year = this.observationTimestamp.getFullYear();
var month = this.observationTimestamp.getMonth() + 1;
emit(year + "-" + month, this.numAnimals);
},
function reduce(key, values) {
return Array.sum(values);
},
{
query: { family: "Sharks" },
out: "monthlySharkReport"
}
);فیلتر برای در نظر گرفتن فقط گونههای کوسه بهصورت declarative مشخص میشود (این extension خاص MongoDB به MapReduce است).
تابع JavaScript map یکبار برای هر سندی که با query match میکند فراخوانی میشود، با this برابر شیء سند.
تابع map یک key (رشتهای شامل سال و ماه، مانند «2013-12» یا «2014-1») و یک value (تعداد حیوانات در آن observation) emit میکند.
جفتهای key-value که map emit میکند بر حسب key گروهبندی میشوند. برای همهٔ جفتهای key-value با همان key (یعنی همان ماه و سال)، تابع reduce یکبار فراخوانی میشود.
تابع reduce تعداد حیوانات از همهٔ observationهای یک ماه خاص را جمع میزند.
خروجی نهایی در collection monthlySharkReport نوشته میشود.
مثلاً فرض کنید collection observations این دو سند را دارد:
json
{
"observationTimestamp": Date.parse("Mon, 25 Dec 1995 12:34:56 GMT"),
"family": "Sharks",
"species": "Carcharodon carcharias",
"numAnimals": 3
}
{
"observationTimestamp": Date.parse("Tue, 12 Dec 1995 16:17:18 GMT"),
"family": "Sharks",
"species": "Carcharias taurus",
"numAnimals": 4
}تابع map یکبار برای هر سند فراخوانی میشود و منجر به emit("1995-12", 3) و emit("1995-12", 4) میشود. سپس تابع reduce با reduce("1995-12", [3, 4]) فراخوانی میشود و ۷ برمیگرداند.
توابع map و reduce تا حدی در آنچه مجازند محدودند. باید pure function باشند، یعنی فقط از دادهای که بهعنوان ورودی به آنها داده شده استفاده کنند، نتوانند پرسوجوی اضافی به پایگاه داده انجام دهند و نباید side effect داشته باشند. این محدودیتها به پایگاه داده اجازه میدهد توابع را هر جا، به هر ترتیبی اجرا کند و در صورت خطا دوباره اجرا کند. با این حال، قدرتمندند: میتوانند رشته parse کنند، توابع کتابخانه فراخوانی کنند، محاسبه انجام دهند و غیره.
MapReduce مدل برنامهنویسی نسبتاً سطح پایینی برای اجرای توزیعشده روی cluster ماشین است. زبانهای پرسوجوی سطح بالاتر مانند SQL میتوانند بهصورت pipeline از عملیات MapReduce پیاده شوند (فصل ۱۰ را ببینید)، اما پیادهسازیهای توزیعشدهٔ زیادی از SQL هم وجود دارد که MapReduce استفاده نمیکنند. توجه کنید چیزی در SQL نیست که آن را به یک ماشین محدود کند، و MapReduce انحصار اجرای پرسوجوی توزیعشده را ندارد.
امکان استفاده از کد JavaScript در وسط پرسوجو برای پرسوجوهای پیشرفته ویژگی عالی است، اما محدود به MapReduce نیست — برخی پایگاههای دادهٔ SQL هم میتوانند با توابع JavaScript extend شوند [34].
مشکل usability با MapReduce این است که باید دو تابع JavaScript هماهنگ با دقت بنویسید که اغلب از نوشتن یک پرسوجوی واحد سختتر است. علاوه بر این، زبان پرسوجوی declarative فرصتهای بیشتری برای query optimizer برای بهبود عملکرد پرسوجو میدهد. به همین دلایل، MongoDB 2.2 از زبان پرسوجوی declarative به نام aggregation pipeline [9] پشتیبانی افزود. در این زبان، همان پرسوجوی شمارش کوسه اینطور است:
javascript
db.observations.aggregate([
{ $match: { family: "Sharks" } },
{ $group: {
_id: {
year: { $year: "$observationTimestamp" },
month: { $month: "$observationTimestamp" }
},
totalAnimals: { $sum: "$numAnimals" }
} }
]);زبان aggregation pipeline از نظر expressiveness شبیه زیرمجموعهای از SQL است، اما syntax مبتنی بر JSON دارد نه syntax شبیه جملهٔ انگلیسی SQL؛ تفاوت شاید مسئلهٔ سلیقه باشد. نتیجهٔ داستان این است که سیستم NoSQL ممکن است ناخواسته SQL را دوباره اختراع کند، هرچند در لباس مبدل.
مدلهای دادهٔ شبیه گراف
قبلاً دیدیم رابطههای چند-به-چند ویژگی متمایزکنندهٔ مهمی بین مدلهای داده مختلف هستند. اگر برنامهٔ شما عمدتاً رابطههای یک-به-چند (دادهٔ درختساختار) دارد یا رابطهای بین رکوردها نیست، مدل سندی مناسب است.
اما اگر رابطههای چند-به-چند در دادهٔ شما بسیار رایج است چه؟ مدل رابطهای میتواند موارد سادهٔ رابطههای چند-به-چند را handle کند، اما با پیچیدهتر شدن اتصالات درون داده، طبیعیتر است داده را بهصورت گراف مدل کنید.
گراف از دو نوع شیء تشکیل شده: vertex (که node یا entity هم نامیده میشود) و edge (که relationship یا arc هم نامیده میشود). انواع زیادی از داده را میتوان بهصورت گراف مدل کرد. مثالهای معمول:
گراف اجتماعی
vertexها مردم هستند و edge نشان میدهد کدام مردم یکدیگر را میشناسند.
گراف وب
vertexها صفحات وب هستند و edge لینکهای HTML به صفحات دیگر را نشان میدهد.
شبکهٔ جاده یا راهآهن
vertexها تقاطعها هستند و edge جادهها یا خطوط راهآهن بین آنها را نشان میدهد.
الگوریتمهای شناختهشده روی این گرافها عمل میکنند: مثلاً سیستمهای مسیریابی خودرو کوتاهترین مسیر بین دو نقطه در شبکهٔ جاده را جستجو میکنند، و PageRank روی گراف وب میتواند محبوبیت صفحهٔ وب و در نتیجه رتبهٔ آن در نتایج جستجو را تعیین کند.
در مثالهای بالا، همهٔ vertexهای گراف نوع یکسانی از چیز را نشان میدهند (بهترتیب مردم، صفحات وب یا تقاطعهای جاده). با این حال، گراف به چنین دادهٔ همگن محدود نیست: استفادهٔ بهاندازهٔ قدرتمند از گراف، ارائهٔ روشی یکنواخت برای ذخیرهٔ انواع کاملاً متفاوت اشیاء در یک datastore واحد است. مثلاً Facebook یک گراف واحد با انواع زیادی vertex و edge نگه میدارد: vertexها مردم، مکانها، رویدادها، checkinها و نظرات کاربران را نشان میدهند؛ edge نشان میدهد کدام مردم با هم دوستاند، کدام checkin در کدام مکان رخ داده، چه کسی روی کدام پست نظر داده، چه کسی در کدام رویداد شرکت کرده و غیره [35].
در این بخش از مثال شکل ۲-۵ استفاده میکنیم. میتواند از شبکهٔ اجتماعی یا پایگاه دادهٔ شجرهنامه باشد: دو نفر Lucy از Idaho و Alain از Beaune، فرانسه را نشان میدهد. آنها ازدواج کردهاند و در London زندگی میکنند.
شکل ۲-۵. مثال دادهٔ ساختاریافتهٔ گراف (مربعها vertex و فلشها edge را نشان میدهند).
چند روش مختلف اما مرتبط برای ساختاردهی و پرسوجوی داده در گراف وجود دارد. در این بخش مدل property graph (پیادهسازیشده توسط Neo4j، Titan و InfiniteGraph) و مدل triple-store (پیادهسازیشده توسط Datomic، AllegroGraph و دیگران) را بحث میکنیم. سه زبان پرسوجوی declarative برای گراف را بررسی میکنیم: Cypher، SPARQL و Datalog. علاوه بر اینها، زبانهای پرسوجوی imperative گراف مانند Gremlin [36] و frameworkهای پردازش گراف مانند Pregel (فصل ۱۰ را ببینید) هم وجود دارند.
گرافهای property
در مدل property graph، هر vertex شامل:
- یک شناسهٔ یکتا
- مجموعهای از edgeهای خروجی
- مجموعهای از edgeهای ورودی
- مجموعهای از propertyها (جفت key-value)
هر edge شامل:
- یک شناسهٔ یکتا
- vertexی که edge از آن شروع میشود (tail vertex)
- vertexی که edge در آن پایان مییابد (head vertex)
- برچسبی برای توصیف نوع رابطه بین دو vertex
- مجموعهای از propertyها (جفت key-value)
میتوانید graph store را متشکل از دو جدول رابطهای تصور کنید، یکی برای vertexها و یکی برای edgeها، همانطور که در مثال ۲-۲ نشان داده شده (این schema از datatype json PostgreSQL برای ذخیرهٔ propertyهای هر vertex یا edge استفاده میکند). head و tail vertex برای هر edge ذخیره میشوند؛ اگر مجموعهٔ edgeهای ورودی یا خروجی یک vertex را بخواهید، میتوانید جدول edges را با head_vertex یا tail_vertex پرسوجو کنید.
مثال ۲-۲. نمایش property graph با schema رابطهای
sql
CREATE TABLE vertices (
vertex_id integer PRIMARY KEY,
properties json
);
CREATE TABLE edges (
edge_id integer PRIMARY KEY,
tail_vertex integer REFERENCES vertices (vertex_id),
head_vertex integer REFERENCES vertices (vertex_id),
label text,
properties json
);
CREATE INDEX edges_tails ON edges (tail_vertex);
CREATE INDEX edges_heads ON edges (head_vertex);برخی جنبههای مهم این مدل:
- هر vertex میتواند edgeای داشته باشد که آن را به هر vertex دیگر وصل کند. schemaای نیست که محدود کند چه نوع چیزهایی میتوانند یا نمیتوانند مرتبط باشند.
- با داشتن هر vertex، میتوانید بهکارآمد edgeهای ورودی و خروجی آن را پیدا کنید و بنابراین گراف را traverse کنید — یعنی مسیر را از زنجیرهای از vertexها هم به جلو و هم به عقب دنبال کنید. (به همین دلیل مثال ۲-۲ index روی ستونهای tail_vertex و head_vertex دارد.)
- با استفاده از برچسبهای مختلف برای انواع مختلف رابطه، میتوانید چند نوع اطلاعات مختلف را در یک گراف واحد ذخیره کنید و همچنان مدل دادهٔ تمیزی داشته باشید.
این ویژگیها انعطاف زیادی برای مدلسازی داده به گراف میدهند، همانطور که در شکل ۲-۵ نشان داده شده. شکل چیزهایی را نشان میدهد که بیان در schema رابطهای سنتی دشوار است، مانند انواع مختلف ساختار منطقهای در کشورهای مختلف (فرانسه département و région دارد، در حالی که US county و state دارد)، عجیبگیریهای تاریخی مانند کشوری درون کشور (فعلاً پیچیدگیهای sovereign state و nation را نادیده میگیریم)، و granularity متفاوت داده (محل سکونت فعلی Lucy بهصورت شهر مشخص شده، در حالی که محل تولدش فقط در سطح state مشخص شده).
میتوانید تصور کنید گراف را گسترش دهید تا حقایق بیشتری دربارهٔ Lucy و Alain یا دیگران شامل شود. مثلاً میتوانید با معرفی vertex برای هر allergen و edge بین شخص و allergen برای نشان دادن allergy، allergyهای غذایی آنها را نشان دهید، و allergenها را با مجموعهای از vertexها که نشان میدهند کدام غذاها چه موادی دارند لینک کنید. آنگاه میتوانید پرسوجویی بنویسید که برای هر شخص چه چیزی امن است برای خوردن. گراف برای قابلیت تکامل (evolvability) خوب است: با افزودن قابلیت به برنامه، گراف بهراحتی میتواند برای سازگاری با تغییرات در ساختارهای دادهٔ برنامه گسترش یابد.
زبان پرسوجوی Cypher
Cypher زبان پرسوجوی declarative برای property graph است که برای پایگاه دادهٔ گراف Neo4j [37] ساخته شد. (بهنام شخصیتی در فیلم The Matrix نامیده شده و ربطی به cipher در رمزنگاری ندارد [38].)
مثال ۲-۳ پرسوجوی Cypher برای درج بخش چپ شکل ۲-۵ در پایگاه دادهٔ گراف را نشان میدهد. بقیهٔ گراف بهطور مشابه اضافه میشود و برای خوانایی حذف شده. هر vertex نام نمادین مانند USA یا Idaho دارد و بخشهای دیگر پرسوجو میتوانند از آن نامها برای ایجاد edge بین vertexها با notation فلش استفاده کنند: (Idaho) -[:WITHIN]-> (USA) edgeای با برچسب WITHIN ایجاد میکند، با Idaho بهعنوان tail node و USA بهعنوان head node.
مثال ۲-۳. زیرمجموعهای از دادهٔ شکل ۲-۵، بهصورت پرسوجوی Cypher
cypher
CREATE
(NAmerica:Location {name:'North America', type:'continent'}),
(USA:Location {name:'United States', type:'country' }),
(Idaho:Location {name:'Idaho', type:'state' }),
(Lucy:Person {name:'Lucy' }),
(Idaho) -[:WITHIN]-> (USA) -[:WITHIN]-> (NAmerica),
(Lucy) -[:BORN_IN]-> (Idaho)وقتی همهٔ vertexها و edgeهای شکل ۲-۵ به پایگاه داده اضافه شدند، میتوانید پرسشهای جالب بپرسید: مثلاً نام همهٔ کسانی که از United States به Europe مهاجرت کردهاند را پیدا کنید. دقیقتر، میخواهیم همهٔ vertexهایی را پیدا کنیم که edge BORN_IN به مکانی در US دارند و همچنین edge LIVING_IN به مکانی در Europe دارند، و property name هر کدام از آن vertexها را برگردانیم.
مثال ۲-۴ نشان میدهد چگونه این پرسوجو در Cypher بیان شود. همان notation فلش در clause MATCH برای یافتن الگو در گراف استفاده میشود: (person) -[:BORN_IN]-> () هر دو vertex را که با edge برچسبدار BORN_IN مرتبطاند match میکند. tail vertex آن edge به متغیر person bind میشود و head vertex بدون نام میماند.
مثال ۲-۴. پرسوجوی Cypher برای یافتن کسانی که از US به Europe مهاجرت کردهاند
cypher
MATCH
(person) -[:BORN_IN]-> () -[:WITHIN*0..]-> (us:Location {name:'United States'}),
(person) -[:LIVES_IN]-> () -[:WITHIN*0..]-> (eu:Location {name:'Europe'})
RETURN person.nameپرسوجو را میتوان اینطور خواند:
هر vertexی (person بنامید) را پیدا کن که هر دو شرط زیر را برآورد:
- person edge خروجی BORN_IN به vertexی دارد. از آن vertex، میتوانید زنجیرهای از edgeهای خروجی WITHIN را دنبال کنید تا در نهایت به vertexی از نوع Location برسید که property name آن برابر «United States» است.
- همان vertex person edge خروجی LIVES_IN دارد. با دنبال کردن آن edge و سپس زنجیرهای از edgeهای خروجی WITHIN، در نهایت به vertexی از نوع Location میرسید که property name آن برابر «Europe» است.
برای هر چنین vertex person، property name را برگردان.
چند روش ممکن برای اجرای پرسوجو وجود دارد. توضیح دادهشده پیشنهاد میکند با scan همهٔ مردم در پایگاه داده شروع کنید، محل تولد و سکونت هر شخص را بررسی کنید و فقط کسانی را برگردانید که معیارها را برآورند. اما بهطور معادل میتوانید از دو vertex Location شروع کنید و به عقب کار کنید. اگر index روی property name باشد، احتمالاً میتوانید بهکارآمد دو vertex نمایندهٔ US و Europe را پیدا کنید. سپس میتوانید همهٔ مکانها (state، region، city و غیره) در US و Europe را با دنبال کردن همهٔ edgeهای WITHIN ورودی پیدا کنید. در نهایت، میتوانید بهدنبال افرادی بگردید که از طریق edge BORN_IN یا LIVES_IN ورودی در یکی از vertexهای مکان یافت میشوند.
همانطور که برای زبان پرسوجوی declarative معمول است، هنگام نوشتن پرسوجو نیازی نیست چنین جزئیات اجرایی را مشخص کنید: query optimizer بهطور خودکار استراتژی پیشبینیشده بهعنوان کارآمدترین را انتخاب میکند، پس میتوانید به نوشتن بقیهٔ برنامه بپردازید.
پرسوجوهای گراف در SQL
مثال ۲-۲ پیشنهاد کرد دادهٔ گراف را میتوان در پایگاه دادهٔ رابطهای نمایش داد. اما اگر دادهٔ گراف را در ساختار رابطهای قرار دهیم، آیا میتوانیم با SQL هم پرسوجو کنیم؟
پاسخ بله است، اما با دشواری. در پایگاه دادهٔ رابطهای، معمولاً از قبل میدانید کدام joinها در پرسوجویتان لازم است. در پرسوجوی گراف، ممکن است نیاز باشد تعداد متغیری edge را traverse کنید قبل از اینکه vertex مورد نظر را پیدا کنید — یعنی تعداد joinها از قبل ثابت نیست.
در مثال ما، این در rule () -[:WITHIN*0..]-> () در پرسوجوی Cypher رخ میدهد. edge LIVES_IN یک شخص ممکن است به هر نوع مکانی اشاره کند: خیابان، شهر، district، region، state و غیره. یک شهر ممکن است WITHIN یک region باشد، region WITHIN یک state، state WITHIN یک country و غیره. edge LIVES_IN ممکن است مستقیماً به vertex مکانی که دنبالش هستید اشاره کند، یا چند سطح در سلسلهمراتب مکان فاصله داشته باشد.
در Cypher، :WITHIN*0.. این واقعیت را بسیار مختصر بیان میکند: یعنی «edge WITHIN را صفر یا بیشتر بار دنبال کن.» مانند عملگر * در regular expression است.
از SQL:1999، این ایدهٔ مسیر traverse با طول متغیر در پرسوجو را میتوان با چیزی به نام recursive common table expressions (syntax WITH RECURSIVE) بیان کرد. مثال ۲-۵ همان پرسوجو — یافتن نام کسانی که از US به Europe مهاجرت کردهاند — را با این تکنیک در SQL نشان میدهد (در PostgreSQL، IBM DB2، Oracle و SQL Server پشتیبانی میشود). با این حال، syntax در مقایسه با Cypher بسیار دستوپاگیر است.
مثال ۲-۵. همان پرسوجوی مثال ۲-۴، بیانشده در SQL با recursive common table expressions
sql
WITH RECURSIVE
-- in_usa is the set of vertex IDs of all locations within the United States
in_usa(vertex_id) AS (
SELECT vertex_id FROM vertices WHERE properties->>'name' = 'United States'
UNION
SELECT edges.tail_vertex FROM edges
JOIN in_usa ON edges.head_vertex = in_usa.vertex_id
WHERE edges.label = 'within'
),
-- in_europe is the set of vertex IDs of all locations within Europe
in_europe(vertex_id) AS (
SELECT vertex_id FROM vertices WHERE properties->>'name' = 'Europe'
UNION
SELECT edges.tail_vertex FROM edges
JOIN in_europe ON edges.head_vertex = in_europe.vertex_id
WHERE edges.label = 'within'
),
-- born_in_usa is the set of vertex IDs of all people born in the US
born_in_usa(vertex_id) AS (
SELECT edges.tail_vertex FROM edges
JOIN in_usa ON edges.head_vertex = in_usa.vertex_id
WHERE edges.label = 'born_in'
),
-- lives_in_europe is the set of vertex IDs of all people living in Europe
lives_in_europe(vertex_id) AS (
SELECT edges.tail_vertex FROM edges
JOIN in_europe ON edges.head_vertex = in_europe.vertex_id
WHERE edges.label = 'lives_in'
)
SELECT vertices.properties->>'name'
FROM vertices
-- join to find those people who were both born in the US *and* live in Europe
JOIN born_in_usa ON vertices.vertex_id = born_in_usa.vertex_id
JOIN lives_in_europe ON vertices.vertex_id = lives_in_europe.vertex_id;ابتدا vertexی که property name آن مقدار «United States» دارد پیدا کنید و آن را اولین عنصر مجموعهٔ vertexهای in_usa قرار دهید.
همهٔ edgeهای within ورودی از vertexهای مجموعه in_usa را دنبال کنید و آنها را به همان مجموعه اضافه کنید، تا همهٔ edgeهای within ورودی visit شوند.
همین کار را با vertexی که property name آن مقدار «Europe» دارد شروع کنید و مجموعه vertexهای in_europe را بسازید.
برای هر vertex در مجموعه in_usa، edgeهای born_in ورودی را دنبال کنید تا افرادی که در جایی در United States متولد شدهاند پیدا شوند.
بهطور مشابه، برای هر vertex در مجموعه in_europe، edgeهای lives_in ورودی را دنبال کنید تا افرادی که در Europe زندگی میکنند پیدا شوند.
در نهایت، مجموعهٔ افراد متولد در USA را با مجموعهٔ افراد زندگیکننده در Europe با join تقاطع دهید.
اگر همان پرسوجو را بتوان در ۴ خط در یک زبان پرسوجو نوشت اما در دیگری به ۲۹ خط نیاز باشد، فقط نشان میدهد مدلهای داده مختلف برای موارد استفادهٔ متفاوت طراحی شدهاند. انتخاب مدل داده مناسب برای برنامه مهم است.
triple-storeها و SPARQL
مدل triple-store عمدتاً معادل مدل property graph است، با کلمات مختلف برای توصیف همان ایدهها. با این حال، ارزش بحث دارد، چون ابزارها و زبانهای مختلفی برای triple-store وجود دارد که میتواند افزودنی ارزشمند به جعبهابزار ساخت برنامه باشد.
در triple-store، همهٔ اطلاعات بهصورت statementهای سهبخشی بسیار ساده ذخیره میشود: (subject, predicate, object). مثلاً در triple (Jim, likes, bananas)، Jim subject، likes predicate (فعل) و bananas object است.
subject یک triple معادل vertex در گراف است. object یکی از دو چیز است:
- مقداری در datatype ابتدایی، مانند رشته یا عدد. در آن صورت، predicate و object triple معادل key و value یک property روی subject vertex هستند. مثلاً (lucy, age, 33) مانند vertex lucy با propertyهای
{"age":33}است. - vertex دیگری در گراف. در آن صورت، predicate edge در گراف است، subject tail vertex و object head vertex. مثلاً در (lucy, marriedTo, alain) subject و object lucy و alain هر دو vertex هستند و predicate marriedTo برچسب edgeای است که آنها را وصل میکند.
مثال ۲-۶ همان دادهٔ مثال ۲-۳ را نشان میدهد، بهصورت triple در قالب Turtle، زیرمجموعهای از Notation3 (N3) [39].
مثال ۲-۶. زیرمجموعهای از دادهٔ شکل ۲-۵، بهصورت tripleهای Turtle
@prefix : <urn:example:>.
_:lucy a :Person.
_:lucy :name "Lucy".
_:lucy :bornIn _:idaho.
_:idaho a :Location.
_:idaho :name "Idaho".
_:idaho :type "state".
_:idaho :within _:usa.
_:usa a :Location.
_:usa :name "United States".
_:usa :type "country".
_:usa :within _:namerica.
_:namerica a :Location.
_:namerica :name "North America".
_:namerica :type "continent".در این مثال، vertexهای گراف بهصورت _:someName نوشته میشوند. نام خارج از این فایل معنا ندارد؛ فقط وجود دارد چون وگرنه نمیدانستیم کدام tripleها به همان vertex اشاره میکنند. وقتی predicate edge را نشان میدهد، object یک vertex است، مانند _:idaho :within _:usa. وقتی predicate یک property است، object literal رشتهای است، مانند _:usa :name "United States".
تکرار همان subject بارها خستهکننده است، اما خوشبختانه میتوانید از semicolon برای گفتن چند چیز دربارهٔ همان subject استفاده کنید. این قالب Turtle را بسیار خوانا میکند: مثال ۲-۷ را ببینید.
مثال ۲-۷. روش مختصرتر نوشتن دادهٔ مثال ۲-۶
@prefix : <urn:example:>.
_:lucy a :Person; :name "Lucy"; :bornIn _:idaho.
_:idaho a :Location; :name "Idaho"; :type "state"; :within _:usa.
_:usa a :Location; :name "United States"; :type "country"; :within _:namerica.
_:namerica a :Location; :name "North America"; :type "continent".وب معنایی
اگر بیشتر دربارهٔ triple-store بخوانید، ممکن است در گرداب مقالاتی دربارهٔ semantic web بیفتید. مدل دادهٔ triple-store کاملاً مستقل از semantic web است — مثلاً Datomic [40] triple-store است که ادعا نمیکند ربطی به آن دارد.vii اما چون دو موضوع در ذهن بسیاری از مردم بههم گره خوردهاند، باید بهاختصار بحث کنیم.
semantic web در اصل ایدهای ساده و معقول است: وبسایتها از قبل اطلاعات را بهصورت متن و تصویر برای خواندن انسان منتشر میکنند، پس چرا اطلاعات را بهصورت دادهٔ machine-readable برای خواندن رایانه هم منتشر نکنند؟ Resource Description Framework (RDF) [41] بهعنوان مکانیزمی برای انتشار داده توسط وبسایتهای مختلف در قالب یکنواخت در نظر گرفته شد که امکان ترکیب خودکار داده از وبسایتهای مختلف در web of data — نوعی «پایگاه دادهٔ همهچیز» در مقیاس اینترنت — را میداد.
متأسفانه، semantic web در اوایل دههٔ ۲۰۰۰ بیش از حد hype شد اما تا امروز نشانهای از تحقق عملی نشان نداده که بسیاری را نسبت به آن بدبین کرده. همچنین از انبوه acronymها، پیشنهادهای استاندارد بیش از حد پیچیده و hubris رنج برده.
با این حال، اگر از آن شکستها بگذرید، کار خوب زیادی هم از پروژهٔ semantic web بیرون آمده. tripleها میتوانند مدل دادهٔ داخلی خوبی برای برنامهها باشند، حتی اگر علاقهای به انتشار دادهٔ RDF روی semantic web ندارید.
vii. از نظر فنی، Datomic بهجای triple از 5-tuple استفاده میکند؛ دو فیلد اضافی metadata برای versioning هستند.
مدل دادهٔ RDF
زبان Turtle که در مثال ۲-۷ استفاده کردیم قالب human-readable برای دادهٔ RDF است. گاهی RDF در قالب XML هم نوشته میشود که همان کار را بسیار verboseتر انجام میدهد — مثال ۲-۸ را ببینید. Turtle/N3 ترجیح دارد چون بسیار راحتتر برای چشم است و ابزارهایی مانند Apache Jena [42] در صورت نیاز میتوانند بین قالبهای مختلف RDF تبدیل کنند.
مثال ۲-۸. دادهٔ مثال ۲-۷، بیانشده با syntax RDF/XML
xml
<rdf:RDF xmlns="urn:example:"
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#">
<Location rdf:nodeID="idaho">
<name>Idaho</name>
<type>state</type>
<within>
<Location rdf:nodeID="usa">
<name>United States</name>
<type>country</type>
<within>
<Location rdf:nodeID="namerica">
<name>North America</name>
<type>continent</type>
</Location>
</within>
</Location>
</within>
</Location>
<Person rdf:nodeID="lucy">
<name>Lucy</name>
<bornIn rdf:nodeID="idaho"/>
</Person>
</rdf:RDF>RDF بهدلیل طراحی برای تبادل داده در مقیاس اینترنت چند عجیبگیری دارد. subject، predicate و object یک triple اغلب URI هستند. مثلاً predicate ممکن است URIای مانند http://my-company.com/namespace#within یا http://my-company.com/namespace#lives_in باشد، نه فقط WITHIN یا LIVES_IN. منطق پشت این طراحی این است که باید بتوانید دادهٔ خود را با دادهٔ شخص دیگر ترکیب کنید، و اگر آنها معنای متفاوتی به کلمهٔ within یا lives_in بدهند، conflict نمیگیرید چون predicateهای آنها در واقع http://other.org/foo#within و http://other.org/foo#lives_in هستند.
URL http://my-company.com/namespace لزوماً به چیزی resolve نمیشود — از دید RDF، فقط namespace است. برای اجتناب از سردرگمی با URLهای http://، مثالهای این بخش از URIهای non-resolvable مانند urn:example:within استفاده میکنند. خوشبختانه میتوانید این prefix را یکبار در بالای فایل مشخص کنید و بعد فراموش کنید.
زبان پرسوجوی SPARQL
SPARQL زبان پرسوجو برای triple-storeها با مدل دادهٔ RDF [43] است. (مخفف SPARQL Protocol and RDF Query Language است، تلفظ «sparkle».) از Cypher قدیمیتر است و چون pattern matching Cypher از SPARQL وام گرفته، بسیار شبیه به نظر میرسند [37].
همان پرسوجوی قبل — یافتن کسانی که از US به Europe نقلمکان کردهاند — در SPARQL حتی از Cypher هم مختصرتر است (مثال ۲-۹ را ببینید).
مثال ۲-۹. همان پرسوجوی مثال ۲-۴، بیانشده در SPARQL
sparql
PREFIX : <urn:example:>
SELECT ?personName WHERE {
?person :name ?personName.
?person :bornIn / :within* / :name "United States".
?person :livesIn / :within* / :name "Europe".
}ساختار بسیار شبیه است. این دو expression معادلاند (متغیرها در SPARQL با علامت سؤال شروع میشوند):
(person) -[:BORN_IN]-> () -[:WITHIN*0..]-> (location) # Cypher
?person :bornIn / :within* ?location. # SPARQLچون RDF بین property و edge تمایز قائل نمیشود و فقط از predicate برای هر دو استفاده میکند، میتوانید همان syntax را برای match کردن propertyها به کار ببرید. در expression زیر، متغیر usa به هر vertexی bind میشود که property name با مقدار رشتهٔ «United States» دارد:
(usa {name:'United States'}) # Cypher
?usa :name "United States". # SPARQLSPARQL زبان پرسوجوی خوبی است — حتی اگر semantic web هرگز محقق نشود، میتواند ابزار قدرتمندی برای استفادهٔ داخلی برنامهها باشد.
پایگاههای دادهٔ گراف در مقایسه با مدل شبکهای
در «آیا پایگاههای دادهٔ سندی تاریخ را تکرار میکنند؟» در صفحه ۳۶ بحث کردیم CODASYL و مدل رابطهای برای حل مسئلهٔ رابطههای چند-به-چند در IMS رقابت کردند. در نگاه اول، مدل شبکهای CODASYL شبیه مدل گراف به نظر میرسد. آیا پایگاههای دادهٔ گراف CODASYL در لباس مبدل بازگشتهاند؟
نه. در چند جنبهٔ مهم متفاوتاند:
- در CODASYL، پایگاه داده schema داشت که مشخص میکرد کدام record type میتواند در کدام record type دیگر تودرتو باشد. در پایگاه دادهٔ گراف چنین محدودیتی نیست: هر vertex میتواند edge به هر vertex دیگر داشته باشد. این انعطاف بسیار بیشتری برای adapt برنامهها به نیازمندیهای در حال تغییر میدهد.
- در CODASYL، تنها راه رسیدن به record خاص، traverse یکی از access pathها به آن بود. در پایگاه دادهٔ گراف، میتوانید مستقیماً با ID یکتا به هر vertex ارجاع دهید، یا از index برای یافتن vertex با مقدار خاص استفاده کنید.
- در CODASYL، فرزندان یک record مجموعهٔ مرتب بودند، پس پایگاه داده باید آن ترتیب را نگه میداشت (که پیامدهایی برای layout ذخیرهسازی داشت) و برنامههایی که record جدید درج میکردند باید نگران موقعیت recordهای جدید در این مجموعهها بودند. در پایگاه دادهٔ گراف، vertexها و edgeها مرتب نیستند (فقط هنگام پرسوجو میتوانید نتایج را مرتب کنید).
- در CODASYL، همهٔ پرسوجوها imperative بودند، نوشتنشان دشوار و بهراحتی با تغییر schema میشکست. در پایگاه دادهٔ گراف، اگر بخواهید میتوانید traversal را imperative بنویسید، اما بیشتر پایگاههای دادهٔ گراف زبانهای پرسوجوی declarative سطح بالا مانند Cypher یا SPARQL هم پشتیبانی میکنند.
بنیاد: Datalog
Datalog زبان بسیار قدیمیتر از SPARQL یا Cypher است که در دههٔ ۱۹۸۰ توسط academia بهطور گسترده مطالعه شد [44, 45, 46]. در میان مهندسان نرمافزار کمتر شناختهشده است، اما مهم است چون بنیادی است که زبانهای پرسوجوی بعدی روی آن ساخته شدهاند.
در عمل، Datalog در چند سیستم داده استفاده میشود: مثلاً زبان پرسوجوی Datomic [40] است و Cascalog [47] پیادهسازی Datalog برای پرسوجوی مجموعهدادههای بزرگ در Hadoop است.viii
viii. Datomic و Cascalog از syntax S-expression Clojure برای Datalog استفاده میکنند. در مثالهای زیر از syntax Prolog استفاده میکنیم که کمی خواناتر است، اما از نظر عملکرد تفاوتی ندارد.
مدل دادهٔ Datalog شبیه مدل triple-store است، کمی تعمیمیافته. بهجای نوشتن triple بهصورت (subject, predicate, object)، مینویسیم predicate(subject, object). مثال ۲-۱۰ نشان میدهد چگونه دادهٔ مثال ما را در Datalog بنویسیم.
مثال ۲-۱۰. زیرمجموعهای از دادهٔ شکل ۲-۵، بهصورت factهای Datalog
name(namerica, 'North America').
type(namerica, continent).
name(usa, 'United States').
type(usa, country).
within(usa, namerica).
name(idaho, 'Idaho').
type(idaho, state).
within(idaho, usa).
name(lucy, 'Lucy').
born_in(lucy, idaho).حالا که داده را تعریف کردیم، میتوانیم همان پرسوجوی قبل را بنویسیم، همانطور که در مثال ۲-۱۱ نشان داده شده. کمی با معادل Cypher یا SPARQL متفاوت به نظر میرسد، اما نگذارید این شما را دلسرد کند. Datalog زیرمجموعهای از Prolog است که اگر علوم کامپیوتر خوانده باشید ممکن است قبلاً دیده باشید.
مثال ۲-۱۱. همان پرسوجوی مثال ۲-۴، بیانشده در Datalog
within_recursive(Location, Name) :- name(Location, Name). /* Rule 1 */
within_recursive(Location, Name) :- within(Location, Via), /* Rule 2 */
within_recursive(Via, Name).
migrated(Name, BornIn, LivingIn) :- name(Person, Name), /* Rule 3 */
born_in(Person, BornLoc),
within_recursive(BornLoc, BornIn),
lives_in(Person, LivingLoc),
within_recursive(LivingLoc, LivingIn).
?- migrated(Who, 'United States', 'Europe').
/* Who = 'Lucy'. */Cypher و SPARQL بلافاصله با SELECT شروع میکنند، اما Datalog گامبهگام پیش میرود. ruleهایی تعریف میکنیم که به پایگاه داده دربارهٔ predicateهای جدید میگویند: اینجا دو predicate جدید within_recursive و migrated تعریف میکنیم. این predicateها triple ذخیرهشده در پایگاه داده نیستند، بلکه از داده یا ruleهای دیگر derive میشوند. ruleها میتوانند به ruleهای دیگر ارجاع دهند، درست مثل توابعی که توابع دیگر را فراخوانی یا بازگشتی خود را فراخوانی میکنند. به این ترتیب، پرسوجوهای پیچیده گامبهگام ساخته میشوند.
در ruleها، کلماتی که با حرف بزرگ شروع میشوند متغیرند و predicateها مانند Cypher و SPARQL match میشوند. مثلاً name(Location, Name) triple name(namerica, 'North America') را با bindingهای Location = namerica و Name = 'North America' match میکند.
rule وقتی اعمال میشود که سیستم بتواند برای همهٔ predicateهای سمت راست عملگر :- match پیدا کند. وقتی rule اعمال میشود، گویی سمت چپ :- به پایگاه داده اضافه شده (با جایگزینی متغیرها با مقادیر matchشده).
یک روش ممکن برای اعمال ruleها این است:
name(namerica, 'North America')در پایگاه داده وجود دارد، پس rule 1 اعمال میشود.within_recursive(namerica, 'North America')تولید میکند.within(usa, namerica)در پایگاه داده وجود دارد و گام قبلیwithin_recursive(namerica, 'North America')تولید کرد، پس rule 2 اعمال میشود.within_recursive(usa, 'North America')تولید میکند.within(idaho, usa)در پایگاه داده وجود دارد و گام قبلیwithin_recursive(usa, 'North America')تولید کرد، پس rule 2 اعمال میشود.within_recursive(idaho, 'North America')تولید میکند.
با اعمال مکرر ruleهای 1 و 2، predicate within_recursive میتواند همهٔ مکانهای North America (یا هر نام مکان دیگر) موجود در پایگاه داده را بگوید. این فرایند در شکل ۲-۶ نشان داده شده.
شکل ۲-۶. تعیین اینکه Idaho در North America است، با ruleهای Datalog از مثال ۲-۱۱.
حالا rule 3 میتواند افرادی را پیدا کند که در مکانی BornIn متولد شده و در مکانی LivingIn زندگی میکنند. با پرسوجو با BornIn = 'United States' و LivingIn = 'Europe' و گذاشتن person بهعنوان متغیر Who، از سیستم Datalog میخواهیم بفهمد چه مقادیری میتواند برای متغیر Who ظاهر شود. پس در نهایت همان پاسخ Cypher و SPARQL را میگیریم.
رویکرد Datalog نوع متفاوتی از تفکر نسبت به زبانهای پرسوجوی دیگر این فصل میطلبد، اما بسیار قدرتمند است چون ruleها را میتوان ترکیب و در پرسوجوهای مختلف reuse کرد. برای پرسوجوهای سادهٔ یکباره کمتر راحت است، اما اگر دادهٔ شما پیچیده است بهتر کنار میآید.
جمعبندی
مدلهای داده موضوع گستردهای هستند و در این فصل نگاه سریعی به انواع مختلف مدلها انداختیم. فضا برای ورود به جزئیات همهٔ مدلها نبود، اما امیدواریم مرور کافی بوده تا اشتیاق شما را برای یافتن مدلی که بهترین تناسب با نیاز برنامهتان را دارد برانگیزد.
از نظر تاریخی، داده ابتدا بهصورت یک درخت بزرگ (مدل سلسلهمراتبی) نمایش داده میشد، اما برای نمایش رابطههای چند-به-چند مناسب نبود، پس مدل رابطهای برای حل آن مسئله اختراع شد. اخیراً توسعهدهندگان یافتند برخی برنامهها در مدل رابطهای هم جا نمیشوند. datastoreهای غیررابطهای «NoSQL» جدید در دو جهت اصلی منشعب شدهاند:
- پایگاههای دادهٔ سندی موارد استفادهای را هدف میگیرند که داده بهصورت سندهای خودکفا میآید و رابطه بین یک سند و سند دیگر نادر است.
- پایگاههای دادهٔ گراف در جهت مخالف میروند و موارد استفادهای را هدف میگیرند که هر چیز بالقوه به همهچیز مرتبط است.
هر سه مدل (سندی، رابطهای و گراف) امروز بهطور گسترده استفاده میشوند و هر کدام در حوزهٔ خود خوب است. یک مدل را میتوان بر حسب مدل دیگر emulate کرد — مثلاً دادهٔ گراف را میتوان در پایگاه دادهٔ رابطهای نمایش داد — اما نتیجه اغلب ناجور است. به همین دلیل سیستمهای مختلف برای اهداف مختلف داریم، نه یک راهحل one-size-fits-all.
چیزی که مدلهای سندی و گراف مشترک دارند این است که معمولاً schema برای دادهای که ذخیره میکنند enforce نمیکنند، که adapt برنامهها به نیازمندیهای در حال تغییر را آسانتر میکند. با این حال، برنامهٔ شما احتمالاً هنوز فرض میکند داده ساختار مشخصی دارد؛ فقط مسئله این است که schema صریح (enforce در نوشتن) است یا ضمنی (handle در خواندن).
هر مدل داده با زبان پرسوجو یا framework خود همراه است و چند مثال بحث کردیم: SQL، MapReduce، aggregation pipeline MongoDB، Cypher، SPARQL و Datalog. همچنین به CSS و XSL/XPath — که زبان پرسوجوی پایگاه داده نیستند اما شباهتهای جالبی دارند — اشاره کردیم.
اگرچه زمین زیادی را پوشش دادیم، هنوز مدلهای دادهٔ زیادی بدون اشاره ماندهاند. فقط چند مثال کوتاه:
- محققان کار با دادهٔ genome اغلب نیاز به جستجوی sequence-similarity دارند، یعنی یک رشتهٔ بسیار بلند (نمایندهٔ مولکول DNA) را با پایگاه دادهٔ بزرگی از رشتههای مشابه اما غیر یکسان match کنند. هیچیک از پایگاههای دادهٔ توصیفشده اینجا این کاربرد را handle نمیکند، به همین دلیل محققان نرمافزار تخصصی پایگاه دادهٔ genome مانند GenBank [48] نوشتهاند.
- فیزیکدانان ذرات دهههاست تحلیل داده در سبک Big Data انجام میدهند و پروژههایی مانند Large Hadron Collider (LHC) اکنون با صدها petabyte کار میکنند! در چنین مقیاسی راهحلهای سفارشی لازم است تا هزینهٔ سختافزار از کنترل خارج نشود [49].
- جستجوی full-text بهطور بحثبرانگیز نوعی مدل داده است که اغلب در کنار پایگاههای داده استفاده میشود. بازیابی اطلاعات موضوع تخصصی بزرگی است که در این کتاب با جزئیات زیاد پوشش نمیدهیم، اما در فصل ۳ و بخش سوم به search indexها اشاره میکنیم.
فعلاً همینجا متوقف میشویم. در فصل بعد trade-offهایی را بحث میکنیم که هنگام پیادهسازی مدلهای دادهٔ توصیفشده در این فصل مطرح میشوند.
منابع
[1] Edgar F. Codd: «A Relational Model of Data for Large Shared Data Banks,» Communications of the ACM, volume 13, number 6, pages 377–387, June 1970. doi: 10.1145/362384.362685
[2] Michael Stonebraker and Joseph M. Hellerstein: «What Goes Around Comes Around,» in Readings in Database Systems, 4th edition, MIT Press, pages 2–41, 2005. ISBN: 978-0-262-69314-1
[3] Pramod J. Sadalage and Martin Fowler: NoSQL Distilled. Addison-Wesley, August 2012. ISBN: 978-0-321-82662-6
[4] Eric Evans: «NoSQL: What's in a Name?,» blog.sym-link.com, October 30, 2009.
[5] James Phillips: «Surprises in Our NoSQL Adoption Survey,» blog.couchbase.com, February 8, 2012.
[6] Michael Wagner: SQL/XML:2006 – Evaluierung der Standardkonformität ausgewählter Datenbanksysteme. Diplomica Verlag, Hamburg, 2010. ISBN: 978-3-836-64609-3
[7] «XML Data in SQL Server,» SQL Server 2012 documentation, technet.microsoft.com, 2013.
[8] «PostgreSQL 9.3.1 Documentation,» The PostgreSQL Global Development Group, 2013.
[9] «The MongoDB 2.4 Manual,» MongoDB, Inc., 2013.
[10] «RethinkDB 1.11 Documentation,» rethinkdb.com, 2013.
[11] «Apache CouchDB 1.6 Documentation,» docs.couchdb.org, 2014.
[12] Lin Qiao, Kapil Surlaker, Shirshanka Das, et al.: «On Brewing Fresh Espresso: LinkedIn's Distributed Data Serving Platform,» at ACM International Conference on Management of Data (SIGMOD), June 2013.
[13] Rick Long, Mark Harrington, Robert Hain, and Geoff Nicholls: IMS Primer. IBM Redbook SG24-5352-00, IBM International Technical Support Organization, January 2000.
[14] Stephen D. Bartlett: «IBM's IMS—Myths, Realities, and Opportunities,» The Clipper Group Navigator, TCG2013015LI, July 2013.
[15] Sarah Mei: «Why You Should Never Use MongoDB,» sarahmei.com, November 11, 2013.
[16] J. S. Knowles and D. M. R. Bell: «The CODASYL Model,» in Databases—Role and Structure: An Advanced Course, edited by P. M. Stocker, P. M. D. Gray, and M. P. Atkinson, pages 19–56, Cambridge University Press, 1984. ISBN: 978-0-521-25430-4
[17] Charles W. Bachman: «The Programmer as Navigator,» Communications of the ACM, volume 16, number 11, pages 653–658, November 1973. doi: 10.1145/355611.362534
[18] Joseph M. Hellerstein, Michael Stonebraker, and James Hamilton: «Architecture of a Database System,» Foundations and Trends in Databases, volume 1, number 2, pages 141–259, November 2007. doi: 10.1561/1900000002
[19] Sandeep Parikh and Kelly Stirman: «Schema Design for Time Series Data in MongoDB,» blog.mongodb.org, October 30, 2013.
[20] Martin Fowler: «Schemaless Data Structures,» martinfowler.com, January 7, 2013.
[21] Amr Awadallah: «Schema-on-Read vs. Schema-on-Write,» at Berkeley EECS RAD Lab Retreat, Santa Cruz, CA, May 2009.
[22] Martin Odersky: «The Trouble with Types,» at Strange Loop, September 2013.
[23] Conrad Irwin: «MongoDB—Confessions of a PostgreSQL Lover,» at HTML5DevConf, October 2013.
[24] «Percona Toolkit Documentation: pt-online-schema-change,» Percona Ireland Ltd., 2013.
[25] Rany Keddo, Tobias Bielohlawek, and Tobias Schmidt: «Large Hadron Migrator,» SoundCloud, 2013.
[26] Shlomi Noach: «gh-ost: GitHub's Online Schema Migration Tool for MySQL,» githubengineering.com, August 1, 2016.
[27] James C. Corbett, Jeffrey Dean, Michael Epstein, et al.: «Spanner: Google's Globally-Distributed Database,» at 10th USENIX Symposium on Operating System Design and Implementation (OSDI), October 2012.
[28] Donald K. Burleson: «Reduce I/O with Oracle Cluster Tables,» dba-oracle.com.
[29] Fay Chang, Jeffrey Dean, Sanjay Ghemawat, et al.: «Bigtable: A Distributed Storage System for Structured Data,» at 7th USENIX Symposium on Operating System Design and Implementation (OSDI), November 2006.
[30] Bobbie J. Cochrane and Kathy A. McKnight: «DB2 JSON Capabilities, Part 1: Introduction to DB2 JSON,» IBM developerWorks, June 20, 2013.
[31] Herb Sutter: «The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software,» Dr. Dobb's Journal, volume 30, number 3, pages 202-210, March 2005.
[32] Joseph M. Hellerstein: «The Declarative Imperative: Experiences and Conjectures in Distributed Logic,» Electrical Engineering and Computer Sciences, University of California at Berkeley, Tech report UCB/EECS-2010-90, June 2010.
[33] Jeffrey Dean and Sanjay Ghemawat: «MapReduce: Simplified Data Processing on Large Clusters,» at 6th USENIX Symposium on Operating System Design and Implementation (OSDI), December 2004.
[34] Craig Kerstiens: «JavaScript in Your Postgres,» blog.heroku.com, June 5, 2013.
[35] Nathan Bronson, Zach Amsden, George Cabrera, et al.: «TAO: Facebook's Distributed Data Store for the Social Graph,» at USENIX Annual Technical Conference (USENIX ATC), June 2013.
[36] «Apache TinkerPop3.2.3 Documentation,» tinkerpop.apache.org, October 2016.
[37] «The Neo4j Manual v2.0.0,» Neo Technology, 2013.
[38] Emil Eifrem: Twitter correspondence, January 3, 2014.
[39] David Beckett and Tim Berners-Lee: «Turtle – Terse RDF Triple Language,» W3C Team Submission, March 28, 2011.
[40] «Datomic Development Resources,» Metadata Partners, LLC, 2013.
[41] W3C RDF Working Group: «Resource Description Framework (RDF),» w3.org, 10 February 2004.
[42] «Apache Jena,» Apache Software Foundation.
[43] Steve Harris, Andy Seaborne, and Eric Prud'hommeaux: «SPARQL 1.1 Query Language,» W3C Recommendation, March 2013.
[44] Todd J. Green, Shan Shan Huang, Boon Thau Loo, and Wenchao Zhou: «Datalog and Recursive Query Processing,» Foundations and Trends in Databases, volume 5, number 2, pages 105–195, November 2013. doi: 10.1561/1900000017
[45] Stefano Ceri, Georg Gottlob, and Letizia Tanca: «What You Always Wanted to Know About Datalog (And Never Dared to Ask),» IEEE Transactions on Knowledge and Data Engineering, volume 1, number 1, pages 146–166, March 1989. doi: 10.1109/69.43410
[46] Serge Abiteboul, Richard Hull, and Victor Vianu: Foundations of Databases. Addison-Wesley, 1995. ISBN: 978-0-201-53771-0, available online at webdam.inria.fr/Alice
[47] Nathan Marz: «Cascalog,» cascalog.org.
[48] Dennis A. Benson, Ilene Karsch-Mizrachi, David J. Lipman, et al.: «GenBank,» Nucleic Acids Research, volume 36, Database issue, pages D25–D30, December 2007. doi: 10.1093/nar/gkm929
[49] Fons Rademakers: «ROOT for Big Data Analysis,» at Workshop on the Future of Big Data Management, London, UK, June 2013.