The increasing complexity and variety of IoT systems require the integration of multiple services to meet a wide range of user needs. This paper addresses the challenge of multi-objective IoT service composition with replication problem by considering multiple Quality of Service (QoS) metrics such as response time and the number of selected service instances. We propose a new Memetic NSGA-II algorithm with Bottleneck-driven Local Search (MNSGA2-BLS) to effectively solve this difficult problem. By integrating genetic operations, clustering-based refinement, and a bottleneck-driven Estimation of Distribution Algorithm for local search, MNSGA2-BLS identifies and optimizes critical service instances causing QoS bottlenecks. This method leverages Pareto-optimal solutions to guide the local search refinement process, enhancing convergence and solution quality. Experimental results across various benchmark cases demonstrate that MNSGA2-BLS can outperform NSGA-II and several state-of-the-art algorithms, achieving superior results in both the hyper-volume and inverse generational distance metrics. This highlights the potential of MNSGA2-BLS to provide efficient and effective composite IoT services while addressing trade-offs between competing QoS objectives.

Dynamic workflow scheduling (DWS) is a challenging and important optimization problem in cloud computing, aiming to execute multiple heterogeneous workflows on dynamically leased virtual machine resources to satisfy user-defined Quality of Service requirements. For the popular deadline-constrained DWS in cloud problem, a virtual machine selection rule (VMSR) and a task selection rule (TSR) need to be designed simultaneously to minimize the rental fee and deadline violation penalty. For this purpose, Dual-Tree Genetic Programming (DTGP) has been previously developed to automatically evolve effective VMSRs and TSRs. However, existing DTGP approaches assume that VMSR and TSR, as well as terminals used by VMSRs and TSRs are equally important and evolve both VMSRs and TSRs in a black box manner, i.e., without using any knowledge about different impacts of trees and terminals. Several recent studies clearly indicate that different trees or terminals have varied performance impacts, making it critical to develop adaptive mutation mechanisms for effective DTGP. Driven by this motivation, this paper proposes two new levels of adaptive mutation mechanisms, contributing to the development of a new DTGP algorithm, which features the use of three new probability vectors for adaptive tree selection of VMSR and TSR at the first level and adaptive terminal selection at the second level while mutating any existing dual-tree individuals. Extensive experimental results demonstrate that the proposed two adaptive mechanisms can improve the effectiveness of DTGP compared to four baseline algorithms.

Internet of Things Service Composition (SCIoT) aims to find the best composite IoT service to fulfil users' requirements. Given the NP-hard complexity of SCIoT, Evolutionary Computation methods, especially Estimation of Distribution Algorithms (EDAs), have received increasing attention to solve SCIoT problems. As one of the most popular EDA methods, Population-Based Incremental Learning (PBIL) has demonstrated its strong competency in optimising composed services in SCIoT. However, conventional PBIL does not explicitly utilize problem knowledge such as QoS and service replication, limiting its effectiveness for IoT service composition. In this paper, we propose a new PBIL based approach, named Population-Based Incremental Learning to Improve Service Composition (PBILISC), to solve the SCIoT problem. Different from traditional PBIL, PBILISC seamlessly integrates PBIL with QoS-aware local search (QLS) to effectively handle replicated services in the SCIoT problem. Specifically, PBILISC evolves a series of populations of solutions jointly through PBIL and QLS. PBIL leverages a probability distribution for population updates, while QLS focuses on improving the best evolved solution by searching promising neighboring solutions under the guidance of QoS. Experimental results show that PBILISC can outperform PBIL and several state-of-the-art methods on multiple benchmark SCIoT problems.

Genetic Programming Hyper-heuristics (GPHH) have been successfully used to evolve scheduling rules for Dynamic Workflow Scheduling (DWS) as well as other challenging combinatorial optimization problems. The method of sampling training instances has a significant impact on the generalization ability of GPHH, yet they are rarely addressed in existing research. This article aims to fill this gap by proposing a GPHH algorithm with a sampling strategy to thoroughly investigate the impact of six instance sampling strategies on algorithmic generalization, including one rotation strategy, three mini-batch strategies, and two hybrid strategies. Experiments across four scenarios with varying settings reveal that: (1) mini-batch with random sampling can outperform rotation in generalizing to unseen workflow scheduling problems under the same computational cost; (2) employing a hybrid strategy that combines rotation and mini-batch further enhances the generalization ability of GPHH; and (3) mini-batch and hybrid strategies can effectively enable heuristics trained on small-scale training instances generalizing well to large-scale unseen ones. These findings highlight the potential of mini-batch strategies in GPHH, offering improved generalization performance while maintaining diversity and suggesting promising avenues for further exploration in GPHH domains.

