Les travaux présentés dans ce mémoire traitent de la synthèse d'algorithmes de diagnostic de défauts simples et multiples. L'objectif vise à proposer une stratégie de diagnostic à minimum de redondance analytique en exploitant au mieux les informations de redondance matérielle éventuellement disponibles sur le système. Les développements proposés s'inscrivent dans une démarche de coopération et d'agrégation des méthodes de diagnostic et la construction optimale d'un diagnostic global en fonction des diagnostiqueurs locaux. Les travaux réalisés se veulent génériques dans le sens où ils mêlent à la fois les concepts et outils de deux communautés : ceux de la communauté FDI (Fault Detection and Isolation) et ceux de la communauté DX (Diagnosis) dont les bases méthodologiques sont issues des domaines informatiques et intelligence artificielle. Ainsi, le problème de détection (ainsi que le problème de localisation lorsque les contraintes structurelles le permettent) est résolu à l'aide des outils de la communauté FDI tandis que le problème de localisation est résolu à l'aide des concepts de la communauté DX, offrant ainsi une démarche méthodologique agrégée. La démarche méthodologique se décline en deux étapes principales. La première phase consiste en la construction d'une matrice de signatures mutuellement exclusive. Ainsi, le problème du nombre minimal de relations de redondance analytique (RRA), nécessaires pour établir un diagnostic sans ambiguïté, est abordé. Ce problème est formalisé comme un problème d'optimisation sous contraintes qui est efficacement résolu à l'aide d'un algorithme génétique. La deuxième étape concerne la génération des diagnostics. Ainsi, pour une situation observée, identifier les conflits revient à définir les RRAs non satisfaites par l'observation. Les diagnostics sont obtenus à l'aide d'un algorithme basé sur le concept de formules sous forme MNF (Maximal Normal Form). L'intérêt majeur dans cette approche est sa capacité à traiter le diagnostic des défauts simples et multiples ainsi que le diagnostic des plusieurs modes de fautes (i.e., le diagnostic des différents types de défauts) associés à chaque composant du système surveillé. De plus, il existe des preuves d'optimalité tant au niveau local (preuve de robustesse/sensibilité) qu'au niveau global (preuve de diagnostics minimaux). La méthodologie proposée est appliquée à la mission spatiale Mars Sample Return (MSR). Cette mission, entreprise conjointement entre l'administration nationale de l'aéronautique et de l'espace (NASA) et l'agence spatiale européenne (ESA), vise à ramener des échantillons martiens sur Terre pour des analyses. La phase critique de cette mission est la phase rendez-vous entre le conteneur d'échantillons et l'orbiteur. Les travaux de recherche traitent le problème de diagnostic des défauts capteurs présents sur la chaîne de mesure de l'orbiteur pendant la phase de rendez-vous de la mission. Les résultats, obtenus à l'aide du simulateur haute fidélité de Thalès Alenia Space, montrent la faisabilité et l'efficacité de la méthode. / The work presented in this thesis deals with the synthesis of algorithms for the diagnosis of simple and multiple faults. The main objective which is pursued is to design a fault diagnosis scheme by merging a minimum number of analytic redundancy with the available hardware redundancy. The main contribution of the proposed technique concerns the general architecture of the proposed diagnosis method. The originality of the research work is the combination of ideas and tools originated from two research communities : the FDI (Fault Detection and Isolation) community and the DX (Diagnosis) community whose foundations are derived from Computer Science and Artificial Intelligence fields. Hence, the fault detection problem (as well as the isolation task when structural constraints allow it) is solved by means of FDI techniques while the fault isolation problem is solved through the DX approaches, thus resulting in an aggregated methodology. The proposed method is divided in two steps. The first step deals with the construction of a mutually exclusive signature matrix. Hence, the problem of the minimal number of analytic redundancy relations (ARR), necessary for generating a diagnosis without any ambiguity, is treated. This problem is formalised as an optimized problem under constraints which is efficiently solved by means of a genetic algorithm. The second step concerns the generation of diagnoses. Thus, for an observed situation, the identification of conflicts results in the determination of the non satisfied ARRs for the given observation. The diagnoses are obtained by means an algorithm based on the concept of MNF (Maximal Normal Form) formulas. The main interest of this approach is its capacity to deal with the diagnosis of simple and multiple faults as well as the diagnosis of multi-modes faults (i.e., multiple types of faults) associated to each component of the system. Furthermore, it exists proofs on optimality both at a local level (proof of robustness/sensitivity) and at a global level (proof of minimal diagnoses). The proposed method is applied to the Mars Sample Return (MSR) mission. This spacecraft mission, undertaken jointly by the National Aeronautics and Space Administration (NASA) and the European Space Agency (ESA), aims at returning tangible samples from Mars atmosphere and ground to Earth for analysis. The critical phase of the mission is the rendezvous phase between the sample container vehicle and the orbiter spacecraft. The research work aims at realising sensor fault diagnosis on the orbiter during the rendezvous phase of the mission. Simulation results from the MSR high fidelity simulator, provided by Thalès Alenia Space, demonstrate the feasibility and the efficiency of the proposed approach.

