Retroactive data structure
কম্পিউটার বিজ্ঞানে একটি পূর্ববর্তী সক্রিয় তথ্য কাঠামো হল একটি তথ্য কাঠামো যা কাঠামোর উপর সম্পাদিত ক্রিয়াকলাপের ক্রমের দক্ষ পরিবর্তনকে সমর্থন করে। এই পরিবর্তনগুলি অতীতের কোনও সময়ে সম্পাদিত কোনও ক্রিয়াকলাপকে পূর্ববর্তী সন্নিবেশ, মুছে ফেলা বা আপডেট করার রূপ নিতে পারে। প্রাক-সক্রিয় তথ্য কাঠামোর কিছু প্রয়োগ বাস্তব জগতে এমন অনেক ক্ষেত্রে রয়েছে যেখানে কেউ ক্রিয়াকলাপের ক্রম থেকে অতীতের ক্রিয়াকলাপকে সংশোধন করতে চায়। নীচে কয়েকটি সম্ভাব্য প্রয়োগের তালিকা দেওয়া হয়েছেঃ ত্রুটি সংশোধনঃ তথ্যের ভুল ইনপুট। তথ্যগুলি সংশোধন করা উচিত এবং ভুল তথ্যের সমস্ত গৌণ প্রভাবগুলি অপসারণ করা উচিত। খারাপ ডেটাঃ বড় সিস্টেমগুলির সাথে কাজ করার সময়, বিশেষত যেগুলি প্রচুর পরিমাণে স্বয়ংক্রিয় ডেটা স্থানান্তরের সাথে জড়িত, এটি অস্বাভাবিক নয়। উদাহরণস্বরূপ, ধরুন একটি আবহাওয়া নেটওয়ার্কের ত্রুটির জন্য সেন্সরগুলির মধ্যে একটি এবং আবর্জনা তথ্য বা ভুল তথ্য রিপোর্ট করতে শুরু করে। সর্বোত্তম সমাধানটি হ 'ল সেন্সরটি যে সমস্ত ডেটা তৈরি করেছিল তা অপসারণ করা কারণ এটি সামগ্রিক সিস্টেমে খারাপ ডেটার সমস্ত প্রভাবের সাথে ত্রুটিযুক্ত ছিল। পুনরুদ্ধারঃ ধরুন যে একটি হার্ডওয়্যার সেন্সর ক্ষতিগ্রস্ত হয়েছিল কিন্তু এখন মেরামত করা হয়েছে এবং সেন্সর থেকে ডেটা পড়তে সক্ষম। আমরা সিস্টেমে ডেটা আবার ঢোকাতে সক্ষম হতে চাই যেন সেন্সরটি প্রথম স্থানে কখনও ক্ষতিগ্রস্ত হয়নি। অতীতের কারসাজিঃ অতীতের পরিবর্তন ক্ষতি নিয়ন্ত্রণের ক্ষেত্রে সহায়ক হতে পারে এবং অতীতের ইচ্ছাকৃত কারসাজির জন্য পূর্ববর্তী তথ্য কাঠামো তৈরি করা হয়। সময়কে একটি স্থানিক মাত্রা হিসাবে বিবেচনা করা সম্ভব নয়। এটি ব্যাখ্যা করার জন্য ধরুন আমরা স্থানের একটি অক্ষের উপর সময়ের মাত্রার মানচিত্র তৈরি করি। স্থানিক সময়ের মাত্রা যোগ করার জন্য আমরা যে ডেটা স্ট্রাকচারটি ব্যবহার করব তা একটি মিনি-হিপ। ধরা যাক y অক্ষটি স্তূপের মধ্যে আইটেমগুলির মূল মানগুলি উপস্থাপন করে এবং x অক্ষটি স্থানিক সময়ের মাত্রা। বেশ কয়েকটি সন্নিবেশ এবং ডিলিট-মিন ক্রিয়াকলাপের পরে (সমস্ত অ-প্রতিক্রিয়াশীলভাবে করা হয়েছে) আমাদের মিনি-হিপ চিত্র 1-এর মতো প্রদর্শিত হবে। এখন ধরুন আমরা অপারেশন তালিকার শুরুতে পূর্ববর্তীভাবে শূন্য সন্নিবেশ করি। আমাদের মিনি-হিপ চিত্র 2-এর মতো দেখাবে। লক্ষ্য করুন কিভাবে একক অপারেশন একটি ক্যাসকেডিং প্রভাব তৈরি করে যা সমগ্র তথ্য কাঠামোকে প্রভাবিত করে। এইভাবে আমরা দেখতে পাই যে সময়কে একটি স্থানিক মাত্রা হিসাবে আঁকা যেতে পারে, সময়ের সাথে জড়িত ক্রিয়াকলাপগুলি নির্ভরশীলতা তৈরি করে যা সময়ের সাথে সামঞ্জস্য রেখে পরিবর্তন করা হলে একটি তরঙ্গ থাকে। অধ্যবসায়ের সাথে তুলনা প্রথম নজরে একটি পূর্ববর্তী তথ্য কাঠামোর ধারণাটি স্থায়ী তথ্য কাঠামোর সাথে খুব মিল বলে মনে হয় কারণ তারা উভয়ই সময়ের মাত্রা বিবেচনা করে। স্থায়ী তথ্য কাঠামো এবং পূর্ববর্তী সক্রিয় তথ্য কাঠামোর মধ্যে মূল পার্থক্য হল তারা কীভাবে সময়ের উপাদান পরিচালনা করে। একটি স্থায়ী ডেটা স্ট্রাকচার একটি ডেটা স্ট্রাকচারের বিভিন্ন সংস্করণ বজায় রাখে এবং ডেটা স্ট্রাকচারের অন্য সংস্করণ তৈরি করতে একটি সংস্করণে অপারেশন করা যেতে পারে। যেহেতু প্রতিটি অপারেশন একটি নতুন সংস্করণ তৈরি করে, তাই প্রতিটি সংস্করণ এইভাবে একটি সংরক্ষণাগারে পরিণত হয় যা পরিবর্তন করা যায় না (এটি থেকে শুধুমাত্র নতুন সংস্করণ তৈরি করা যেতে পারে)। যেহেতু প্রতিটি সংস্করণ পরিবর্তিত হয় না, তাই প্রতিটি সংস্করণের মধ্যে নির্ভরতাও পরিবর্তিত হয় না। পূর্ববর্তী সক্রিয় তথ্য কাঠামোতে আমরা সরাসরি পূর্ববর্তী সংস্করণগুলিতে পরিবর্তন করার অনুমতি দিই। যেহেতু প্রতিটি সংস্করণ এখন পরস্পর নির্ভরশীল, তাই একটি একক পরিবর্তন পরবর্তী সমস্ত সংস্করণের পরিবর্তনের তরঙ্গ সৃষ্টি করতে পারে। চিত্র 1 এবং 2 এই তরঙ্গায়িত প্রভাবের একটি উদাহরণ দেখায়। সংজ্ঞা যে কোনও তথ্য কাঠামোকে পূর্ববর্তী ক্রিয়াশীল পরিবেশে সংস্কার করা যেতে পারে। সাধারণভাবে তথ্য কাঠামোতে কিছু সময়ের মধ্যে একাধিক আপডেট এবং প্রশ্ন জড়িত থাকে। ধরা যাক U = [ut1, ut2, ut3,., utm] হল t1 থেকে tm পর্যন্ত আপডেট ক্রিয়াকলাপের ক্রম যাতে t1 <t2 <. <tm। এখানে অনুমান করা হয় যে একটি নির্দিষ্ট সময়ের জন্য সর্বাধিক একটি অপারেশন করা যেতে পারে। আংশিকভাবে পূর্ববর্তী আমরা ডেটা কাঠামোকে আংশিকভাবে পূর্ববর্তী হিসাবে সংজ্ঞায়িত করি যদি এটি বর্তমান সময়ে আপডেট এবং ক্যোয়ারি অপারেশন করতে পারে এবং অতীতে সন্নিবেশ এবং মুছে ফেলার ক্রিয়াকলাপগুলিকে সমর্থন করে। এইভাবে আংশিকভাবে পূর্ববর্তী ক্রিয়াকলাপের জন্য আমরা নিম্নলিখিত ক্রিয়াকলাপগুলিতে আগ্রহীঃ (t, u) সন্নিবেশ করানঃ t সময়ে U তালিকায় একটি নতুন ক্রিয়াকলাপ u সন্নিবেশ করান। মুছে ফেলুন (t): U তালিকা থেকে t সময়ে ক্রিয়াকলাপটি মুছে ফেলুন। উপরের পূর্ববর্তী ক্রিয়াকলাপগুলির পরিপ্রেক্ষিতে, একটি স্ট্যান্ডার্ড সন্নিবেশ ক্রিয়াকলাপ এখন সন্নিবেশ (টি, "সন্নিবেশ (এক্স)") এর রূপ হবে। তথ্য কাঠামোর কার্যকরী ইতিহাসে সমস্ত পূর্ববর্তী পরিবর্তনগুলি সম্ভাব্যভাবে বর্তমান পর্যন্ত ক্রিয়াকলাপের সময় সমস্ত ক্রিয়াকলাপকে প্রভাবিত করতে পারে। উদাহরণস্বরূপ, যদি আমাদের কাছে ti-1 <t <ti + 1 থাকে, তবে সন্নিবেশ (t, সন্নিবেশ (x)) একটি নতুন অপারেশন স্থাপন করবে, op, অপারেশন ওপি-1 এবং ওপি + 1 এর মধ্যে। তথ্য কাঠামোর বর্তমান অবস্থা (অর্থাৎ। : বর্তমান সময়ে তথ্য কাঠামো) তখন এমন একটি অবস্থায় থাকবে যেমন অপারেশন ওপিআই-1, ওপি এবং ওপিআই + 1 সবই একটি ক্রমে ঘটেছিল, যেন অপারেশন ওপি সর্বদা ছিল। একটি দৃশ্যমান উদাহরণের জন্য চিত্র 1 এবং 2 দেখুন। আমরা তথ্য কাঠামোকে সম্পূর্ণরূপে পূর্ববর্তী হিসাবে সংজ্ঞায়িত করি যদি আংশিকভাবে পূর্ববর্তী ক্রিয়াকলাপের পাশাপাশি আমরা অতীত সম্পর্কে প্রশ্ন করার অনুমতিও দিই। আংশিকভাবে রেট্রোঅ্যাকটিভ মডেলে স্ট্যান্ডার্ড অপারেশন ইনসার্ট (x) যেভাবে ইনসার্ট (t, "ইনসার্ট (x)") হয়ে যায়, ঠিক তেমনই সম্পূর্ণ রেট্রোঅ্যাকটিভ মডেলে অপারেশন কোয়ারির (x) এখন কোয়ারির (t, "কোয়ারির (x)") রূপ রয়েছে। বিপরীতমুখী চলমান সময় পূর্ববর্তী সক্রিয় তথ্য কাঠামোর চলমান সময় কাঠামোর উপর সঞ্চালিত ক্রিয়াকলাপের সংখ্যা, এম, পূর্ববর্তী ক্রিয়াকলাপ সম্পাদনের আগে সঞ্চালিত ক্রিয়াকলাপের সংখ্যা এবং যে কোনও একক সময়ে কাঠামোর সর্বাধিক সংখ্যক উপাদানের উপর ভিত্তি করে। স্বয়ংক্রিয় রেট্রো-অ্যাক্টিভিটি ডেটা স্ট্রাকচারের ক্ষেত্রে স্বয়ংক্রিয় রেট্রো-অ্যাক্টিভিটি সম্পর্কিত প্রধান প্রশ্ন হল এমন কোনও সাধারণ কৌশল আছে কি না যা কোনও ডেটা স্ট্রাকচারকে দক্ষ রেট্রো-অ্যাক্টিভ প্রতিরূপে রূপান্তর করতে পারে। একটি সহজ পদ্ধতি হল পূর্ববর্তী ক্রিয়াকলাপের আগে কাঠামোতে করা সমস্ত পরিবর্তনের উপর একটি রোল-ব্যাক করা যা প্রয়োগ করা হবে। একবার আমরা ডেটা স্ট্রাকচারটি যথাযথ অবস্থায় ফিরিয়ে আনার পরে আমরা যে পরিবর্তনটি চেয়েছিলাম তা করার জন্য পূর্ববর্তী ক্রিয়াকলাপ প্রয়োগ করতে পারি। একবার পরিবর্তন করা হয়ে গেলে, তথ্য কাঠামোকে তার নতুন অবস্থায় আনার জন্য আমাদের অবশ্যই আগে করা সমস্ত পরিবর্তনগুলি পুনরায় প্রয়োগ করতে হবে। যদিও এটি যে কোনও তথ্য কাঠামোর জন্য কাজ করতে পারে, এটি প্রায়শই অদক্ষ এবং অপচয়মূলক হয়, বিশেষত যখন আমাদের রোল-ব্যাক করার জন্য প্রয়োজনীয় পরিবর্তনের সংখ্যা বেশি হয়। একটি দক্ষ পূর্ববর্তী তথ্য কাঠামো তৈরি করতে আমাদের অবশ্যই কাঠামোর বৈশিষ্ট্যগুলির দিকে নজর দিতে হবে যাতে নির্ধারণ করা যায় যে কোথায় গতি বৃদ্ধি করা যেতে পারে। সুতরাং কোনও তথ্য কাঠামোকে দক্ষ পূর্ববর্তী প্রতিরূপে রূপান্তর করার কোনও সাধারণ উপায় নেই। এরিক ডি. ডেমাইন, জন আইয়াকো এবং স্টেফান ল্যাঙ্গারম্যান এটি প্রমাণ করেছেন। আরও দেখুন স্থায়ী তথ্য কাঠামো রেফারেন্স তথ্য কাঠামো