Service composition in Internet of Things (SCIoT), as an emerging topic in service computing, aims to select optimal services to complete user requests according to various user requirements such as minimizing energy consumption and response time. To solve this NP-hard problem, numerous heuristic methods, e.g., local search and population-based algorithms, have been proposed, wherein Estimation of Distribution Algorithm (EDA) gains increasing attention because of its explicit global probabilistic nature. However, existing EDAs increase solution diversity by using fixed bias, yet interfere the stability of the learned distribution in the later stage of optimization. Therefore, this paper proposes an EDA with an adaptive bias strategy (EDA-AdaBias) to solve the service composition in IoT problem. The decreasing bias value is added onto the probability values for all choices of each solution variable over generations, which improves diversity of sampled solutions and avoids dramatic change of constructed distribution. Experiments indicate that EDA-AdaBias presents promising performance compared to other competitive methods on this problem.

Web service composition composes existing Web services to accommodate users’ requests for required functionalities with the best possible quality of services (QoS). Due to the computational complexity of this problem, evolutionary computation (EC) techniques have been employed to efficiently find composite services with near-optimal functional quality (i.e., quality of semantic matchmaking, QoSM for short) or nonfunctional quality (i.e., QoS) for each composition request individually. With a rapid increase in composition requests from a growing number of users, solving one composition request at a time can hardly meet the efficiency target anymore. Driven by the idea that the solutions obtained from solving one request can be highly useful for tackling other related requests, multitasking service composition approaches have been proposed to efficiently deal with multiple composition requests concurrently. However, existing attempts have not been effective in learning and sharing knowledge among solutions for multiple requests. In this article, we model the problem of collectively handling multiple service composition requests as a new multitasking service composition problem and propose a new permutation-based multifactorial evolutionary algorithm based on an estimation of distribution algorithm (EDA), named PMFEA-EDA, to effectively and efficiently solve this problem. In particular, we introduce a novel method for effective knowledge sharing across different service composition requests. For that, we develop a new sampling mechanism to increase the chance of identifying high-quality service compositions in both the single-tasking and multitasking contexts. Our experiment shows that our proposed approach, PMFEA-EDA, takes much less time than existing approaches that process each service request separately, and also outperforms them in terms of both QoSM and QoS.

As a lightweight and flexible infrastructure solution, containers have increasingly been used for application deployment on a global scale. By rapidly scaling containers at different locations, the deployed applications can handle dynamic workloads from the worldwide user community. Existing studies usually focus on the (dynamic) container scaling within a single data center or the (static) container deployment across geo-distributed data centers. This article studies an increasingly important container scaling problem for application deployment in geo-distributed clouds. Reinforcement learning (RL) has been widely used in container scaling due to its high adaptability and robustness. To handle high-dimensional state spaces in geo-distributed clouds, we propose a deep RL algorithm, namedDeepScale, to auto-scale containerized applications.DeepScaleinnovatively utilizes multi-step predicted future workloads to train a holistic scaling policy. It features several newly designed algorithmic components, including a domain-tailored state constructor and a heuristic-based action executor. These new algorithmic components are essential to meet the requirements of low deployment costs and achieve desirable application performance. We conduct extensive simulation studies using real-world datasets. The results show thatDeepScalecan significantly outperform an industry-leading scaling strategy and two state-of-the-art baselines in terms of both cost-effectiveness and constraint satisfaction.

Quality-of-service (QoS)-aware automated semantic Web service composition aims to find a composite service with optimized or near-optimized QoS and quality of semantic matchmaking within polynomial time. To cope with this NP-hard problem with high complexity, a variety of evolutionary computation (EC) techniques has been developed. To improve the effectiveness and efficiency of these techniques, in this article, we proposed a novel memetic estimation of the distribution algorithm-based approach, namely, MEEDA, to tackle this problem. In particular, MEEDA explores four different domain-dependent local search methods that search for effective composite services by utilizing several neighborhood structures. Apart from that, to significantly reduce the computational time of MEEDA, an efficient local search strategy is introduced by combining a uniform fitness distribution scheme for selecting suitable solutions and stochastic local search operators for effectively and efficiently exploiting neighbors. To better demonstrate MEEDA’s effectiveness and scalability, we create a more challenging, augmented version of the service composition benchmark dataset. Experimental results on this benchmark show that MEEDA with newly developed domain-dependent local search operator, i.e., layer-based constrained one-point swaps, significantly outperforms existing state-of-the-art algorithms in finding high-quality composite services.