Abstract There are many reasons for sharing a photo of a printout. The intention might be to copy the image for personal use or experience an interesting ad with friends. With watermarking, the images can also carry side information and with specialized watermarking methods the information can be read with a mobile device camera. In digital image watermarking, information is hidden on an image in such a way that a computer can read the hidden information but a human cannot discern it. The aim of this thesis is to research the process in which the watermarked image is printed and then read with a digital camera or a camera phone from the printed image. In order to survive the process, the watermark must survive multiple attacks. Some of the attacks occur during printing as the image is halftoned, others when the image is recaptured with a camera, in which case the camera might be rotated around multiple axis. These attacks may cause a loss of synchronization of the watermark and make the extraction impossible. The main objective of the thesis is thus to develop methods that are robust to the printing and capturing process, especially for the situations when the capturing angle is large. This problem contains the circumstances in which the synchronization is lost and the camera lens is not focused properly. In this work, research on digital image watermarking, computational photography and mobile phones are combined. The contributions of this thesis lie in two main parts: First, two print-cam robust methods are proposed, one based on a frame and the other on autocorrelation for synchronization. These two are then used as a basis for an algorithm that recovers the watermark even after camera rotation and image blurring caused by the narrow depth of focus of the lens. The algorithm is later refined and implemented for a mobile phone. The results show that the method is highly robust to capturing the watermark without errors in angles up to 60° with processing times acceptable for real-life applications. / Tiivistelmä On olemassa useita syitä tulosteesta otetun valokuvan jakamiseen. Aikomuksena voi olla kopioida kuva omaan käyttöön tai jakaa mielenkiintoinen ilmoitus ystävien kanssa. Vesileimauksessa kuvaan voidaan sijoittaa lisätietoa ja erityisillä menetelmillä tieto voidaan myöhemmin lukea mobiililaitteen kameralla. Digitaalisten kuvien vesileimauksen tavoite on piilottaa tietoa kuvaan siten, että tietokone pystyy lukemaan piilotetun informaation, siinä missä ihminen ei pysty sitä havaitsemaan. Tämän väitöskirjan tavoitteena on tutkia prosessia, missä vesileimattu kuva tulostetaan ja vesileima luetaan digitaalisella kameralla tai kamerapuhelimella tulosteesta. Selviytyäkseen tästä prosessista, vesileiman on kestettävä useita hyökkäyksiä. Osa hyökkäyksistä esiintyy tulostuksen aikana, kun kuva rasteroidaan, ja osa valokuvatessa, jolloin kamera voi olla kiertynyt. Näiden hyökkäysten seurauksena vesileiman synkronointi voi kadota, jolloin vesileiman lukeminen ei enää onnistu. Väitöskirjan päätavoitteena on siis kehittää tulostuksen ja valokuvauksen kestäviä vesileimausmenetelmiä erityisesti niitä tilanteita varten, jolloin kuvauskulma on suuri. Tämä ongelma sisältää olosuhteet, joissa synkronointi menetetään, ja kun kameran linssi ei ole kohdistunut oikein. Työssä yhdistetään digitaalinen kuvien vesileimaus, laskennallinen valokuvaus ja matkapuhelimet. Tutkimus voidaan jakaa kahteen osa-alueeseen: Ensimmäisessä kehitetään kaksi tulostuksen ja valokuvauksen kestävää menetelmää, joista toinen perustuu kehykseen ja toinen autokorrelaatioon synkronoinnin säilyttämiseksi. Toisessa osassa näitä menetelmiä hyödynnetään algoritmissa, joka kykenee vesileiman lukemiseen myös silloin kun kameran kiertyminen on voimakasta ja objektiivin kapea tarkennussyvyys aiheuttaa sumeita alueita kuvassa. Tutkimustyön lopussa tätä algoritmia viedään eteenpäin ja testataan matkapuhelinalustalla. Tulokset osoittavat menetelmän kestävän kameran kiertymistä 60°:seen saakka suoritusajoilla, jotka ovat hyväksyttäviä sovelluskäyttöön.

