Retroactive data structure
کمپیوٹر سائنس میں ریٹرو ایکٹیو ڈیٹا اسٹرکچر ایک ڈیٹا اسٹرکچر ہے جو اسٹرکچر پر انجام دی گئی کارروائیوں کے سلسلے میں موثر تبدیلیوں کی حمایت کرتا ہے۔ یہ تبدیلیاں ماضی میں کسی وقت انجام دیے گئے آپریشن کو ریٹرو ایکٹیو انسرشن، ڈیلیٹ یا اپ ڈیٹ کرنے کی شکل اختیار کر سکتی ہیں۔ ریٹرو ایکٹیو ڈیٹا ڈھانچے کی کچھ ایپلی کیشنز حقیقی دنیا میں بہت سے ایسے معاملات ہیں جہاں کوئی ماضی کے آپریشن کو کارروائیوں کے سلسلے سے تبدیل کرنا چاہے گا۔ ذیل میں کچھ ممکنہ ایپلی کیشنز درج ہیں: غلطی کی اصلاح: ڈیٹا کا غلط ان پٹ۔ ڈیٹا کو درست کیا جانا چاہیے اور غلط ڈیٹا کے تمام ثانوی اثرات کو ہٹا دیا جانا چاہیے۔ خراب ڈیٹا: بڑے سسٹمز سے نمٹتے وقت، خاص طور پر جن میں بڑی مقدار میں خودکار ڈیٹا کی منتقلی شامل ہوتی ہے، یہ کوئی غیر معمولی بات نہیں ہے۔ مثال کے طور پر، فرض کریں کہ موسمی نیٹ ورک کی خرابی کے لیے سینسرز میں سے ایک اور کچرے کے ڈیٹا یا غلط ڈیٹا کی اطلاع دینا شروع کر دیتا ہے۔ مثالی حل یہ ہوگا کہ وہ تمام ڈیٹا کو ہٹا دیا جائے جو سینسر نے تیار کیا تھا کیونکہ اس نے مجموعی نظام پر خراب ڈیٹا کے تمام اثرات کے ساتھ خرابی پیدا کی تھی۔ بازیافت: فرض کریں کہ ہارڈ ویئر سینسر کو نقصان پہنچا تھا لیکن اب اس کی مرمت کی گئی ہے اور ڈیٹا کو سینسر سے پڑھا جا سکتا ہے۔ ہم ڈیٹا کو سسٹم میں واپس داخل کرنے کے قابل ہونا چاہیں گے گویا سینسر کو پہلی جگہ میں کبھی نقصان نہیں پہنچا تھا۔ ماضی کی ہیرا پھیری: ماضی کو تبدیل کرنا نقصان پر قابو پانے کے معاملات میں مددگار ثابت ہوسکتا ہے اور ماضی سے متعلق ڈیٹا ڈھانچے ماضی کی جان بوجھ کر ہیرا پھیری کے لیے بنائے گئے ہیں۔ وقت کو ایک مقامی جہت کے طور پر وقت کو ایک اضافی مقامی جہت کے طور پر سمجھنا ممکن نہیں ہے۔ اس کی وضاحت کے لیے فرض کریں کہ ہم وقت کے طول و عرض کو خلا کے محور پر نقشہ بناتے ہیں۔ اعداد و شمار کا ڈھانچہ جسے ہم مقامی وقت کے طول و عرض کو شامل کرنے کے لیے استعمال کریں گے وہ ایک چھوٹا سا ڈھیر ہے۔ فرض کریں کہ y محور ڈھیر کے اندر آئٹمز کی کلیدی اقدار کی نمائندگی کرتا ہے اور x محور مقامی وقت کا طول و عرض ہے۔ کئی اندراجات اور ڈیلیٹ-من کارروائیوں کے بعد (تمام غیر ریٹرو ایکٹیو طور پر کیے گئے) ہمارا منی-ہیپ شکل 1 کی طرح نظر آئے گا۔ اب فرض کریں کہ ہم آپریشن کی فہرست کے آغاز میں سابقہ طور پر صفر داخل کرتے ہیں۔ ہمارا منی ہیپ شکل 2 کی طرح نظر آئے گا۔ غور کریں کہ کس طرح واحد آپریشن ایک جھرن اثر پیدا کرتا ہے جو پورے ڈیٹا ڈھانچے کو متاثر کرتا ہے۔ اس طرح ہم دیکھ سکتے ہیں کہ وقت کو ایک مقامی جہت کے طور پر کھینچا جا سکتا ہے، لیکن وقت کے ساتھ ہونے والی کارروائیوں سے انحصار پیدا ہوتا ہے جس میں وقت کے حوالے سے تبدیلیاں کی جاتی ہیں۔ استقامت سے موازنہ پہلی نظر میں ریٹرو ایکٹیو ڈیٹا ڈھانچے کا تصور مستقل ڈیٹا ڈھانچے سے بہت ملتا جلتا لگتا ہے کیونکہ وہ دونوں وقت کے طول و عرض کو مدنظر رکھتے ہیں۔ مستقل ڈیٹا ڈھانچے اور ریٹرو ایکٹیو ڈیٹا ڈھانچے کے درمیان کلیدی فرق یہ ہے کہ وہ وقت کے عنصر کو کس طرح سنبھالتے ہیں۔ ایک مستقل ڈیٹا ڈھانچہ ڈیٹا ڈھانچے کے کئی ورژن کو برقرار رکھتا ہے اور ڈیٹا ڈھانچے کا دوسرا ورژن تیار کرنے کے لیے ایک ورژن پر آپریشن انجام دیا جا سکتا ہے۔ چونکہ ہر آپریشن ایک نیا ورژن تیار کرتا ہے، اس طرح ہر ورژن ایک آرکائیو بن جاتا ہے جسے تبدیل نہیں کیا جا سکتا (اس سے صرف نئے ورژن تیار کیے جا سکتے ہیں)۔ چونکہ ہر ورژن تبدیل نہیں ہوتا، اس لیے ہر ورژن کے درمیان انحصار بھی تبدیل نہیں ہوتا۔ ریٹرو ایکٹیو ڈیٹا ڈھانچوں میں ہم تبدیلیوں کو براہ راست پچھلے ورژن میں کرنے کی اجازت دیتے ہیں۔ چونکہ ہر ورژن اب ایک دوسرے پر منحصر ہے، اس لیے ایک ہی تبدیلی بعد کے تمام ورژن کی تبدیلیوں کی لہر کا سبب بن سکتی ہے۔ اعداد و شمار 1 اور 2 اس لہر کے اثر کی ایک مثال دکھاتے ہیں۔ تعریف کسی بھی ڈیٹا ڈھانچے کو ریٹرو ایکٹیو ترتیب میں دوبارہ تشکیل دیا جا سکتا ہے۔ عام طور پر اعداد و شمار کے ڈھانچے میں کچھ عرصے کے دوران اپ ڈیٹس اور سوالات کا ایک سلسلہ شامل ہوتا ہے۔ یو = [یو ٹی 1، یو ٹی 2، یو ٹی 3،.، یو ٹی ایم] کو ٹی 1 سے ٹی ایم تک اپ ڈیٹ آپریشنز کا سلسلہ اس طرح ہونا چاہیے کہ ٹی 1 <ٹی 2 <. <ٹی ایم۔ یہاں یہ مفروضہ ہے کہ ایک مقررہ وقت کے لیے زیادہ سے زیادہ ایک آپریشن انجام دیا جا سکتا ہے۔ جزوی طور پر ریٹرو ایکٹیو ہم ڈیٹا ڈھانچے کو جزوی طور پر ریٹرو ایکٹیو ہونے کی وضاحت کرتے ہیں اگر یہ موجودہ وقت میں اپ ڈیٹ اور استفسار آپریشن انجام دے سکتا ہے اور ماضی میں اندراج اور حذف کرنے کی کارروائیوں کی حمایت کر سکتا ہے۔ اس طرح جزوی طور پر ریٹرو ایکٹیو کے لیے ہم درج ذیل کارروائیوں میں دلچسپی رکھتے ہیں: داخل کریں (t، u): فہرست U میں وقت t پر ایک نیا آپریشن داخل کریں۔ حذف کریں (t): فہرست U سے وقت t پر آپریشن کو حذف کریں۔ مذکورہ بالا ریٹرو ایکٹیو آپریشنز کو دیکھتے ہوئے، ایک معیاری اندراج آپریشن اب داخل (t، "داخل (x)") کی شکل اختیار کرے گا۔ ڈیٹا ڈھانچے کی آپریشنل ہسٹری پر تمام سابقہ تبدیلیاں ممکنہ طور پر آپریشن کے وقت سے لے کر آج تک تمام کارروائیوں کو متاثر کر سکتی ہیں۔ مثال کے طور پر، اگر ہمارے پاس ti-1 <t <ti + 1 ہے، تو داخل کریں (t، داخل کریں (x)) اوپی-1 اور اوپی + 1 کارروائیوں کے درمیان ایک نیا آپریشن، اوپی، رکھے گا۔ ڈیٹا ڈھانچے کی موجودہ حالت (یعنی۔ : موجودہ وقت میں ڈیٹا ڈھانچہ) اس کے بعد ایسی حالت میں ہوگا کہ آپریشن اوپی-1، اوپی اور اوپی + 1 سب ایک ترتیب میں ہوئے، گویا کہ آپریشن اوپی ہمیشہ موجود تھا۔ بصری مثال کے لیے شکل 1 اور 2 دیکھیں۔ مکمل طور پر ریٹرو ایکٹیو ہم ڈیٹا ڈھانچے کو مکمل طور پر ریٹرو ایکٹیو ہونے کی وضاحت کرتے ہیں اگر جزوی طور پر ریٹرو ایکٹیو کارروائیوں کے علاوہ ہم ماضی کے بارے میں سوالات کرنے کی بھی اجازت دیتے ہیں۔ جزوی طور پر ریٹرو ایکٹیو ماڈل میں معیاری آپریشن انسٹر (x) کس طرح انسٹر (t "، انسٹر (x)") بن جاتا ہے، اسی طرح مکمل طور پر ریٹرو ایکٹیو ماڈل میں آپریشن استفسار (x) میں اب سوال (t "، استفسار (x)") کی شکل ہوتی ہے۔ ریٹرو ایکٹیو رننگ ٹائمز ریٹرو ایکٹیو ڈیٹا اسٹرکچرز کا رننگ ٹائم اسٹرکچر پر انجام دی جانے والی کارروائیوں کی تعداد، m، ریٹرو ایکٹیو آپریشن سے پہلے انجام دی جانے والی کارروائیوں کی تعداد، اور کسی بھی وقت اسٹرکچر میں عناصر n کی زیادہ سے زیادہ تعداد پر مبنی ہوتا ہے۔ ڈیٹا ڈھانچے کے حوالے سے خودکار ریٹرو ایکٹیویٹی کے حوالے سے بنیادی سوال یہ ہے کہ آیا کوئی عمومی تکنیک موجود ہے یا نہیں جو کسی بھی ڈیٹا ڈھانچے کو ایک موثر ریٹرو ایکٹیو ہم منصب میں تبدیل کر سکتی ہے۔ ایک آسان طریقہ یہ ہے کہ سابقہ عمل سے پہلے ساخت میں کی گئی تمام تبدیلیوں پر رول بیک انجام دیا جائے جو لاگو ہونا ہے۔ ایک بار جب ہم اعداد و شمار کے ڈھانچے کو مناسب حالت میں واپس لے لیتے ہیں تو ہم اپنی مطلوبہ تبدیلی لانے کے لیے ریٹرو ایکٹیو آپریشن کا اطلاق کر سکتے ہیں۔ ایک بار تبدیلی ہونے کے بعد ہمیں ان تمام تبدیلیوں کو دوبارہ لاگو کرنا ہوگا جو ہم نے ڈیٹا ڈھانچے کو اس کی نئی حالت میں ڈالنے کے لیے پہلے کی تھیں۔ اگرچہ یہ کسی بھی ڈیٹا ڈھانچے کے لیے کام کر سکتا ہے، لیکن یہ اکثر غیر موثر اور فضول ہوتا ہے خاص طور پر جب ہمیں رول بیک کرنے کے لیے درکار تبدیلیوں کی تعداد زیادہ ہو۔ ایک موثر ریٹرو ایکٹیو ڈیٹا ڈھانچہ بنانے کے لیے ہمیں ڈھانچے کی خصوصیات پر ایک نظر ڈالنی چاہیے تاکہ اس بات کا تعین کیا جا سکے کہ رفتار کو کہاں حاصل کیا جا سکتا ہے۔ اس طرح کسی بھی ڈیٹا ڈھانچے کو ایک موثر ریٹرو ایکٹیو ہم منصب میں تبدیل کرنے کا کوئی عمومی طریقہ نہیں ہے۔ ایرک ڈی ڈیمین، جان آئکونو اور اسٹیفن لینگرمین اس بات کو ثابت کرتے ہیں۔ مستقل ڈیٹا ڈھانچہ حوالہ جات ڈیٹا ڈھانچے بھی دیکھیں۔