Multi-cloud is becoming a popular cloud ecosystem because it allows enterprise users to share the workload across multiple cloud service providers to achieve high-quality services with lower operation cost and higher application resilience. In multi-cloud, cloud services are widely distributed at different locations with differentiated prices. Therefore, Web application providers face the challenge to select proper cloud services for application replication and deployment with the aim of minimizing the deployment cost. Meanwhile, the deployed application replicas must satisfy the constraint on request response time to maintain the quality of user experience. To meet the two major requirements, this article studies a new problem of Web application replication and deployment in multi-cloud (WARDMC) that jointly considers both the cost minimization and constraints on average response time, including particularly request processing time and network latency. To address the problem, we develop a new approach named MCApp. MCApp combines iterative mixed integer linear programming with domain-tailored large neighborhood search to optimize both application replicas deployment and user requests dispatching. Extensive experiments using the real-world datasets demonstrate that MCApp significantly outperforms several recently proposed approaches.

AC machines may be subjected to different electrical or mechanical faults during their operation. Fault patterns can be detected in the DC current from the machine's E-Drive system with the help of Deep or Machine Learning algorithms. However, Deep or Machine Learning algorithms require large amounts of dataset for training and without the availability of a large dataset the algorithms fail to generalize or give their optimal performance. Collecting large amounts of data from faulty machine can be a tedious task. It is expensive and not always possible. In some cases, the machine is completely damaged even before sufficient amount of data can be collected. Also, data collection from defected machine may cause permanent damage to the connected system. Therefore, in this paper the problem of small dataset is tackled by presenting a methodology for large dataset generation by using the well-known generative model, Generative Adversarial Networks (GAN). As an example, the stator open circuit fault in a synchronous machine is considered. DC currents from the machine's E-Drive system are measured from different healthy and faulty machines and are used for training of two 1d DCGANs (Deep Convolutional GANs), one for the healthy and the other for the current signal from the faulty machine. Conventional GANs are difficult to train, however in this paper, training parameters of 1d DCGAN are tuned which results an improved training process. The performance of generator during the training of 1d DCGAN is evaluated by using the Fréchet Inception Distance (FID) metric. The proposed 1d DCGAN model is said to converge when FID score between the real and generated signal reaches below a certain threshold. The generated signals from the trained 1d DCGAN are further evaluated using the PDF (Probability Density Function), frequency domain analysis and other measures which check for duplication of the real data and their statistical diversity. The trained 1d DCGAN is able to generate DC current signals for building large datasets for the training of Deep or Machine learning models.

To gain technical and economic benefits, enterprise application providers are increasingly moving their workloads to the cloud. With the increasing number of cloud resources from multiple cloud providers at different locations with differentiated prices, application providers face the challenge to select proper cloud resources to replicate and deploy applications to maintain low response time and high quality of user experience without running into the risk of over-spending. In this paper, we study the global-wide cloud application replication and deployment problem considering the application average response time, including particularly application execution time and network latency, subject to the budgetary control. To address the problem, we propose a GA-based approach with domain-tailored solution representation, fitness measurement, and population initialization. Extensive experiments using the real-world datasets demonstrate that our proposed GA-based approach significantly outperforms common application placement strategies, i.e., NearData and NearUsers, and our recently proposed hybrid GA approach.

Embedded functional dependencies (eFDs) advance data management applications by data completeness and integrity requirements. We show that the discovery problem of eFDs is NP-complete, W[2]-complete in the output, and has a minimum solution space that is larger than the maximum solution space for functional dependencies. Nevertheless, we use novel data structures and search strategies to develop row-efficient, column-efficient, and hybrid algorithms for eFD discovery. Our experiments demonstrate that the algorithms scale well in terms of their design targets, and that ranking the eFDs by the number of redundant data values they cause can provide useful guidance in identifying meaningful eFDs for applications. Finally, we demonstrate the benefits of introducing completeness requirements and ranking by the number of redundant data values for approximate and genuine functional dependencies.