Ce travail constitue une contribution à l’étude de la synergie entre le vieillissement accéléré et l’évolution de la robustesse aux évènements singuliers pour les technologies MOS avancées. Ce manuscrit expose le travail fait autour de la Caractérisations des mécanismes de dégradation NBTI, HCI, TDDB et Electromigration sur les structures de tests conçues dans le véhicule de test NANOSPACE en technologie CMOS LP 65 nm. Il décrit aussi l’évaluation de la robustesse face aux évènements singuliers après un vieillissement de type NBTI sur les chaines de portes logiques (inverseurs, NOR, bascules D). Cette dernière partie nous a permis de démontrer que le vieillissement de type NBTI améliore la robustesse face aux SET dans ce cas d’étude. / This work is a contribution to the study of the synergy between accelerated aging and the evolution of robustness to single event effects for advanced MOS technologies.This manuscript describes the work done around the characterization of degradation mechanisms NBTI, HCI, TDDB and Electromigration on test structures designed in the NANOSPACE test vehicle on CMOS 65 nm Low Power technology. It also describes the evaluation of the robustness to Single Events Effects after NBTI aging on chains of logic gates (inverters, NOR, D flip-flops). This last part allows to show that the NBTI aging improves the robustness to SET in this case of study.

In the field of formal verification of real-time systems, major developments have been recorded in the last fifteen years. It is about logics, automata, process algebra, programming languages, etc. From the beginning, a formalism has played an important role: timed automata and their natural extension,hybrid automata. Those models allow the definition of real-time constraints using real-valued clocks, or more generally analog variables whose evolution is governed by differential equations. They generalize finite automata in that their semantics defines timed words where each symbol is associated with an occurrence timestamp.<p><p>The decidability and algorithmic analysis of timed and hybrid automata have been intensively studied in the literature. The central result for timed automata is that they are positively decidable. This is not the case for hybrid automata, but semi-algorithmic methods are known when the dynamics is relatively simple, namely a linear relation between the derivatives of the variables.<p>With the increasing complexity of nowadays systems, those models are however limited in their classical semantics, for modelling realistic implementations or dynamical systems.<p><p>In this thesis, we study the algorithmics of complex semantics for timed and hybrid automata.<p>On the one hand, we propose implementable semantics for timed automata and we study their computational properties: by contrast with other works, we identify a semantics that is implementable and that has decidable properties. <p>On the other hand, we give new algorithmic approaches to the analysis of hybrid automata whose dynamics is given by an affine function of its variables.<p> / Doctorat en sciences, Spécialisation Informatique / info:eu-repo/semantics/nonPublished

In this thesis, we study robust combinatorial problems with interval data. We introduce several new measures of robustness in response to the drawbacks of existing measures of robustness. The idea of these new measures is to ensure that the solutions are satisfactory for the decision maker in all scenarios, including the worst case scenario. Therefore, we have introduced a threshold over the worst case costs, in which above this threshold, solutions are no longer satisfactory for the decision maker. It is, however, important to consider other criteria than just the worst case.<p>Therefore, in each of these new measures, a second criteria is used to evaluate the performance of the solution in other scenarios such as the best case one. <p><p>We also study the robust deviation p-elements problem. In fact, we study when this solution is equal to the optimal solution in the scenario where the cost of each element is the midpoint of its corresponding interval. <p><p>Then, we finally formulate the robust combinatorial problem with interval data as a bicriteria problem. We also integrate the decision maker's preferences over certain types of solutions into the model. We propose a method that uses these preferences to find the set of solutions that are never preferred by any other solution. We call this set the final set. <p><p>We study the properties of the final sets from a coherence point of view and from a robust point of view. From a coherence point of view, we study necessary and sufficient conditions for the final set to be monotonic, for the corresponding preferences to be without cycles, and for the set to be stable.<p>Those that do not satisfy these properties are eliminated since we believe these properties to be essential. We also study other properties such as the transitivity of the preference and indifference relations and more. We note that many of our final sets are included in one another and some are even intersections of other final sets. From a robust point of view, we compare our final sets with different measures of robustness and with the first- and second-degree stochastic dominance. We show which sets contain all of these solutions and which only contain these types of solutions. Therefore, when the decision maker chooses his preferences to find the final set, he knows what types of solutions may or may not be in the set.<p><p>Lastly, we implement this method and apply it to the Robust Shortest Path Problem. We look at how this method performs using different types of randomly generated instances. <p> / Doctorat en sciences, Orientation recherche opérationnelle / info:eu-repo/semantics/nonPublished

Die Anforderungen an schnelle Dioden sind sehr hoch für große Spannungen und große Ströme. Die Beeinflussung des Bauelementverhaltens durch das Design des Dotierprofils mit einem tiefen mehrstufigen Feldstopp aus Selen bildet einen zentralen Punkt der Dissertation. Mit physikalischen Messverfahren werden die in der Literatur nur unzureichend untersuchten Eigenschaften von Selen in Silizium erfasst und als Basis für Bauelementsimulationen verwendet. Für die Untersuchung der Störstelleneigenschaften kommt die klassische aufwändige DLTS zum Einsatz. Des Weiteren werden für diese Untersuchungen die Vorteile der einfacheren frequenzabhängigen Admittanzspektroskopie ausführlich dargelegt. Anhand der Bauelementsimulationen erfolgt ein Vergleich mit Messungen und führt zur Vorstellung und Erläuterung einer verbesserten soften und robusten Diodenstruktur mit tiefen Donatoren aus Selen. / The focus of the following work is the correlation between the field-stop design and the behaviour of high-voltage power diodes. The objective is to present a further improvement of the diode performance using a special field-stop, which optimizes the diode in relation to a soft switching behaviour and an increased robustness. The function of such a field-stop is investigated. Benefits are shown of materials for field-stops with deep impurities in the semiconductor material and of multiple stepped deep field-stop structures. Therefore a central role have silicon diodes with selenium in the field-stop layer. Measurements and simulations with the power device simulator Sentaurus TCAD are done and explain the named correlations. The deep level transient spectroscopy is used as method to analyse the required impurity parameters. Beside this method the evaluation is done by the introduced frequency resolved admittance spectroscopy.