Enterprise application providers are increasingly moving their workloads to the cloud for technical and economic benefits. Multi-cloud environment makes it possible to orchestrate multiple cloud resources. With the increasing number of available cloud resources provided by multiple cloud providers at different locations with different prices, application providers face the challenge to select proper cloud resources to deploy their applications in the form of a workflow of component service units. Existing studies usually consider minimizing execution time or/and deployment cost. From the perspective of application providers, however, they also pay huge attention to application response time, including particularly network latency between deployed services and users. Meanwhile, application deployment is often subject to stringent budgetary control to ensure financial viability. This article studies a new type of composite application deployment problem that jointly considers both the performance optimization and budget control in multi-cloud at the global scale. To find solutions with minimal response time without running into the risk of over-spending, we propose a hybrid GA-based approach, featuring new design of domain-tailored service clustering, repair algorithm, solution representation, population initialization, and genetic operators. Extensive experiments using the real-world dataset demonstrate that our proposed hybrid GA approach outperforms some recently proposed approaches.

Web services are basic functions of a software system to support the concept of service-oriented architecture. They are often composed together to provide added values, known as web service composition. Researchers often employ Evolutionary Computation techniques to efficiently construct composite services with near-optimized functional quality (i.e., Quality of Semantic Matchmaking) or non-functional quality (i.e., Quality of Service) or both due to the complexity of this problem. With a significant increase in service composition requests, many composition requests have similar input and output requirements but may vary due to different preferences from different user segments. This problem is often treated as a multi-objective service composition so as to cope with different preferences from different user segments simultaneously. Without taking a multi-objective approach that gives rise to a solution selection challenge, we perceive multiple similar service composition requests as jointly forming an evolutionary multi-tasking problem in this work. We propose an effective permutation-based evolutionary multi-tasking approach that can simultaneously generate a set of solutions, with one for each service request. We also introduce a neighborhood structure over multiple tasks to allow newly evolved solutions to be evaluated on related tasks. Our proposed method can perform better at the cost of only a fraction of time, compared to one state-of-art single-tasking EC-based method. We also found that the use of the proper neighborhood structure can enhance the effectiveness of our approach.

Rolling element bearings are one of the most critical components of rotating machinery, with bearing faults amounting up to 50% of the faults in electrical machines. Therefore, the bearing fault diagnosis has attracted attention of many researchers. Typically, the bearing fault diagnosis is performed using vibration signals from the machine. In addition, by using deep learning algorithms on the vibration signals, the fault detection accuracy close to 100% can be achieved. However, measurement of vibration signals requires an additional sensor, which is not present in majority of the machines. Nevertheless, with an alternative approach, the stator current can be used for diagnosis. Therefore, the paper emphasizes on the diagnosis of bearing faults using the stator current. The diagnosis requires signal processing for the fault signature extraction that is buried underneath the noise in the current signal. The paper uses the Paderborn University damaged bearing dataset, which contains stator current data from healthy, real damaged inner raceway and real damaged outer raceway bearings with different fault severity. For fault signature extraction from the current signals, the redundant frequencies in the signals are filtered, then from the filtered signals eight features are extracted from the time and time-frequency domain by using the wavelet packet decomposition (WPD). Then, using these features and the well known deep learning algorithm Long Short-Term Memory (LSTM), bearing fault classification is made. The deep learning LSTM algorithm is mostly used in speech recognition due to its time coherence, but in this paper, the ability of LSTM is also demonstrated with the fault classification accuracy of 96%, which outperforms most of the present algorithms that perform bearing fault diagnosis using stator current. The method developed is independent of the speed and the loading conditions.

Cardinality constraints and functional dependencies can enforce complex business rules within database systems. As the interaction of these constraints is intricate on SQL data, data engineers and domain experts face the challenge of deciding which of the constraints are meaningful for the underlying application domain. We present a tool that computes data samples that perfectly summarize which of the constraints are currently perceived meaningful. It is demonstrated how the tool facilitates the interaction and understanding of data engineers and domain experts to help them separate meaningful from meaningless cardinality constraints and functional dependencies.