隨著WiFi訊號在都市的涵蓋率逐漸普及，基於WiFi訊號強度值的定位方法逐漸發展。WiFi匹配定位(Matching Positioning)是透過參考點坐標與WiFi訊號強度(Received Signal Strength Indicator, RSSI)的蒐集，以最小二乘法(Least Squares, LS)計算RSSI模型參數；然後，利用模型參數與使用者位置的WiFi訊號強度，推估出使用者的位置。然而WiFi訊號強度容易受到環境因素影響，例如降雨、建物遮蔽、人群擾動等因素，皆會使訊號強度降低，若以受影響的訊號強度進行定位，將使定位成果與真實位置產生偏移。 為了降低訊號強度的錯誤造成定位結果的誤差，本研究嘗試透過具有穩健性的最小一乘法( Least Absolute Deviation, LAD)結合WiFi匹配定位，去克服WiFi訊號易受環境影響的特性，期以獲得較精確的WiFi定位成果。研究首先透過模擬資料的建立，測試不同粗差狀況最小一乘法WiFi匹配定位之表現，最後再以真實WiFi訊號進行匹配定位的演算，並比較最小一乘法WiFi匹配定位與最小二乘法WiFi匹配定位的成果差異，探討二種方法的特性。 根據本研究成果顯示，於模擬資料中，最小一乘法WiFi匹配定位相較於最小二乘法WiFi匹配定位，在面對參考點接收的AP訊號與檢核點接收的AP訊號強度含有粗差的情形皆能有較好的穩健性，且在參考點接收的AP訊號含有粗差的情況有良好的偵錯能力。而於真實環境之下，最小一乘法WiFi匹配定位之精度也較最小二乘法WiFi匹配定位具有穩健性；在室外資料的部份，最小一乘法WiFi匹配定位之精度為8.46公尺，最小二乘法WiFi匹配定位之精度為8.57公尺。在室內資料的部份，最小一乘法WiFi匹配定位之精度為2.20公尺，最小二乘法WiFi匹配定位之精度為2.41公尺。 / Because of the extensive coverage of WiFi signal, the positioning methods by the WiFi signal are proposed. WiFi Matching Positioning is a method of WiFi positioning. By collecting the WiFi signal strength and coordiates of reference points to calculate the signal strength transformation parameters, then, user’s location can be calculated with the LS (Least Squares). However, the WiFi signal strength is easily degraded by the environment. Using the degraded WiFi signal to positioning will produce wrong coordinates. Hence this research tries to use the robustness of LAD (Least Absolute Deviation) combining with WiFi Matching Positioning to overcome the sensibility of WiFi signal strength, expecting to make the result of WiFi positioning more reliable. At first, in order to test the ability of LAD, this research uses simulating data to add different kind of outliers in the database, and checks the performance of LAD WiFi Matching Positioning. Finally, this research uses real data to compare the difference between the results of LAD and LS WiFi Matching Positioning. In the simulating data, the test result shows that LAD WiFi Matching Positioning can not only have better robust ability to deal with the reference and check points AP signal strength error than LS WiFi Matching Positioning but also can detect the outlier in the reference points AP signal strength. In the real data, LAD WiFi Matching Positioning can also have better result. In the outdoor situation, the RMSE (Root Mean Square Error) of LAD WiFi Matching Positioning and LS (Least Squares) WiFi Matching Positioning are 8.46 meters and 8.57 meters respectively. In the indoor situation, the RMSE (Root Mean Square Error) of LAD WiFi Matching Positioning and LS (Least Squares) WiFi Matching Positioning are 2.20 meters and 2.41 meters respectively.