The data deluge is defined by increasing amounts of large data with increasing degree of uncertainty. In a recent response, probabilistic databases are receiving a great deal of interest from research and industry. One popular approach to probabilistic databases is to extend traditional relational database technology to handle uncertainty. In this approach probabilistic databases are probability distributions over a collection of possible worlds of relational databases. On the one hand, research has seen various efforts to extend query evaluation from relational to probabilistic databases. On the other hand, updates have not received much attention at all. In this paper we show that well-known syntactic normal form conditions capture probabilistic databases with desirable update behavior. Such behavior includes the absence of data redundancy, insertion, deletion, and modification anomalies. We further show that standard normalization procedures can be applied to standard representations of probabilistic databases to obtain database schemata that satisfy the normal form condition, and can thus be updated efficiently.

We investigate the implication problem for classes of data dependencies over SQL table definitions. Under Zaniolo's “no information” interpretation of null markers we establish an axiomatization and algorithms to decide the implication problem for the combined class of functional and multivalued dependencies in the presence of NOT NULL constraints. The resulting theory subsumes three previously orthogonal frameworks. We further show that the implication problem of this class is equivalent to that in a propositional fragment of Schaerf and Cadoli's [1995] family of para-consistent S-3 logics. In particular, S is the set of variables that correspond to attributes declared NOT NULL. We also show how our equivalences for multivalued dependencies can be extended to Delobel's class of full first-order hierarchical decompositions, and the equivalences for functional dependencies can be extended to arbitrary Boolean dependencies. These dualities allow us to transfer several findings from the propositional fragments to the corresponding classes of data dependencies, and vice versa. We show that our results also apply to Codd's null interpretation “value unknown at present”, but not to Imielinski's [1989] or-relations utilizing Levene and Loizou's weak possible world semantics [Levene and Loizou 1998]. Our findings establish NOT NULL constraints as an effective mechanism to balance not only the certainty in database relations but also the expressiveness with the efficiency of entailment relations. They also control the degree by which the implication of data dependencies over total relations is soundly approximated in SQL table definitions.

Keys allow a database management system to uniquely identify tuples in a database. Consequently, the class of keys is of great significance for almost all data processing tasks. In the relational model of data, keys have received considerable interest and are well understood. However, for efficient means of data processing most commercial relational database systems deviate from the relational model. For example, tuples may contain only partial information in the sense that they contain so-called null values to represent incomplete information. Codd's principle of entity integrity says that every tuple of every relation must not contain a null value on any attribute of the primary key. Therefore, a key over partial relations enforces both uniqueness and totality of tuples on the attributes of the key. On the basis of these two requirements, we study the resulting class of keys over relations that permit occurrences of Zaniolo's null value ‘no-information’. We show that the interaction of this class of keys is different from the interaction of the class of keys over total relations. We establish a finite ground axiomatization, and an algorithm for deciding the associated implication problem in linear time. Further, we characterize Armstrong relations for an arbitrarily given sets of keys; that is, we give a sufficient and necessary condition for a partial relation to satisfy a key precisely when it is implied by a given set of keys. We also establish an algorithm that computes an Armstrong relation for an arbitrarily given set of keys. While the problem of finding an Armstrong relation for a given key set is precisely exponential in general, our algorithm returns an Armstrong relation whose size is at most quadratic in the size of a minimal Armstrong relation. Finally, we settle various questions related to the maximal size of a family of non-redundant key sets. Our results help to bridge the gap between the existing theory of database constraints and database practice.

We study functional and multivalued dependencies over SQL tables with NOT NULL constraints. Under a no-information interpretation of null values we develop tools for reasoning. We further show that in the absence of NOT NULL constraints the associated implication problem is equivalent to that in propositional fragments of Priest's paraconsistent Logic of Paradox. Subsequently, we extend the equivalence to Boolean dependencies and to the presence of NOT NULL constraints using Schaerf and Cadoli's S-3 logics where S corresponds to the set of attributes declared NOT NULL. The findings also apply to Codd's interpretation "value at present unknown" utilizing a weak possible world semantics. Our results establish NOT NULL constraints as an effective mechanism to balance the expressiveness and tractability of consequence relations, and to control the degree by which the existing classical theory of data dependencies can be soundly approximated in practice.

Constraints are important for a variety of XML recommendations and applications. Consequently, there are numerous opportunities for advancing the treatment of XML semantics. In particular, suitable notions of keys will enhance XML's capabilities of modeling, managing and processing native XML data. However, the different ways of accessing and comparing XML elements make it challenging to balance expressiveness and tractability.

Nesting is a useful technique in many areas of database practice. For instance, nesting is a fundamental operation for the nested relational data model, it can be applied to reduce the level of data redundancy in a database instance, to improve query processing or to convert data from one model to another. We further address the question when nesting operations commute with one another, i.e., when the final nested database relation is independent of the order in which the nesting operations are applied. In fact, it has been shown that the satisfaction of weakmultivalued dependencies provides a sufficient and necessary condition for the commutativity of nesting operations. We study inference systems for different notions of implication for weak multivalued dependencies. First, we establish an axiomatisation with the property that every weak multivalued dependency can be inferred either without any application of the complementation rule or by a single application of the complementation rule necessary only in the very last step of the inference. Consequently, the complementation rule is a mere means to achieve a decomposition of the database. Secondly, we drop the assumption of having a fixed underlying schema, and establish an axiomatisation of weak multivalued dependencies for the notion of implication in this context.

We review key constraints in the context of XML as introduced by Buneman et al. We demonstrate that: (1) one of the proposed inference rules is not sound in general, and (2) the inference rules are incomplete for XML key implication, even for nonempty sets of simple key paths. This shows, in contrast to earlier statements, that the axiomatizability of XML keys is still open, and efficient algorithms for deciding their implication still need to be developed. Solutions to these problems have a wide range of applications including consistency validation, XML schema design, data exchange and integration, consistent query answering, XML query optimization and rewriting, and indexing. In this article, we investigate the axiomatizability and implication problem for XML keys with nonempty sets of simple key paths. In particular, we propose a set of inference rules that is indeed sound and complete for the implication of such XML keys. We demonstrate that this fragment is robust by showing the duality of XML key implication to the reachability problem of fixed nodes in a suitable digraph. This enables us to develop a quadratic-time algorithm for deciding implication, and shows that reasoning about this XML key fragment is practically efficient. Therefore, XML applications can be unlocked effectively since they benefit not only from those XML keys specified explicitly by the data designer but also from those that are specified implicitly.

The study of integrity constraints has been identified as one of the major challenges in XML database research. The main difficulty is finding a balance between the expressiveness and the existence of automated reasoning tools for different classes of constraints.

This paper describes a methodology for increasing the scope and precision of diagnostic Knowledge Based (KB) Systems. It has been stated that medical KB systems are either highly specialised, lack accuracy or are just too simple. To resolve this problem of scope we propose the use of a phased approach to diagnosis. The first phase being the querying of a symptoms ontology, to direct diagnostic systems to the most appropriate domain or class reference given input symptoms. Additional symptoms can then be targeted, extracted and analysed with a domain specific set of KB systems. This process allows us to forecast key symptoms, patient characteristics and increase the value of available data in decision making. In addition this approach could allow a system to dynamically correct an inappropriate domain decision. Such an approach also has the potential to be used to build a bridge between existing specialised medical KB systems.

Formal logic has been considered as one of the advanced topics in computing that students do not grasp easily. But the inherent nature of formal logic makes itself a natural choice for forming an overbearing organizing structure, which can be utilized in providing scaffolding during instructional process. This paper discusses the role of formal logic in teaching information science and information systems. We claim that formal logic can be used to realize the modern instruction design principles by ensuring activation of relevant prior knowledge and experiences when learner moves from one topic to another. The paper also describes the successful implementation and evaluation of an on-line teaching tool utilizing predicate logic notation to assist learners in mastering a difficult to learn Unix/Linux system administration command.

Multi-valued depdendencies (MVDs) are an important class of relational constraints. We axiomatise MVDs in data models that support nested list types. In order to capture different data models at a time, an abstract approach based on nested attributes is taken. The set of subattributes of some fixed nested attribute carries the structure of a co-Heyting algebra. This enables us to generalise significant features of MVDs from the relational data model to the presence of lists. It is shown that an MVD is satisfied by some instance exactly when this instance can be decomposed without loss of information. The full power of the algebraic framework allows to provide a sound and complete set of inference rules for the finite implication of MVDs in the context of lists. The presence of the list operator calls for a new inference rule which is not required in the relational data model. Further differences become apparant when the minimality of the inference rules is investigated. The extension of the relational theory of MVDs to the presence of lists allows to specify more real-world constraints and increases therefore the number of application domains.