La protection de l’image médicale numérique comporte au moins deux aspects principaux: la sécurité et l’authenticité. Afin d’assurer la sécurité, l’information doit être protégée vis-à-vis des utilisateurs non autorisés. L’authenticité permet quant à elle de s’assurer que la donnée reçue n’est pas modifiée, n’est pas altérée, et qu’elle est bien envoyée par l’expéditeur supposé. La « technique » cryptographique garantit la sécurité en faisant l’hypothèse que l’expéditeur et le destinataire ont des clés permettant respectivement de crypter et de décrypter le message. De cette manière, seule la personne possédant la bonne clé peut décrypter le message et accéder au contenu de la donnée médicale. Dans cette thèse, nous avons apporté plusieurs contributions. La principale contribution est la proposition de solutions de tatouage d'images médicales robustes et réversibles dans le domaine spatial basées respectivement sur l’analyse de concepts formels (FCA) et le diagramme de décision binaire par suppression des zéros (ZBDD). La seconde est une approche de tatouage d’image médicale semi-aveugle pour la détection de modifications malveillantes. Une autre contribution est la proposition d'un système de chiffrement symétrique sécurisé basé sur les N-grams. La dernière contribution est un système hybride de tatouage et de cryptographie d’image médicale qui s’appuie sur une nouvelle forme de carte chaotique (chaotic map) pour générer des clés ayant des propriétés spécifiques, et qui permet d'obtenir une meilleure efficacité, une grande robustesse et une faible complexité par rapport aux approches existantes. / The protection of digital medical image comprises at least two main aspects: security and authentication. In order to ensure the security, the information has to be protected from the unauthorized users while the authentication confirms that the received data is not affected or modified and is sent by the intended sender (watermarking). The cryptography technique proves the security issues by assuming the intended sender and intended receiver have some security aspects called keys. So, after encryption of the digital material from the sender side, the person who has the key (receiver) can decrypt and access the content of the digital material. In this thesis, we have brought several contributions. The main one is the provision of robust and reversible medical image watermarking solutions in the spatial domain based respectively on FCA and ZBDD. The second one is a semi-blind medical image watermarking approach for the tamper detection. Another contribution is the proposal of a secure symmetric encryption system based on N-gram. The last contribution is a hybrid watermarking and cryptography medical image system which focuses on a new form of chaotic map to generate keys with specific properties, and achieves better efficiency, high robustness and low complexity than the existing approaches.

Sensor nodes in a wireless sensor network (WSN) have a small, non-rechargeable power supply. Each message transmission or reception depletes a sensor node’s energy. Many WSN applications are ad-hoc deployments where a sensor node is only aware of its immediate neighbours. The lack of a predefined route path and the need to restrict the amount of communication that occurs within the application area impose constraints on WSNs not prevalent in other types of networks. An area of active research has been how to notify the central sink (or monitoring hub) about an event in real-time by utilising the minimum number of messages to route a message from a source node to the destination sink node. In this thesis, strategies to limit communication within a WSN application area, while ensuring that events are reported on and responded to in real-time, is presented. A solution based on modelling a WSN as a small world network and then transmitting an initialisation message (IM) on network start-up to create multiple route paths from any sensor node to one or more sinks is proposed. The reason for modelling a WSN as a small world network is to reduce the number of nodes required to re-transmit a message from a source sensor node to a sink. The purpose of sending an IM at network start-up is to ensure that communication within the WSN is minimised. When routing a message to a static sink, the nodes closest to the static sink receive a disproportionate number of messages, resulting in their energy being consumed earlier. The use of mobile sinks has been proposed but to our knowledge no studies have been undertaken on the paths these mobile sinks should follow. An algorithm to determine the optimum path for mobile sinks to follow in a WSN application area is described. The purpose of an optimum path is to allow more equitable usage of all nodes to transfer an event message to a mobile sink. The idea of using multiple static sinks placed at specific points in the small world model is broadened to include using multiple mobile sinks called actors to move within a WSN application area and respond to an event in real-time. Current coordination solutions to determine which actor(s) must respond to the event result in excessive message communication and limit the real-time response to an event. An info gap decision theory (IGDT) model to coordinate which actor or set of actors should respond to the event is described. A comparison of the small world routing (SWR) model against routing using flooding and gossiping shows that the SWR model significantly reduces the number of messages transmitted within the network. An analysis of the number of IMs transmitted and received at individual node level shows that prudent selection of the hop count (number of additional nodes required to route a message to sink) to a sink node will result in a reduced number of messages transmitted and received per node within the network. The use of the IGDT model results in a robust decision on the actor(s) chosen to respond to an event even when uncertainty about the location and available energy of other actor(s) exists. / Thesis (PhD(Eng))--University of Pretoria, 2012. / Electrical, Electronic and Computer Engineering / unrestricted

Over the last four decades, relational database systems, with their mathematical basis in first-order logic, have provided a congenial and efficient environment to handle enterprise data during its entire life cycle of generation, storage, maintenance and processing. An organic reason for their pervasive popularity is intrinsic support for declarative user queries, wherein the user only specifies the end objectives, and the system takes on the responsibility of identifying the most efficient means, called “plans”, to achieve these objectives. A crucial input to generating efficient query execution plans are the compile-time estimates of the data volumes that are output by the operators implementing the algebraic predicates present in the query. These volume estimates are typically computed using the “selectivities” of the predicates. Unfortunately, a pervasive problem encountered in practice is that these selectivities often differ significantly from the values actually encountered during query execution, leading to poor plan choices and grossly inflated response times. While the database research community has spent considerable efforts to address the above challenge, the prior techniques all suffer from a systemic limitation - the inability to provide any guarantees on the execution performance. In this thesis, we materially address this long-standing open problem by developing a radically different query processing strategy that lends itself to attractive guarantees on run-time performance. Specifically, in our approach, the compile-time estimation process is completely eschewed for error-prone selectivities. Instead, from the set of optimal plans in the query’s selectivity error space, a limited subset called the “plan bouquet”, is selected such that at least one of the bouquet plans is 2-optimal at each location in the space. Then, at run time, an exploratory sequence of cost-budgeted executions from the plan bouquet is carried out, eventually finding a plan that executes to completion within its assigned budget. The duration and switching of these executions is controlled by a graded progression of isosurfaces projected onto the optimal performance profile. We prove that this construction provides viable guarantees on the worst-case performance relative to an oracular system that magically possesses accurate apriori knowledge of all selectivities. Moreover, it ensures repeatable execution strategies across different invocations of a query, an extremely desirable feature in industrial settings. Our second contribution is a suite of techniques that substantively improve on the performance guarantees offered by the basic bouquet algorithm. First, we present an algorithm that skips carefully chosen executions from the basic plan bouquet sequence, leveraging the observation that an expensive execution may provide better coverage as compared to a series of cheaper siblings, thereby reducing the aggregate exploratory overheads. Next, we explore randomized variants with regard to both the sequence of plan executions and the constitution of the plan bouquet, and show that the resulting guarantees are markedly superior, in expectation, to the corresponding worst case values. From a deployment perspective, the above techniques are appealing since they are completely “black-box”, that is, non-invasive with regard to the database engine, implementable using only API features that are commonly available in modern systems. As a proof of concept, the bouquet approach has been fully prototyped in QUEST, a Java-based tool that provides a visual and interactive demonstration of the bouquet identification and execution phases. In similar spirit, we propose an efficient isosurface identification algorithm that avoids exploration of large portions of the error space and drastically reduces the effort involved in bouquet construction. The plan bouquet approach is ideally suited for “canned” query environments, where the computational investment in bouquet identification is amortized over multiple query invocations. The final contribution of this thesis is extending the advantage of compile-time sub-optimality guarantees to ad hoc query environments where the overheads of the off-line bouquet identification may turn out to be impractical. Specifically, we propose a completely revamped bouquet algorithm that constructs the cost-budgeted execution sequence in an “on-the-fly” manner. This is achieved through a “white-box” interaction style with the engine, whereby the plan output cardinalities exposed by the engine are used to compute lower bounds on the error-prone selectivities during plan executions. For this algorithm, the sub-optimality guarantees are in the form of a low order polynomial of the number of error-prone selectivities in the query. The plan bouquet approach has been empirically evaluated on both PostgreSQL and a commercial engine ComOpt, over the TPC-H and TPC-DS benchmark environments. Our experimental results indicate that it delivers orders of magnitude improvements in the worst-case behavior, without impairing the average-case performance, as compared to the native optimizers of these systems. In absolute terms, the worst case sub-optimality is upper bounded by 20 across the suite of queries, and the average performance is empirically found to be within a factor of 4 wrt the optimal. Even with the on-the-fly bouquet algorithm, the guarantees are found to be within a factor of 3 as compared to those achievable in the corresponding canned query environment. Overall, the plan bouquet approach provides novel performance guarantees that open up exciting possibilities for robust query processing.