Nishita Balamuralikrishna

Yingnan Jiang

Henning Koehler
email: h.koehler@massey.ac.nz

Uwe Leck
email: uwe.leck@uni-flensburg.de

Sebastian Link
email: s.link@auckland.ac.nz

Henri Prade
email: prade@irit.fr

OATAO is an open access repository that collects the work of Toulouse researchers and makes it freely available over the web where possible Possibilistic keys

Keywords: Armstrong relation, Axiomatization, Constraint maintenance, Database, Extremal combinatorics, Discovery, Implication, Key, Possibility theory, Uncertain data

Possibility theory is applied to introduce and reason about the fundamental notion of a key for uncertain data. Uncertainty is modeled qualitatively by assigning to tuples of data a degree of possibility with which they occur in a relation, and assigning to keys a degree of certainty which says to which tuples the key applies. The associated implication problem is characterized axiomatically and algorithmically. Using extremal combinatorics, we then characterize the families of non-redundant possibilistic keys that attain maximum cardinality. In addition, we show how to compute for any given set of possibilistic keys a possibilistic Armstrong relation, that is, a possibilistic relation that satisfies every key in the given set and violates every possibilistic key not implied by the given set. We also establish an algorithm for the discovery of all possibilistic keys that are satisfied by a given possibilistic relation. It is shown that the computational complexity of computing possibilistic Armstrong relations is precisely exponential in the input, and the decision variant of the discovery problem is NP-complete as well as W[2]-complete in the size of the possibilistic key. Further applications of possibilistic keys in constraint maintenance, data cleaning, and query processing are illustrated by examples. The computation of possibilistic Armstrong relations and discovery of possibilistic keys from possibilistic relations have been implemented as prototypes. Extensive experiments with these prototypes provide insight into the size of possibilistic Armstrong relations and the time to compute them, as well as the time it takes to compute a cover of the possibilistic keys that hold on a possibilistic relation, and the time it takes to remove any redundant possibilistic keys from this cover.

motivate the introduction and study of possibilistic keys (p-keys) as a fundamental notion for identifying records of uncertain data. Summary. Our article provides a comprehensive study of the new concept of possibilistic keys. The goal is to establish fundamental results about core computational problems associated with possibilistic keys. These include the implication problem, extremal problems, and the problems of computing Armstrong relations for sets of possibilistic keys, and discovering all possibilistic keys that hold on a given p-relation. Solutions to these problems provide computational support to reason about possibilistic keys, acquire possibilistic keys that are meaningful in a given application domain, and estimate worst case scenarios for their maintenance. Detailed experiments complement our theoretical analysis regarding the computational complexity of these problems. Primary application areas of possibilistic keys are found in database design and data cleaning, which have been investigated in related work [START_REF] Köhler | Qualitative cleaning for uncertain data[END_REF][START_REF] Link | Relational database schema design for uncertain data[END_REF]. A case study from web data extraction illustrates the use of possibility degrees in data integration as well as their acquisition. In addition, we will also illustrate the applicability of possibilistic keys in constraint maintenance and query processing. Contributions. Our contributions can be described in detail as follows.

• First, we define a semantics for possibilistic keys. Here, uncertainty is modeled qualitatively by degrees of possibility. The degrees bring forward a nested chain of possible worlds, with each being a classical relation that has some degree of possibility. Smaller worlds are more possible and satisfy at least as many keys as any of the worlds they are contained in. This "possible world" semantics is quite different from that used in the context of probabilistic databases. Our possible worlds form a linear chain with the smallest world forming a kernel that contains all tuples that are certain to occur, and adding tuples that become less possible whenever less constraints are imposed. Classical relations form the special case of possibilistic relations with only two degrees of possibility, that is, where k = 1. For example, the possible worlds of the p-relation from Table 1 are shown in Fig. 1. The key {time, rfid} is satisfied by r 3 but not by r 4 , and {zone, time} is satisfied by r 1 but not by r 2 . • We have conducted a use case study in web data extraction. The case study shows how p-degrees can naturally quantify our confidence in data that is integrated from different sources, which p-keys are satisfied by such possibilistic data, and how the possibilistic data can be summarized by a sample that consists of only 2% of the tuples contained in the original p-relation but satisfies the same p-keys. The sample can be used by business analysts to consolidate which p-keys are meaningful for the application domain. • We then establish axiomatic and linear-time algorithmic characterizations for the implication problem of p-keys.

Our characterizations subsume the axiomatization and linear-time decision algorithm for the implication of classical keys as the special case where k = 1. • Subsequently, we illustrate the applicability of possibilistic keys in the areas of constraint maintenance, data cleaning, and query processing. In constraint maintenance, our algorithm for deciding the implication problem can be used to remove any redundant elements from the set of p-keys whose validity are maintained under updates of possibilistic relations. In classical data cleaning, a minimal set of tuples is usually removed in order to restore the consistency of a given relation with respect to a given set of keys. For possibilistic relations, we minimally lower the degrees of possibility for tuples until consistency of a given possibilistic relation with respect to a given set of p-keys is restored. In query processing, our possibilistic framework makes it possible to rank query answers according to their associated degrees of possibility, and to utilize p-keys for optimizing a given query. • Using extremal combinatorics, we characterize the non-redundant families of p-keys that attain maximum cardinality. This shows how large sets of possibilistic keys may become, providing insight into the worst-case complexity of modeling required. Families of non-redundant classical keys that attain maximum cardinality were characterized by Sperner's theorem, which is subsumed by our result for the special case where k = 1. • Armstrong relations are data samples that exactly represent a given set of business rules. That is, they satisfy the given set and violate all business rules that are not implied by the given set. As such, Armstrong relations help business analysts with the acquisition of classical keys that are meaningful for a given application domain.

A possibilistic relation is said to be Armstrong for a given set of p-keys if and only if for every p-key ϕ, the possibilistic relation satisfies ϕ if and only if ϕ is implied by . We establish structural and computational characterizations of possibilistic Armstrong relations for sets of possibilistic keys. We characterize when a given possibilistic relation is Armstrong for a given set of possibilistic keys. While the problem of finding a possibilistic Armstrong relation is precisely exponential, we establish an algorithm that computes a possibilistic Armstrong relation whose size is guaranteed to be at most quadratic in the size of a minimum-sized possibilistic Armstrong relation. These results subsume the case of Armstrong relations for classical keys for k = 1. • We then show that the complexity of deciding whether a given possibilistic relation satisfies some possibilistic key with at most n attributes is both NP-complete and W [START_REF] Beeri | On the structure of Armstrong relations for functional dependencies[END_REF]-complete in the size of the possibilistic key. It is therefore very unlikely that tractable algorithms for the discovery of possibilistic keys can be found, even when the size of the possibilistic keys are fixed. Using hypergraph transversals, we establish an algorithm that computes a representation for the set of possibilistic keys that hold on a given possibilistic relation. Again, the special case where k = 1 covers the discovery of classical keys from relations. While the computation of Armstrong relations turns a set of possibilistic keys into a possibilistic relation that satisfies only those p-keys that are implied by the given set, the discovery algorithm turns a given possibilistic relation into a set of possibilistic keys that only implies those p-keys that hold on the given relation. • The algorithms for computing possibilistic Armstrong relations and the discovery of possibilistic keys from possibilistic relations have been implemented as prototypes. These prototypes transfer our findings into actual tools that can help business analysts with the acquisition of meaningful possibilistic keys in practice.

• Finally, we have used the prototypes to conduct detailed experiments. For the computation of possibilistic Armstrong relations, we measure the time it takes to compute them as well as their size. We show cases where the size grows exponentially in the input, and other cases where the size grows logarithmically in the input. For randomly created input sets, the output size and computation time each grow low-degree polynomial in the number of given input attributes and for any fixed number of available possibility degrees, and each also grow low-degree polynomial in the number of available possibility degrees and for any fixed number of input attributes. For the discovery problem, we have applied our algorithm to six real-world data sets with varying numbers of attributes and columns after they have been made possibilistic by randomly assigning available possibility degrees to each of their tuples. We compare results for all applicable data sets under different null marker semantics, that is, under null = null and under null = null. We also compare results between a sequential and a parallel implementation of our algorithms.

Organization. The remainder of this article is organized as follows. In Section 2 we compare our work to previous research, emphasizing the lack of a qualitative framework for data dependencies under uncertain data. In the same section, we also briefly summarize the work on other classes of possibilistic data dependencies.

Related work

This section will elaborate on the wider context of work on uncertain data. We will start with the general trade-offs between the use of probabilistic and possibilistic approaches, and highlight some recent work on constraints over probabilistic databases. Subsequently, we will identify database design and data cleaning as the main target areas of our possibilistic model in contrast to other possibilistic data models that target database queries. We will then comment on recent related work on other classes of database constraints that are founded on the possibilistic model we use. We will say how our contributions to possibilistic keys generalize previous findings for the special case of keys over certain relations. Finally, we will detail how our current submission extends our conference article on possibilistic keys.

Probabilistic databases

Probabilistic databases have received much interest [START_REF] Suciu | Probabilistic databases[END_REF] due to the need to deal with uncertain data. While the many types of uncertainty information make it challenging for uncertain data to become first-class citizens in commercial database systems, the benefits and applications of uncertain data are broad and deep. For example, the METIS system is "an industrial prototype system for supporting real-time, actionable maritime situational awareness". It uses web harvesting, information extraction, and data integration to collect substantial data on ships, their routes, and actions. The system represents the uncertainty in this data explicitly, and utilizes the information for reasoning purposes with ProbLog. When coast guards notice ships in their waters, they ask queries of the following type to METIS: "What is the probability of smuggling and how reliable is this assessment?". Given there are more than 300,000 ships in the world and each of them creates a lot of data, this is quite an impressive achievement, and a good motivator to conduct research on uncertain data.

Constraints present a key challenge here: "When the data is uncertain, constraints can be used to increase the quality of the data, and hence they are an important tool in managing data with uncertainties" [START_REF] Dalvi | Management of probabilistic data: foundations and challenges[END_REF]. Suciu et al. emphasize that "the main use of probabilities is to record the degree of uncertainty in the data and to rank the outputs to a query; in some applications, the exact output probabilities matter less to the user than the ranking of the outputs" [START_REF] Suciu | Probabilistic databases[END_REF]. This suggests that a qualitative approach to uncertainty, such as possibility theory [START_REF] Dubois | Possibility theory[END_REF], can avoid the high computational complexity in obtaining and processing probabilities, while guaranteeing the same qualitative outcome.

Research on probabilistic databases has naturally focused on query processing, e.g. [START_REF] Benjelloun | Databases with uncertainty and lineage[END_REF][START_REF] Jha | Probabilistic databases with markoviews[END_REF]. Keys and cardinality constraints on probabilistic databases have been studied in [START_REF] Brown | Probabilistic keys[END_REF][START_REF] Brown | Probabilistic keys for data quality management[END_REF][START_REF] Jha | Query evaluation with soft-key constraints[END_REF][START_REF] Roblot | Probabilistic cardinality constraints[END_REF][START_REF] Roblot | Probabilistic cardinality constraints[END_REF][START_REF] Roblot | Urd: a data summarization tool for the acquisition of meaningful cardinality constraints with probabilistic intervals[END_REF]. Here, [START_REF] Brown | Probabilistic keys[END_REF][START_REF] Brown | Probabilistic keys for data quality management[END_REF][START_REF] Roblot | Probabilistic cardinality constraints[END_REF][START_REF] Roblot | Probabilistic cardinality constraints[END_REF][START_REF] Roblot | Urd: a data summarization tool for the acquisition of meaningful cardinality constraints with probabilistic intervals[END_REF] study similar problems for probabilistic keys and cardinality constraints that we investigate in this article for possibilistic keys. Probabilistic and possibilistic keys complement one another and are incomparable: Probabilistic keys are based on underlying probability distributions, and possibilistic keys are based on underlying possibility distributions. The use of either probabilistic or possibilistic keys therefore depends on what kind of uncertainty information is available and/or required. The paper [START_REF] Jha | Query evaluation with soft-key constraints[END_REF] focuses on the use of probabilistic keys for query optimization.

Possibilistic data models and their target use cases

Similar to probabilistic databases, possibilistic approaches to uncertain data have mainly dealt with query languages. Queries are not the main subject of this article, so we refer the reader to a survey on fuzzy approaches to database querying [START_REF] Zadrozny | An overview of fuzzy approaches to flexible database querying[END_REF]. Nevertheless, we will now comment on various possibilistic data models, their expressiveness, and their main target areas. From the least to the most expressive, we can at least distinguish four possibilistic models for uncertain data [START_REF] Pivert | Handling uncertainty in relational databases with possibility theory -A survey of different modelings[END_REF]:

• databases with layered tuples • tuples involving certainty-qualified attribute values • tuples involving attribute values restricted by possibility distributions, and • possibilistic c-tables.

Layered tuples. This is the data model we use here. The idea is just to provide a total ordering of the tuples in the database according to the confidence we have in their truth. This is encoded by assigning a possibility degree with each tuple. The result is a layered database: all the tuples having the same degree are in the same layer (and only them). The tuples of highest possibility degree are also associated with the highest certainty degree, while tuples with a smaller possibility degree are not certain at all. This means that any possible world contains all the tuples with the highest possibility degree, while the other tuples may or may not be present in a particular possible world, see [START_REF] Link | Possibilistic functional dependencies and their relationship to possibility theory[END_REF] for details. Our model does not provide information about the uncertainty of specific attribute values. Consequently, enforcing the p-degrees on tuples in situations where the degree of uncertainty is known for some attribute values and can be quantified, we would loose some information. On the other hand, there may well be situations where the sources of uncertainty are unclear, cannot be quantified adequately, or where this is not even desired. In this model, the possibility degree of a tuple can be understood as a global function of many (unspecified) factors, or as a simple means to holistically assess the degree of possibility we associate with a tuple. It is the quantity that results from the combination of the uncertainty information present in the given set of attributes. A different way of interpretation, which is closer to the quantification of p-degrees for a value of an attribute, is to take the minimum p-degree associated with the values on the given attributes. This is a trade-off: if specific information (such as the p-degree of an attribute value) is available, we may not be able to express it in less expressive models, but if specific information is unavailable, then we can still express it in less expressive models. The trade-off can be viewed as a generalization of the situation that is already apparent in databases with null markers: SQL permits only one type of null marker, so we lose information whenever we know more about the kind of missing value (e.g. the value exists but is unknown, or the value does not exist). The possibilistic grounding of this model was first presented in [START_REF] Link | Possibilistic functional dependencies and their relationship to possibility theory[END_REF] where the duality between p-degrees and c-degrees is pointed out and exploited, but the model has its roots in an early proposal dealing with weighted tuple databases [START_REF] Kiss | λ-decomposition of fuzzy relational data[END_REF]. The possibilistic model has gained recent momentum in a series of articles that highlight its applications in data modeling [START_REF] Hall | Cardinality constraints on qualitatively uncertain data[END_REF][START_REF] Köhler | Cardinality constraints for uncertain data[END_REF], database design [START_REF] Link | Relational database schema design for uncertain data[END_REF], and data cleaning [START_REF] Köhler | Qualitative cleaning for uncertain data[END_REF]. In [START_REF] Link | Possibilistic functional dependencies and their relationship to possibility theory[END_REF], a new class of possibilistic functional dependencies was introduced, and the equivalence of their associated implication problem to that of Horn clauses in possibilistic logic was proven. The main target area of this new class of possibilistic functional dependencies was database schema design, since different degrees of data redundancy can be introduced and different normal forms guarantee that no redundant data values of these degrees can occur in any instances of the schemata that meet the normal form condition. This normalization framework for uncertain data has been reported in [START_REF] Link | Relational database schema design for uncertain data[END_REF]. Possibilistic keys form the important special case of possibilistic functional dependencies that represent the sub-class of functional dependencies which do not case any form of data redundancy. Possibilistic keys were the first class of database constraints introduced for the underlying possibilistic model [START_REF] Köhler | Logical foundations of possibilistic keys[END_REF]. The current article is an extended version of [START_REF] Köhler | Logical foundations of possibilistic keys[END_REF]. Another important area of application for any form of constraints over this possibilistic model is data cleaning. Here, the details can be found in [START_REF] Köhler | Qualitative cleaning for uncertain data[END_REF]. Basically, the p-degrees of tuples provide a new view of cleaning dirty data: Instead of viewing the data itself as dirty, we view the p-degrees associated with the data as dirty. The c-degrees of constraints then provide guidelines for the cleaning of the p-degrees in the sense that the p-degrees must be lowered minimally to restore consistency with respect to the given c-degrees of constraints. In [START_REF] Hall | Cardinality constraints on qualitatively uncertain data[END_REF][START_REF] Köhler | Cardinality constraints for uncertain data[END_REF], the possibilistic model was used to introduce a new class of possibilistic cardinality constraints. While keys stipulate that there cannot be two different tuples with matching values on all the attributes of the key, cardinality constraints stipulate that there cannot be b + 1 different tuples with matching values on all the attributes of the cardinality constraint. Keys therefore form the important special case of cardinality constraints where b = 1. Certainty-qualified attribute values. In this model [START_REF] Pivert | A certainty-based model for uncertain databases[END_REF], attribute values (or disjunctions thereof) are associated with a c-degree (which is the lower bound of the value of a necessity function). This amounts to associating each attribute value with a simplified type of possibility distribution restricting it. Different attributes in a tuple may have different c-degrees associated with their respective values. This model has some advantages with respect to querying: i) it constitutes a strong representation system for the whole relational algebra, ii) it does not require the use of any lineage mechanism and the query complexity is close to the classical case, and iii) the approach seems more robust with respect to small changes in the value of degrees than a probabilistic handling of uncertainty. Attribute values restricted by general possibility distributions. In this "full possibilistic model" [START_REF] Bosc | About projection-selection-join queries addressed to possibilistic relational databases[END_REF], any attribute value can be represented by a possibility distribution. Moreover, representing the result of some relational operations (in particular the join) in this model requires the expression of dependencies between candidate values of different attributes in the same tuple, which leads to the use of nested relations. In [START_REF] Bosc | About projection-selection-join queries addressed to possibilistic relational databases[END_REF], it is shown that this model is a strong representation system for selection, projection and foreign-key join only. The handling of the other relational operations requires the use of a lineage mechanism as in the probabilistic approaches. This model makes it possible to compute not only the more or less certain answers to a query (as in the previous model), but also the answers which are only possible to some extent. Possibilistic c-tables. This model is outlined in [START_REF] Pivert | Possibilistic conditional tables[END_REF]. The possibilistic extension of c-tables preserves all the advantages of classical c-tables (for expressing constraints linking attribute values) while the attribute values are restricted by any kind of possibility distribution. This model generalizes the two previous ones. In fact, possibilistic c-tables, similar to probabilistic c-tables, can be encompassed in the general setting of the semiring framework proposed by Tannen et al. [START_REF] Green | Provenance semirings[END_REF].

Extending results from keys over certain relations

The present article extends the conference version [START_REF] Köhler | Logical foundations of possibilistic keys[END_REF] in various directions. Firstly, a new section on extremal combinatorics for possibilistic keys has been added. Here, we characterize which families of non-redundant possibilistic keys attain maximum cardinality. The result can be used by data engineers to simulate scenarios where the largest potential number of possibilistic keys must be maintained, and can therefore provide estimates into the worstcase complexity of managing them. Secondly, we prove a new result that the discovery of possibilistic keys is both NP-complete and W [2]-complete in the size of the possibilistic keys. Thirdly, we implemented our algorithms for computing possibilistic Armstrong relations as well as for computing a cover for the set of possibilistic keys that hold on a given possibilistic relation. The graphical user interfaces for these prototype systems are briefly summarized. Fourthly, we used the prototype systems to conduct extensive experiments regarding the time it takes to compute the outputs of both algorithms as well as the size of these outputs. The findings are also discussed in a new section. Fifthly, we have provided full proofs for all our results. Sixthly, we have included a new result on the equivalence of the finite and unrestricted implication problems for p-keys. Seventhly, we have also included the new application area of constraint maintenance in the section on applications for p-keys. Eighthly, we have included a new section on a use case for our possibilistic model and p-keys from web data integration. Finally, the presentation of our findings in [START_REF] Köhler | Logical foundations of possibilistic keys[END_REF] has been substantially revised to add more algorithms, explanations, illustrations, and examples.

Our contributions extend results on keys from classical relations [START_REF] Link | Old keys that open new doors[END_REF], covered by the special case of two possibility degrees where k = 1. These include results on the implication problem [START_REF] Armstrong | Dependency structures of data base relationships[END_REF][START_REF] Diederich | New methods and fast algorithms for database normalization[END_REF], Armstrong relations [START_REF] Beeri | On the structure of Armstrong relations for functional dependencies[END_REF][START_REF] Fagin | Horn clauses and database dependencies[END_REF][START_REF] Hartmann | Design by example for SQL table definitions with functional dependencies[END_REF][START_REF] Mannila | Design by example: an application of Armstrong relations[END_REF][START_REF] Wei | Link DataProf, Semantic profiling for iterative data cleansing and business rule acquisition[END_REF] and the discovery of keys from relations [START_REF] Bläsius | The parameterized complexity of dependency detection in relational databases[END_REF][START_REF] Heise | Scalable discovery of unique column combinations[END_REF][START_REF] Köhler | Discovering meaningful certain keys from incomplete and inconsistent relations[END_REF][START_REF] Mannila | Algorithms for inferring functional dependencies from relations[END_REF][START_REF] Papenbrock | Functional dependency discovery: an experimental evaluation of seven algorithms[END_REF][START_REF] Papenbrock | A hybrid approach to functional dependency discovery[END_REF], as well as extremal combinatorics [START_REF] Demetrovics | Extremal combinatorial problems of database models[END_REF][START_REF] Hartmann | Extremal combinatorics of SQL keys[END_REF][START_REF] Köhler | Possible and certain keys for SQL[END_REF][START_REF] Sali | Keys and Armstrong databases in trees with restructuring[END_REF]. Keys have also been considered in other data models, including incomplete relations [START_REF] Hannula | Automated reasoning about key sets[END_REF][START_REF] Köhler | Possible and certain keys for SQL[END_REF][START_REF] Köhler | Possible and certain SQL keys[END_REF][START_REF] Köhler | SQL schema design: foundations, normal forms, and normalization[END_REF][START_REF] Köhler | SQL schema design: foundations, normal forms, and normalization[END_REF][START_REF] Hartmann | On Codd families of keys over incomplete relations[END_REF][START_REF] Thalheim | On semantic issues connected with keys in relational databases permitting null values[END_REF][START_REF] Wei | Contextual keys[END_REF] and XML data [START_REF] Hartmann | Efficient reasoning about a robust XML key fragment[END_REF][START_REF] Hartmann | Numerical constraints on XML data[END_REF]. Note that Armstrong relations are also an AI tool to acquire and reason about conditional independencies [START_REF] Geiger | Axioms and algorithms for inferences involving probabilistic independence[END_REF][START_REF] Niepert | On the conditional independence implication problem: a lattice-theoretic approach[END_REF].

Possibilistic keys

In this section we extend the classical relational model of data to model uncertain data qualitatively. Based on the data model, we then introduce the notion of a possibilistic key, and illustrate it by examples.

A relation schema, denoted by R, is a finite non-empty set of attributes. Each attribute a ∈ R has a domain dom(a) of values. A tuple t over R is an element of the Cartesian product a∈R dom(a) of the attributes' domains. For X ⊆ R we denote by t (X) the projection of t on X. A relation over R is a finite set r of tuples over R. As example we use the relation schema TRACKING with attributes zone, time, rfid, object from before. Tuples either belong or do not belong to a relation. For example, we cannot express that we have less confidence for the Grizzly identified by rfid value H 3 to be in zone Z3 at 1pm than for the Grizzly identified by H 2.

We model uncertain relations by assigning to each tuple some degree of possibility with which the tuple occurs in a relation. Formally, we have a scale of possibility, that is, a finite strict linear order S = (S, <) with k + 1 elements, denoted by α 1 > • • • > α k > α k+1 . The elements α i ∈ S are called possibility degrees, or p-degrees. The top p-degree α 1 is reserved for tuples that are 'fully possible' to occur in a relation, while the bottom p-degree α k+1 is reserved for tuples that are 'impossible' to occur. Humans like to use simple scales in everyday life to communicate, compare, or rank. Simple means to classify items qualitatively, rather than quantitatively by putting a precise value on it. Classical relations use two p-degrees, that is k = 1.

A possibilistic relation schema (R, S), or p-relation schema, consists of a relation schema R and a possibility scale S. A possibilistic relation, or p-relation, over (R, S) consists of a relation r over R, and a function Poss r that assigns to each tuple t ∈ r a p-degree Poss r (t) ∈ S. Table 1 shows a p-relation over (TRACKING, S = {α 1 , . . . , α 5 }).

P-relations enjoy a possible world semantics. For i = 1, . . . , k let r i consist of all tuples in r that have p-degree at least α i , that is,

r i = {t ∈ r | Poss r (t) ≥ α i }. Indeed, we have r 1 ⊆ r 2 ⊆ • • • ⊆ r k .
The possibility distribution π r for this linear chain of possible worlds is defined by π r (r i ) = α i . Note that r k+1 is not a possible world, since its possibility π(r k+1 ) = α k+1 means 'impossible'. Vice versa, the possibility Poss r (t) of a tuple t ∈ r is the maximum possibility max{α i | t ∈ r i } of a world to which t belongs. If t / ∈ r k , then Poss r (t) = α k+1 . Every tuple that is 'fully possible' occurs in every possible world, and is therefore also 'fully certain'. Hence, relations are a special case of uncertain relations. Fig. 1 shows the possible worlds r 1 r 2 r 3 r 4 of the p-relation of Table 1.

We introduce possibilistic keys, or p-keys, as keys with some degree of certainty. As keys are fundamental to applications with certain data, p-keys will serve a similar role for application with uncertain data. A key K ⊆ R is satisfied by a relation r over R, denoted by |= r K, if there are no distinct tuples t, t ′ ∈ r with matching values on all the attributes in K. For example, the key {time, object} is not satisfied by any relation r 1 , . . . , r 4 . The key {zone, time} is satisfied by r 1 , but not by r 2 . The key {zone, rfid} is satisfied by r 2 , but not by r 3 . The key {time, rfid} is satisfied by r 3 , but not by r 4 . The key {zone, time, rfid} is satisfied by r 4 .

The p-degrees of tuples result in degrees of certainty with which keys hold. Since K 1 = {zone, time, rfid} holds in every possible world, it is fully certain to hold on r. As K 2 = {time, rfid} is only violated in a somewhat possible world r 4 , it is quite certain to hold on r. Since the smallest relation that violates K 3 = {zone, rfid} is the medium possible world r 3 , it is medium certain to hold on r. As the smallest relation that violates K 4 = {zone, time} is the quite possible world r 2 , it is somewhat certain to hold on r. Since {time, object} is violated in the fully possible world r 1 , it is not certain at all to hold on r. The scope of these keys, that is the largest possible world on which they hold, is illustrated in Fig. 1.

Similar to a scale S of p-degrees for tuples we use a scale S T of certainty degrees, or c-degrees, for keys. We use subscripted versions of the Greek letter β to denote c-degrees. Formally, the correspondence between p-degrees in S and the c-degrees in S T can be defined by the mapping α i → β k+2-i for i = 1, . . . , k + 1. Hence, the marginal certainty C r (K) with which the key K holds on the uncertain relation r is either the top degree β 1 if K is satisfied by r k , or the minimum amongst the c-degrees β k+2-i that correspond to possible worlds r i in which K is violated, that is,

C r (K) = β 1 , if r k satisfies K min{β k+2-i | |= r i K} , otherwise .
For the p-relation r from Table 1, we can observe from Fig. 1 that the marginal certainty of

K 1 = {zone, time, rfid} is C r (K 1 ) = β 1 , the marginal certainty of K 2 = {time, rfid} is C r (K 2 ) = β 2 , the marginal certainty of K 3 = {zone, rfid} is C r (K 3 ) = β 3 ,

and the marginal certainty of

K 4 = {zone, time} is C r (K 4 ) = β 4 .
In the same way keys can ensure the integrity of entities in certain relations, possibilistic keys aim at ensuring the integrity of entities in uncertain relations. More precisely, p-keys aim at ensuring the integrity of entities in some of the possible worlds of uncertain relations. For this purpose, we empower p-keys to stipulate that the marginal certainty by which they hold in some uncertain relation must meet a given minimum threshold. This aim is formalized by the following definition.

Definition 1. Let (R, S) denote a p-relation schema. A possibilistic key (p-key) over (R, S) is an expression (K, β) where K ⊆ R and β ∈ S T . A p-relation (r, Poss r ) over (R, S) satisfies the p-key (K, β) if and only if C r (K) ≥ β.
In other words, a p-key (K, β) is violated by a p-relation r if and only if the marginal certainty C r (K) by which the key K holds in r is lower than the minimum c-degree β that has been specified. We illustrate the notion of a p-key on our running example. 1 satisfies the p-key set consisting of

Example 2. The p-relation from Table

• ({zone, time, rfid}, β 1 ), • ({time, rfid}, β 2 ),
• ({zone, rfid}, β 3 ), and • ({zone, time}, β 4 ).

It violates the p-key

({zone, rfid}, β 2 ) since C r ({zone, rfid}) = β 3 < β 2 .

A real-world example from web data integration

In this section we illustrate the application of our framework on a real-world example from Web data integration. Here, basic information about the top-100 best-selling books was extracted from five online book sellers:

1. eBay book store1 2. Amazon book store2 3. book directory3 4. Barnes & Noble4 5. Easons. 5For our collection the tool Web Scraper6 was used on a Chrome extension plugin. It extracted the content from the same HTML tags from every book web page. The extracted results had many mistakes initially, since not all books have the same details and the same HTML tags may also have different values. Errors were fixed manually. In total, 344 tuples were extracted over the p-schema (BOOKS, {α 1 , . . . , α 5 , α 6 }) with BOOKS = {title, author, pages, price, publisher}. For i = 1, . . . , 6, a tuple was assigned p-degree α i if and only if it was contained in 6i of the data sets. The p-degree therefore denotes the possibility by which a book is listed in the top-100 of each book seller. From the resulting p-relation we then applied Algorithm 4 to discover the following set of p-keys that are satisfied by it.

• ({pages, title}, β 1 ), ({price, title}, β 1 ), ({publisher, title}, β 1 ), • ({title}, β 2 ), • ({pages}, β 4 ), ({author, price}, β 4 ), ({price, publisher}, β 4 ), and • ({publisher}, β 5 ).

These p-keys may now be used for the optimization of any queries on the given data set. Note that this is true whether the discovered p-key is meaningful for the given application domain, or not.

With the help of Algorithm 3 we then computed an Armstrong p-relation for the set , and then looked manually for tuples of the original p-relation that had same agree sets as those in the Armstrong p-relation. The benefit is that the resulting Armstrong p-relation consists of real-world tuples and is a subset of the original p-relation. Such Armstrong p-relations are known as informative Armstrong databases [START_REF] Marchi | Semantic sampling of existing databases through informative Armstrong databases[END_REF][START_REF] Wei | Link DataProf, Semantic profiling for iterative data cleansing and business rule acquisition[END_REF]. Informative Armstrong databases may be understood as semantic samples of the original database, since they represent the same set of constraints. Their big advantage is that they are easier to understand by humans because of their smaller size. In our example, the resulting informative Armstrong p-relation is shown in Table 2.

It consists of seven tuples, which is 2% of the number of tuples in the original p-relation. The sample may serve different purposes. It can be understood as a semantic data profile of the given data set, and thus be used for testing purposes, such as queries or updates. This provides data profiling with a different, more user-friendly, perspective of the result set. Another application is business rule acquisition and data cleaning. The aim of business rule acquisition is to identify those constraints which are meaningful in a given application domain. This is usually done with the help of domain experts, who have commonly no knowledge of database constraints but can readily assess samples and provide feedback. Given the sample above, for instance, a domain expert may spot that different books with the same author and title occur in the list. If the original intention of the integration process was to not list multiple books with the same author and title, then the sample would immediately alert domain experts to a violation of this constraint. The feedback to the business analysts would then result in the specification of the p-key ({author, title}, β 1 ). In turn, such p-keys may guide data repairs.

Reasoning tools

The primary purpose of any class of data dependencies is the enforcement of data integrity. In the case of keys, data integrity refers to entity integrity. Enforcing a set of keys on a relation means that any updates to the relation should only be permitted when they result in a new relation that still satisfies all the keys in the given set. Validating that the new relation does satisfy all the keys in the given set consumes time, which should be minimized in order to progress data processing. As such, it is important that the given set of keys does not contain any redundant keys. Here, a key σ is redundant in a given set if and only if σ is implied by -{σ }. Recall that a constraint σ is implied by a constraint set , written |= ϕ, if and only if every relation that satisfies all the constraints in also satisfies σ . In other words, if a key σ is redundant in a given set , then knowing that all the keys in -{σ } are satisfied by the new relation also guarantees us that σ is satisfied by the new relation: We do not need to validate that σ is satisfied by the new relation. This means that the following implication problem is fundamental for the class of p-keys.

PROBLEM: Implication problem

INPUT: A set ∪ {ϕ} of p-keys over p-relation schema (R, S)

OUTPUT: Yes, if |= ϕ No, otherwise
It is the aim of this section to establish axiomatic and algorithmic solutions to the implication problem of p-keys. The solutions capture those for the notion of a classical key by the special case where the number of available p-degree is two, that is, where k = 1. We will first introduce some more terminology and show that, for the class of p-keys, finite and unrestricted implication problems coincide. Subsequently, we will establish a strong correspondence between the implication problem for p-keys and that for classical keys. We will then utilize this correspondence to develop the axiomatic and algorithmic solutions to the implication problem.

Finite and unrestricted implication problems

So far, we have defined relations to be finite set of tuples. In theory, it would also be possible to allow infinite set of tuples as p-relations. This results in two different notions of implication, which we define now. Let ∪ {ϕ} denote a set of p-keys over (R, S). We say (finitely) implies ϕ, denoted by |= (f ) ϕ, if every (finite) p-relation (r, Poss r ) over (R, S) that satisfies every p-key in also satisfies ϕ. Consequently, for the unrestricted implication problem we consider finite and infinite relations, while for the finite implication problem we restrict ourselves to finite relations only. We use * (f ) = {ϕ | |= (f ) ϕ} to denote the (finite) semantic closure of . We will show now that finite and unrestricted implication problem coincide for the class p-keys. That is, for any given set ∪ {ϕ} of p-keys on any given p-relation schema (R, S) it holds that |= ϕ if and only if |= (f ) ϕ. In fact, we can show something stronger: We show that the unrestricted implication problem coincides with the implication problem in two-tuple relations, which we denote by |= 2 . The latter problem is to decide for any given set ∪ {ϕ} of p-keys on any given p-relation schema (R, S), whether |= 2 ϕ holds, that is, whether every two-tuple p-relation over (R, S) that satisfies all the p-keys in also satisfies ϕ. We will now show that all three implication problems coincide for the class of p-keys. Suppose |= ϕ does not hold. Then there is some (possibly infinite) p-relation (r, Poss r ) over (R, S) such that (r, Poss r ) satisfies , but (r, Poss r ) violates ϕ = (K, β i ). Since (r, Poss r ) violates ϕ, there is a smallest possible world r j that violates K and where C r (K) = β k+2-j < β. Since r j violates K, there must be two tuples t 1 , t 2 ∈ r j such that t 1 (K) = / t 2 (K). Let (r ′ , Poss r ′ ) be the two-tuple p-relation over (R, S) where r ′ = {t 1 , t 2 } and Poss r ′ (t 1 ) = Poss r (t 1 ) and Poss r ′ (t 2 ) = Poss r (t 2 ). It follows immediately that for every Notice that p-relation is a two-tuple relation.

(K ′ , β ′ ) ∈ , C r ′ (K ′ ) ≥ C r (K ′ ) ≥ β ′ holds. That is, (r ′ , Poss r ′ ) satisfies all p-keys in . Since (r ′ , Poss r ′ ) violates ϕ = (K, ϕ) it

The magic of β-cuts

For our axiomatic and algorithmic solutions to the implication problem for p-keys we will establish a strong correspondence to the implication problem for classical keys. This is possible because of the sub-model property of p-keys: Whenever a relation satisfies a key, then every sub-relation of the relation will also satisfy the key. A fundamental notion is that of a β-cut, which we define now. We illustrate the definition of β-cuts on our running example.

Example 5. For the p-key set = {(K 1 , β 1 ), (K 2 , β 2 ), (K 3 , β 3 ), (K 4 , β 4 )} from Example 2, we obtain for i = 1, . . . , 4 the following β-cuts β i = i j =1 {K j }.

The fundamental property of β-cuts is given by the following result.

Theorem 2. Let ∪ {(K, β)} be a p-key set over (R, S) where β > β k+1 . Then |= (K, β) if and only if β |= K.

Proof. Suppose (r, Poss r ) is some p-relation over (R, S) that satisfies , but violates (K, β). In particular, C r (K) < β implies that there is some relation r i that violates K and where β k+2-i < β. Let K ′ ∈ β , where (K ′ , β ′ ) ∈ . Since Table 3 Axiomatization K ′ = {T ′ , S ′ } of keys and K = {T , S, B, W} of possibilistic keys.

R (top, T ′ ) K K ∪ K ′ (superkey, S ′ ) (R, β) (K, β k+1 ) (top, T ) (bottom, B) (K, β) (K ∪ K ′ , β) (K, β) (K, β ′ ) β ′ ≤ β (superkey, S) (weakening, W) r satisfies (K, β ′ ) ∈ we have C r (K ′ ) ≥ β ′ ≥ β. If r i violated K ′ , then β > β k+2-i ≥ C r (K ′ ) ≥ β, a contradiction.
Hence, r i satisfies β and violates K.

Let r ′ denote some relation that satisfies β and violates K, w.l.o.g. r ′ = {t, t ′ }. Let r be the p-relation over (R, S) that consists of r ′ and where Poss r

′ (t) = α 1 and Poss r ′ (t ′ ) = α i , such that β k+1-i = β. Then r violates (K, β) since C r (K) = β k+2-i , as r i = r ′ is the smallest relation that violates K, and β k+2-i < β k+1-i = β. For (K ′ , β ′ ) ∈ we distinguish two cases. If r i satisfies K ′ , then C r (K ′ ) = β 1 ≥ β. If r i violates K ′ , then K ′ / ∈ β , i.e., β ′ < β = β k+1-i . Therefore, β ′ ≤ β k+2-i = C r (K ′ ) as r i = r ′ is the smallest relation that violates K ′ . We conclude that C r (K ′ ) ≥ β ′ .
Consequently, (r, Poss r ) is a p-relation that satisfies and violates (K, β). ✷

The following example illustrates an instance of the correspondence that Theorem 2 has established. zone time rfid object Z0 10am H0 Grizzly Z0 3pm H0 Grizzly satisfies the key {time, rfid} that implies both keys in β 2 . However, r 3 violates the key {zone, rfid, object}.

In the following subsections and sections we will make extensive use of Theorem 2.

Axiomatic characterization

We determine the semantic closure by applying inference rules of the form premise conclusion condition .

For a set R of inference rules let ⊢ R ϕ denote the inference of ϕ from by R. That is, there is some sequence σ 1 , . . . , σ n such that σ n = ϕ and every σ i is an element of or is the conclusion that results from an application of an inference rule in R to some premises in {σ 1 , . . . , σ i-1 }. Let + R = {ϕ | ⊢ R ϕ} be the syntactic closure of under inferences by R. R is sound (complete) if for every set over every (R, S) we have + R ⊆ * ( * ⊆ + R ). The (finite) set R is a (finite) axiomatization if R is both sound and complete.

For the set K from Table 3 the attribute sets K, K ′ are subsets of a given R, and β, β ′ belong to a given S T . In particular, β k+1 denotes the bottom certainty degree.

Theorem 3. The set K forms a finite axiomatization for the implication problem of p-keys.

Proof. We prove soundness first. For the soundness of the top-rule T we observe that every possible world is a relation, which means there cannot be any possible world which contains two different tuples that have matching values on all the attributes of the underlying relation schema R. In other words, R is always guaranteed to be a p-key that holds with c-degree β 1 and thus any c-degree. For the soundness of the bottom-rule B we observe that the marginal c-degree of any key in any p-relation is at least β k+1 . For the soundness of the superkey-rule S, let r be a p-relation that satisfies (K, β). Then every possible world of r that satisfies the key K will also satisfy the superkey K ∪ K ′ . Consequently, the marginal certainty of K ∪ K ′ in r is at least as high as the marginal certainty of K in r. Consequently, r will also satisfy (K ∪ K ′ , β). For the soundness of the weakening-rule W let r be a p-relation that satisfies (K, β). That is, the marginal certainty C r (K) of K in r is at least β. Consequently, the marginal certainty C r (K) of K in r is also at least β ′ for every β ′ such that β ′ ≤ β. This shows the soundness of the inference rules.

For completeness, we apply Theorem 2 and the fact that K ′ axiomatizes key implication. Let (R, S) be a p-relation schema with |S| = k + 1, and ∪ {(K, β)} a p-key set such that |= (K, β). We show that ⊢ K (K, β) holds.

For |= (K, β k+1 ) we have ⊢ K (K, β k+1 ) by applying B. Let now β < β k+1 . From |= (K, β) we conclude

β |= K by Theorem 2. Since K ′ is complete for key implication, β ⊢ K ′ K holds. Let β β = {(K ′ , β) | K ′ ∈ β }.
Thus, the inference of K from β using K ′ can be turned into an inference of (K, β) from β β by K, simply by adding β to each key in the inference. Hence, whenever T ′ or S ′ is applied, one applies instead T or S, respectively. Consequently,

β β ⊢ K (K, β).
The definition of β β ensures that every p-key in β β can be inferred from by applying W. Hence,

β β ⊢ K (K, β) means that ⊢ K (K, β). ✷
We illustrate the use of the inference rules on our running example.

Example 7. Let denote the p-key set from Example 2: ({zone, time, rfid}, β 1 ), ({time, rfid}, β 2 ), ({zone, rfid}, β 3 ), and ({zone, time}, β 4 ). Independent of the given , the top-rule T allows us to infer ({zone, time, rfid, object}, β 1 ), and the bottom-rule B allows us to infer p-keys such as ({zone}, β 5 ) or even (∅, β 5 ). From ({time, rfid}, β 2 ) we can infer ({time, rfid, object}, β 2 ) by means of the superkey-rule S, and from the latter p-key we can infer ({time, rfid, object}, β 4 ) by application of the weakening-rule W.

Algorithmic characterization

The axiomatization K from the last subsection enables us to enumerate all p-keys implied by a p-key set . In practice, however, it often suffices to decide whether a given p-key ϕ is implied by . Enumerating all implied p-keys and checking whether ϕ is among them is neither efficient nor does it make good use of the input ϕ. We will now establish an efficient procedure to decide the implication problem for p-keys. The procedure is based on the following result which says that a p-key is implied by a p-key set if and only if it is trivial (i.e. contains all attributes or has bottom c-degree) or there is some p-key in the p-key set whose attribute set is contained in that of the given p-key and whose c-degree is higher than the c-degree of the given p-key.

Theorem 4. Let ∪ {(K, β)} denote a set of p-keys over (R, S) with |S| = k + 1. Then implies (K, β) if and only if β = β k+1 , or K = R, or there is some (K ′ , β ′ ) ∈ such that K ′ ⊆ K and β ′ ≥ β.
Proof. Theorem 2 shows for i = 1, . . . , k that implies (K, β i ) if and only if β implies K. It is known from the relational model of data [START_REF] Thalheim | Dependencies in Relational Databases[END_REF] (or easy to observe from the axiomatization K ′ of keys) that a key K is implied by a key set β if and only if K = R or there is some K ′ ∈ β such that K ′ ⊆ K holds. From the definition of β-cuts it follows that K ′ ∈ β , if (K ′ , β ′ ) ∈ for some β ′ ≥ β. Consequently, the theorem holds for i = 1, . . . , k. Furthermore, implies (K, β k+1 ), so the theorem follows. ✷

We apply Theorem 4 to our running example. c ← ( c -{σ }); 5: return c ; β 5 , {time, rfid, object} does not include zone, and there is no (K ′ , β ′ ) ∈ such that K ′ ⊆ {time, rfid, object} and

β ′ ≥ β 1 .
Theorem 4 can be easily converted into an algorithm for deciding the implication problem of p-keys. The pseudocode for such an algorithm is given in Algorithm 1. The algorithm first checks if the p-key in question is trivial and, if not, then goes through to see if any member satisfies the remaining condition of Theorem 4 for implication. If no member can be found, the p-key is not implied. It is immediate that this algorithm runs in linear time in the input. This section has established axiomatic and algorithmic characterizations for the implication problem of possibilistic keys. These will form the foundation for subsequent sections.

Applications of possibilistic keys

We use this section to outline some important applications of p-keys. This provides further motivation for the study of their properties.

Constraint maintenance

As stated at the beginning of Section 5, the primary purpose of solving the implication problem for p-keys is to minimize the time required for validating sets of p-keys against an updated p-relation. A set c of p-keys is called a non-redundant cover of a given set of p-keys if and only if + c = + and c does not contain any p-key that is redundant. A p-key σ ∈ c is said to be redundant with respect to c if ( c -{σ }) |= σ . It is therefore our aim to compute a non-redundant cover for a given set of p-keys. This can be achieved by applying Algorithm 1 to check for each given p-key σ ∈ whether ( -{σ }) |= σ , and removing σ from whenever that is the case. The pseudo-code of this algorithm is given in Algorithm 2. Let | | denote the cardinality of a given set of p-keys, that is, the number of its elements. Indeed, every set of p-keys has a unique non-redundant cover, given by

c = {(K, β) ∈ | K = R ∧ β < β k+1 ∧ ¬∃(K ′ , β ′ ) ∈ ((K ′ ⊂ K ∧ β ′ ≤ β) ∨ (K ′ ⊆ K ∧ β ′ < β))} .
For that reason we can speak of the non-redundant cover.

Corollary 6. Algorithm 2 computes the non-redundant cover for a given set of p-keys in time O(| | × || ||).

Proof. Algorithm 2 removes successively any redundant p-keys from the input . All remaining members of c are not redundant. The time bound is therefore a consequence of Corollary 5. ✷ Algorithm 2 is non-deterministic due to the different orders in which redundant p-keys may be selected. However, the algorithm is confluent, that is the result is guaranteed to be the unique non-redundant cover. We illustrate the computation of the non-redundant cover on our running example.

Example 9. Let denote the p-key set from Example 2: ({zone, time, rfid}, β 1 ), ({time, rfid}, β 2 ), ({zone, rfid}, β 3 ), and ({zone, time}, β 4 ). It is easily observed that none of the p-keys in is implied by the subset of the remaining given p-keys. In other words, none of the elements in is redundant. Consequently, is its own non-redundant cover.

Data cleaning

In this subsection we illustrate an application of possibilistic keys to data cleaning. In [START_REF] Köhler | Qualitative cleaning for uncertain data[END_REF], possibilistic data cleaning was introduced. In classical data cleaning, a minimal sequence of update operations are applied to the data to restore consistency with respect to given set of constraints. Possibilistic data cleaning offers a new view: It is not the data that is considered to be dirty, but the p-degrees associated with the tuples. In this sense, the p-degrees of tuples are changed minimally such that consistency with respect to the given set of possibilistic constraints is restored. This section illustrates this new view on our running example with respect to the class of possibilistic keys. For details of the algorithm we refer the interested reader to [START_REF] Köhler | Qualitative cleaning for uncertain data[END_REF].

Given that the permitted update operations are limited to tuple deletions, the classical data cleaning problem with respect to keys can be stated as follows: Given a relation r and a set of keys, find a relation r ′ ⊆ r of maximum cardinality such that r ′ satisfies . For example, the relation r (without the two last columns)

r zone time rfid object Poss r Poss ′ r Z3 1pm H2 Grizzly α 1 α 1 Z3 1pm H3 Grizzly α 1 α 2 Z3 3pm H3 Grizzly α 1 α 3 Z4 3pm H3 Grizzly α 1 α 4
violates the set = {zt, zr, tr} of keys. Solutions to the classical data cleaning problem would be the relations r 1 consisting of the first and third tuple, r 2 consisting of the first and last tuple, and r 3 consisting of the second and last tuple. Each solution requires us to remove at least two tuples from the relation. In this sense, classical data cleaning removes valuable information from the given relation. We now consider possibilistic data cleaning as a means to minimize the removal of tuples from a p-relation. For this purpose, we exploit the c-degrees of p-keys to "reduce" the given p-degrees of tuples such that all p-keys will be satisfied.

Given two p-relations (r ′ , Poss r ′ ) and (r, Poss r ) we say that (r ′ , Poss r ′ ) is a p-subrelation of (r, Poss r ), denoted by (r ′ , Poss r ′ ) ⊆ p (r, Poss r ), if and only if r ′ i ⊆ r i for i = 1, . . . , k. The p-subset relationship is simply the partial order of functions induced by the ordering on p-degrees, that is, (r ′ , Poss r ′ ) ⊆ p (r, Poss r ) if and only if Poss r ′ (t) ≤ Poss r (t) holds for all tuples t . The p-cardinality of the p-relation (r, Poss r ) is the mapping C : α i → |r i | for i = 1, . . . , k. We compare p-cardinalities with respect to the lexicographical order, that is,

C 1 < L C 2 :⇔ ∃α i (C 1 (α i ) < C 2 (α i ) ∧ ∀α j < α i (C 1 (α j ) = C 2 (α j )))
The possibilistic data cleaning problem is: Given a p-relation r and set of p-keys, find a p-subrelation r ′ ⊆ p r of maximal p-cardinality so that holds on r ′ .

A point that might seem perhaps controversial in our problem definition is the use of the lexicographic order < L in defining our target function to optimize. We chose this linearization of the natural partial order between p-cardinalities over other candidates for several reasons. Firstly, leximin ordering is appropriate for accounting for the cardinality of level-cuts [START_REF] Dubois | Refinements of the maximin approach to decision-making in a fuzzy environment[END_REF]. Secondly, by maximizing |r ′ k | = |r ′ |, the number of tuples completely "lost" during data cleaning is minimized. Thirdly, it allows one to develop more efficient algorithms for computing it. For example, the p-relation (r, Poss r ) violates the p-key set = {(zt, β 4 ), (zr, β 3 ), (tr, β 2 )}.

However, if we change the p-degree of the second tuple to α 2 , the p-degree of the third tuple to α 3 , and the p-degree of the last tuple to α 4 , then the resulting p-relation (r, Poss ′ r ) satisfies . Note that none of the p-degrees had to be set to the bottom degree α 5 . That is, every tuple in the cleaned p-relation (r, Poss ′ r ) is at least somewhat possible to occur. We refer the interested reader to [START_REF] Köhler | Qualitative cleaning for uncertain data[END_REF] in which a fixed parameter-tractable algorithm has been established for the possibilistic data cleaning problem.

Query processing

We demonstrate the benefit of p-keys on query processing. Therefore, we add the attribute p-degree to the relation schema TRACKING with attributes zone, time, rfid, object.

Suppose we are interested in finding out which grizzly bears have been tracked in which zone, but we are only interested in answers that come from 'certain' or 'quite possible' tuples in the database. A user might enter the following SQL query:

SELECT DISTINCT zone, rfid, p-degree FROM TRACKING WHERE p-degree = α 1 OR p-degree = α 2 ORDER BY p-degree ASC zone rfid p-degree Z0 H0 α 1 Z1 H1 α 1 Z1 H2 α 1 Z3 H2 α 1 Z3 H3 α 2
which removes duplicate answers, and orders them with decreasing p-degree. When applied to the p-relation from Table 1, the query returns the answers on the right. Firstly, our framework allows users to ask such queries, since the p-degrees of tuples is available. Secondly, answers can be ordered according to the p-degree, which is a huge benefit for users in terms of ranking outputs. Thirdly, the example shows how our framework can be embedded with standard technology, here SQL. Finally, recall our p-key ({zone, rfid}, β 3 ) which holds on the set of tuples that have p-degree α 1 or α 2 . Consequently, the query answers satisfy the key {zone, rfid} and the DISTINCT clause becomes superfluous. A query optimizer, capable of reasoning about p-keys, can remove the DISTINCT clause from the input query without affecting its output. This optimization saves response time when answering queries, as duplicate elimination is an expensive operation and therefore not executed by default in SQL databases. P-keys, and the ability to reason about them, have therefore direct applications to query processing.

If we want to use the data model to physically store and manage data, an operational language is required to evaluate queries. Despite being slightly out of scope, we are providing the basic definitions here for selection, projection, and join operations. For a p-relation (r, Poss r ) and X ⊆ R, we define the projection π X (r) = {t (X) | t ∈ r} of r onto X, and Poss π X (r) as Poss π X (r) (t) = max{Poss r (t ′ ) | t ′ ∈ r, t ′ (X) = t}. For a p-relation (r, Poss r ), attribute A ∈ R, and constant c ∈ dom(A), we define the constant selection σ A=c (r) = {t | t ∈ r, t (A) = c}, and Poss σ A=c (r) as Poss σ A=c (r) (t) = Poss r (t) for all t ∈ σ A=c (r). For a p-relation (r, Poss r ), and attributes A, B ∈ R, we define the attribute selection σ A=B (r) = {t | t ∈ r, t (A) = t (B)}, and Poss σ A=B (r) as Poss σ A=B (r) (t) = Poss r (t) for all t ∈ σ A=B (r). Finally, for p-relations (r, Poss r ) and (s, Poss s ) over p-schemata ♯r and ♯s and the same linear orders of p-degrees, we define the join r ⊲⊳ s = {t | ∃t ′ ∈ r, t ′′ ∈ s, t ′ (♯r) = t (♯r), t ′′ (♯s) = t (♯s)}, and Poss r⊲⊳s as Poss r⊲⊳s (t) = min{Poss r (t ′ ), Poss s (t ′′ ) | t ′ ∈ r, t ′′ ∈ s, t ′ (♯r) = t (♯r), t ′′ (♯s) = t (♯s)} for all t ∈ r ⊲⊳ s. Note that these operators can also be defined by their possible worlds. That is, the ith possible world for each of these operations is equal to the classical relational algebra operation applied to the ith possible world of its operands. In particular, (π r ) i = π r i , (σ A=c (r)) i = σ A=c (r i ), (σ A=B (r)) i = σ A=B (r i ), and (r ⊲⊳ s) i = r i ⊲⊳ s i .

Extremal combinatorics for possibilistic keys

In this section we provide answers to fundamental questions concerning the maximum cardinality that nonredundant families of p-keys with at most ℓ attributes can have, and which families attain this cardinality. The result shows data engineers how large families of p-keys can potentially grow, which gives them insight into the complexity of modeling required and clues for reducing this complexity. A characterization of non-redundant families enables us to apply techniques from extremal set theory to answer our questions. The main result is interesting from a combinatorial perspective itself, as it generalizes the famous theorem by Sperner [START_REF] Sperner | Ein Satz über Untermengen einer endlichen Menge[END_REF].

We use the following notations:

[n] = {1, 2, . . . , n} represents sets of attributes, 2 [n] = {S : S ⊆ [n]} the powerset of [n], and 2 [n] ℓ = {S : S ⊆ [n], |S| ≤ ℓ} the elements of 2 [n] with at most ℓ attributes. Recall from before that a set of constraints is non-redundant if for all σ ∈ , σ is not implied by -{σ }. For 0 ≤ ℓ < n and a set ⊆ 2 [n] ℓ × [k] of p-keys (K, i) where i ∈ [k] denotes the index of its c-degree β i , is non-redundant if and only if does not contain two distinct elements (X, i) and (Y, j ) with X ⊆ Y and i ≤ j .

The proof of the following theorem uses the properties that p(F) = {X | (X, i) ∈ F} is a k-Sperner family [START_REF] Engel | Sperner Theory[END_REF], i.e. does not contain chains of length k + 1 and 2 [n] ℓ has the strong Sperner property w.r.t. set inclusion [START_REF] Kleitman | On an extremal property of antichains in partial orders. The Lym property and some of its implications and applications[END_REF][START_REF] Sperner | Ein Satz über Untermengen einer endlichen Menge[END_REF], i.e. the size of the largest k-Sperner family in 2 [n] ℓ is the sum of the min{k, ℓ + 1} largest of the binomial coefficients n i , i = 0, 1, . . . , ℓ.

Theorem 7. Let n, ℓ, k be integers with 0 ≤ ℓ < n and k ≥ 1, and let

G 1 = (X, i) ∈ 2 [n] × [k] : |X| + i = n+k+1 2 , G 2 = (X, i) ∈ 2 [n] × [k] : |X| + i = n+k+1 2 , H = {(X, i) ∈ 2 [n] × [k] : |X| + i = ℓ + 1}. Let F ⊆ 2 [n]
ℓ × [k] such that F does not contain two distinct elements (X, i) and (Y, j ) with X ⊆ Y and i ≤ j .

(i) If ℓ ≥ (n + k -1)/2, then |F| ≤ |G 1 |, where equality holds if F ∈ {G 1 , G 2 }. (ii) If ℓ < (n + k -1)/2, then |F| ≤ |H|, where equality holds if F = H.
Proof. For F ∈ F let p(F ) be its projection to 2 [n] ℓ , i.e., if F = (X, i), then p(F ) = X. By the properties of F , the mapping p : F → 2 [n] is a bijection. Hence, |p(F)| = |F|.

Assume that p(F) contains a chain of length k + 1, that is, there are distinct sets X 1 , . . . , X k , X k+1 ∈ p(F) with

X 1 ⊂ X 2 ⊂ • • • ⊂ X k+1
. By the pigeonhole principle, there must be distinct s, t ∈ [k + 1] such that p -1 (X s ) = (X s , i) and p -1 (X t ) = (X t , i) for some i ∈ [k], contradicting the choice of F . Consequently, p(F) does not contain a chain of length k + 1. In other words, p(F) is a k-Sperner family [START_REF] Engel | Sperner Theory[END_REF].

2 [n] ℓ has the strong Sperner property w.r.t. set inclusion, i.e., for any k the size of the largest k-Sperner family in 2 [n] ℓ is the sum of the min{k, ℓ + 1} largest of the binomial coefficients n i , i = 0, 1, . . . , ℓ. Clearly, |p(F)| = |F| attains this maximum size if F = G 1 or F = G 2 when ℓ ≥ n+k-1 2 and if F = H when ℓ < n+k-1 2 . To see that 2 [n] ℓ has the strong Sperner property, note that [START_REF] Sperner | Ein Satz über Untermengen einer endlichen Menge[END_REF] proved that the poset (2 [n] , ⊆) has the normalized matching property. Such posets are called normal. We refer to Section 4.5 of Engel's book for definition. Now (2 [n] ℓ , ⊆) as a rank-selected subposet of (2 [n] , ⊆) is normal, too. (See Proposition 4.5.3 in [START_REF] Engel | Sperner Theory[END_REF].) Finally, normal posets have the strong Sperner property [START_REF] Kleitman | On an extremal property of antichains in partial orders. The Lym property and some of its implications and applications[END_REF]. ✷ From the above proof and the LYM inequality [START_REF] Engel | Sperner Theory[END_REF] it is easy to derive the following characterization of the extremal F in Theorem 7.

(a) For n > ℓ ≥ (n + k -1)/2, equality holds in Theorem 7(i) if and only if

F ∈ {G 1 , G 2 }. (b) For (n + k -1)/2 > ℓ ≥ k -1, equality holds in Theorem 7(ii) if and only if F = H. (c) For k -2 ≥ ℓ ≥ 0, equality in Theorem 7(ii) if and only if p(F) := {X | (X, i) ∈ F} = 2 [n]
ℓ .

Note that the condition in (a) implies ℓ ≥ k, and the condition in (c) implies ℓ < (n + k -1)/2 and p(H) = 2 [n] ℓ . Fig. 2 shows the case of n = 4 attributes, k = 2 c-degrees other than β k+1 , and ℓ = 2 the maximum size of a key. Unary/binary keys (marked red/green) have c-degree β 2 /β 1 , respectively.

Acquisition tools

New applications benefit from the ability of data engineers to acquire the p-keys that are semantically meaningful in the domain of the application. For that purpose, data engineers communicate with domain experts. Unfortunately, they have to overcome a communication problem which is caused by a mismatch in expertise. Indeed, data engineers know database concepts but not the domain, while domain experts know the domain but not database concepts. It is therefore helpful to translate the knowledge of the data engineers into a format that can be understood by the domain experts. As humans learn a lot from good examples, the goal is to visualize the abstract set of p-keys that data engineers currently perceive as meaningful in the form of a data sample. Here, the data sample should be representative of the abstract p-key set. This means the data sample satisfies all the elements of the set, but violates all the p-keys not implied by the abstract set. The intuitive idea is that domain experts will easily spot cases in which actually meaningful p-keys are violated by the data sample, because they are incorrectly perceived as meaningless by the data engineers. The notion of a representative data sample is also known as an Armstrong database in the research literature.

In this section we will establish two major tools that help data engineers to effectively communicate with domain experts. We follow the framework in Fig. 3. We will first establish an algorithm that data engineers can use to visualize abstract p-key sets in the form of some Armstrong p-relation r . This p-relation is then inspected jointly with the domain experts. The domain experts may change r or supply entirely new data samples to the engineers. For that case we establish an algorithm that computes a non-redundant cover of the set of p-keys that hold in the data sample. In subsequent sections we will describe prototypes that have implemented these algorithms, and report on results we obtained by experimenting with these prototypes.

Structure and computation of Armstrong relations for keys and Armstrong p-relations for p-keys

Keys and relations

We first recall the definition and results for Armstrong relations in the context of relations and keys [START_REF] Beeri | On the structure of Armstrong relations for functional dependencies[END_REF][START_REF] Mannila | Design by example: an application of Armstrong relations[END_REF]. Here, a relation r over relation schema R is Armstrong for a given set of keys over R if and only if for every key K over R it is true that r satisfies K if and only if K is implied by . In this sense, the implication problem for any key by a given key set reduces to checking whether K holds on an Armstrong relation for .

Example 10. Let denote the p-key set from Example 2. Then a non-redundant cover of β 4 consists of the keys {time, rfid}, {zone, rfid}, and {zone, time}. The relation r 1 of Table 1 is an Armstrong relation for β 4 . It satisfies all the given keys, and violates all keys that are not implied by β 4 . For example, the keys {time, object}, {zone, object}, and {rfid, object} are violated by r 1 . In fact, these are the maximal keys (with respect to subset order) that are not implied by β 4 , also known as anti-keys.

In the relational model, a given relation is Armstrong for a given key set if and only if the relation satisfies every given key and violates every anti-key for the given key set. The computation of an Armstrong relation for a given key set therefore involves the computation of the anti-keys for the given key set, followed by the insertion of a new tuple for each anti-key that has matching values with the previous tuple on exactly those attributes that belong to the anti-key. In Example 10, pairs of consecutive tuples have matching values on exactly those attributes that belong to the anti-keys {time, object}, {zone, object}, and {rfid, object}.

P-keys and p-relations

Our goal is now to extend these results to p-relations and p-keys Our first aim is to characterize the structure of Armstrong p-relations. We recall two notions from relational databases. The agree set of two tuples t, t ′ over R is the set ag(t, t ′ ) = {a ∈ R | t (a) = t ′ (a)} of attributes on which t and t ′ have matching values. The agree set of a relation is the set ag(r) = {ag(t, t ′ ) | t, t ′ ∈ r ∧ t = t ′ }. Let denote a set of keys over relation schema R. An anti-key of R with respect to is a subset A ⊆ R such that does not imply the key A over R and for all a ∈ R -A, implies the key A ∪ {a} over R. We denote by -1 the set of all anti-keys of R with respect to . Example 12. Consider the possible world r 4 of the p-relation r in Table 1. Then the set of agree sets of r 4 consists of {time, object}, {object}, {zone, object}, {rfid, object}, {zone, time, object}, {zone, rfid, object}, and {time, rfid, object}.

Let β 1 denote the β 1 -cut of the p-key set from Example 2, that is, β 1 = {zone, time, rfid}. Then the set -1 β 1 of anti-keys consists of {zone, time, object}, {zone, rfid, object}, and {time, rfid, object}.

We will now characterize when a given p-relation is Armstrong with respect to a given set of p-keys. This is the case precisely when every possible world r k+1-i of the given p-relation is an Armstrong relation for the β i -cut of the given p-key set . ,k,β i ⊆ ag(r k+1-i ), and for all K ∈ β i and for all X ∈ ag(r k+1-i ), K X. The agree sets of r 1 consists of to, o, zo, and ro. The agree sets of r 2 include those of r 1 and zto. The agree sets of r 3 include those of r 2 and zro. The agree sets of r 4 include those of r 3 and tro. The β-cuts β of and anti-key sets -1 β are (using the first letters of the attributes): For r 1 we can see that every anti-key in -1 β 4 is also an agree set of r 1 , and that no key in β 4 is contained in an agree set of r 1 . Hence, r 1 is Armstrong for β 4 . For r 2 we can see that every anti-key in -1 β 3 is also an agree set of r 2 , and that no key in β 3 is contained in an agree set of r 2 . Hence, r 2 is Armstrong for β 3 . For r 3 we can see that every anti-key in -1 β 2 is also an agree set of r 3 , and that no key in β 2 is contained in an agree set of r 3 . Hence, r 3 is Armstrong for β 2 . For r 4 we can see that every anti-key in -1 β 1 is also agree set of r 4 , and that no key in β 1 is contained in an agree set of r 4 . Hence, r 4 is Armstrong for β 1 . We conclude, by Theorem 8, that r is an Armstrong p-relation for .

Proof. (r,

• β 1 = {ztr} and -1 β 1 = {zto, tro, zro} • β 2 = {tr} and -1 β 2 = {zto, zro} • β 3 = {tr,
We can now use Theorem 8 to develop an algorithm that computes for a given p-key set an Armstrong p-relation for . The pseudo-code of this algorithm is given as Algorithm 3. It computes for i = 1, . . . , k the sets -1 β i of anti-keys incrementally. Starting with a tuple of p-degree α 1 , for i = k, . . . , 1, each A ∈ -1 β i is realized as an agree set by introducing a tuple that agrees with the previous tuple on A and has p-degree α k+1-i , as long as A did not already occur for some larger i. In fact, if A already occurred for some larger i, then the corresponding agree set has already been realized.

We illustrate Algorithm 3 on our running example.

Example 14. We apply Algorithm 3 to the set from Example 2. Using the first letters of each attribute we obtain Anti-keys are underlined when they are realized as agree sets of tuples in the Armstrong p-relation:

• 1 = {ztr} and -1 β 1 = {zto, tro, zro} • 2 = {tr} and -1 β 2 = {zto, zro} • 3 = {tr,
zone time rfid object Poss. degree c z,0 c t,0 c r,0 c o,0 α 1 c z,1 c t,0 c r,1 c o,0 α 1 c z,1 c t,2 c r,2 c o,0 α 1 c z,3 c t,3 c r,2 c o,0 α 1 c z,3 c t,3 c r,4 c o,0 α 2 c z,3 c t,5 c r,4 c o,0 α 3 c z,6 c t,5 c r,4 c o,0 α 4
Fitting substitution yields the p-relation from Table 1.

Finally, we derive some results regarding the space and time complexity of our algorithm. Here, an Armstrong p-relation for is said to be minimum-sized if and only if there is no Armstrong p-relation for with fewer tuples.

Algorithm 3 Visualize.

Input: P-key set over p-relation schema (R, {β 1 , . . . , β k , β k+1 }) Output: Armstrong p-relation (r, Poss r ) for 1:

-1 0 ← {R -{a} | a ∈ R}; 2: for i = 1, . . . , k do ⊲ Compute -1 β i incrementally 3: i ← {K | (K, β j ) ∈ and j ≤ i}, 4: -1 i ← ANTIKEYS(R, i , -1
i-1 ), 5: for all a ∈ R do 6:

t 0 (a) ← c a,0 ; ⊲ c a,i are fresh constants 7: j ← 0; r ← {t 0 }; P oss r (t 0 ) ← α 1 ; 0 ← ∅; 8: for i = k downto 1 do 9: for all A ∈ -1 i -0 do 10:

j ← j + 1; 11:
for all a ∈ R do ⊲ New tuple with agree set A 12:

if a ∈ A then t j (a) ← t j -1 (a); 13: else t j (a) ← c a,j ;

14: Poss r (t j ) ← α k+1-i ; ⊲ and p-degree α k+1-i 15:

r ← r ∪ {t j };

16: 0 ← 0 ∪ -1 i ; 17: return (r, Poss r ); Subroutine ANTIKEYS(R, , -1 ) Input: R, set of keys in i , -1 set of anti-keys in -1 i-1 Output: -1 set of anti-keys for β i 18: for all K ∈ , A ∈ -1 with K ⊆ A do 19: -1 ← ( -1 -{A}) ∪ a∈K {A -{a}}; 20: -1 ← {A | ∀B ∈ -1 -{A}(A B)}; 21: return -1 ;
Theorem 9. Algorithm 3 computes an Armstrong p-relation for whose size is at most quadratic in that of a minimum-sized Armstrong p-relation for .

Proof. The soundness of Algorithm 3 follows from Theorem 8, which also shows that for

-1 = k i=1 -1 i we have | -1 | ≤ ag(r) ≤ |r| 2 .
The inequalities establish the lower bound in

1 2 • 1 + 8 • | -1 | ≤ |r| ≤ | -1 | + 1.
The upper bound follows from Algorithm 3. Hence, the p-relation computed by Algorithm 3 is at most quadratic in the size of a minimum-sized Armstrong p-relation for . ✷ Finding Armstrong p-relations is precisely exponential. That means that there is an algorithm for computing an Armstrong p-relation whose running time is exponential in the size of , and that there is some set in which the number of tuples in each minimum-sized Armstrong p-relation for is exponential -thus, an exponential amount of time is required in this case simply to write down the p-relation.

Theorem 10. Finding an Armstrong p-relation for a p-key set is precisely exponential in the size of .

Proof. Algorithm 3 computes an Armstrong p-relation for in time at most exponential in its size. Some p-key sets have only Armstrong p-relations with exponentially many tuples in the size of . For R = {a 1 , . . . , a 2n }, S = {α 1 , α 2 } and = {({a 1 , a 2 }, β 1 ), . . . , ({a 2n-1 , a 2n }, β 1 )} with size 2 • n, -1 consists of the 2 n anti-keys n j =1 X j where X j ∈ {a 2j -1 , a 2j }. ✷ Armstrong p-relations for some other p-key sets ′ only require a number of tuples that is logarithmic in the size of ′ . Such a set ′ is given by the 2 n p-keys ( n j =1 X j , β 1 ) where X j ∈ {a 2j -1 , a 2j }. In fact, Algorithm 3 computes an Armstrong p-relation for ′ with n + 1 tuples. For n = 3, for example, we obtain the eight p-keys ({a 1 , a 3 , a 5 }, β 1 ), ({a 1 , a 3 , a 6 }, β 1 ), ({a 1 , a 4 , a 5 }, β 1 ), ({a 1 , a 4 , a 6 }, β 1 ), ({a 2 , a 3 , a 5 }, β 1 ), ({a 2 , a 3 , a 6 }, β 1 ), ({a 2 , a 4 , a 5 }, β 1 ), and ({a 2 , a 4 , a 6 }, β 1 ). These result in the three anti-keys ({a 1 , a 2 , a 3 , a 4 }, β 1 ), ({a 1 , a 2 , a 5 , a 6 }, β 1 ), and ({a 3 , a 4 , a 5 , a 6 }, β 1 ), which produces an Armstrong p-relation with 4 tuples.

It is our recommendation to use both representation of the constraints: the abstract set and an Armstrong prelation for . Later sections will discuss an implementation of Algorithm 3 and results we obtained from experiments with the implementation.

Discovery

We are now addressing the discovery part of our acquisition framework illustrated in Fig. 3. The problem is, given a p-relation over some p-relation schema, compute a cover of the set of p-keys that hold on the p-relation. In other words, given a p-relation we would like to compute a set of p-keys for which the p-relation is Armstrong. This problem was first introduced in [START_REF] Mannila | Dependency inference[END_REF] under the name dependency inference. It is also known as dependency mining or constraint mining, and in recent times the problem is considered to be an important part of data profiling. We will first show that the decision variant of this problem is both NP-complete and W [2]-complete in the size of the p-key, thus illustrating that it is unlikely that there are tractable algorithms to solve this problem, even in case the size of the p-key is fixed. Subsequently, we develop an algorithm based on hypergraph transversals.

The computational complexity of the discovery problem

Before we can state and prove the (parameterized) computational complexity of the p-key discovery problem, we formally state its decision variant and recall some necessary definitions from the area of (parametrized) complexity theory [START_REF] Downey | Parameterized Complexity[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF].

The problem (KEY, n) is to decide whether for a given relation r over relation schema R and a given positive integer n there is some X ⊆ R of size |X| ≤ n such that r satisfies the key X. Note that (KEY, n) does not depend upon asking for a solution of size at most n as opposed to one of size exactly n, since adding attributes to a satisfied key X will result in a satisfied key XY .

Similarly, the problem (P-KEY, n) is to decide whether for a given p-relation (r, Poss r ) over p-relation schema (R, {α 1 , . . . , α k+1 }), a given c-degree β i with 1 ≤ i ≤ k, and a given positive integer n, there is some X ⊆ R of size |X| ≤ n such that (r, Poss r ) satisfies the p-key (X, β i ). Again, (P-KEY, n) does not depend upon asking for a solution of size at most n as opposed to one of size exactly n, since adding attributes to a satisfied p-key (X, β i ) will result in a satisfied p-key (XY, β i ).

For an instance I of a decision problem and a parameter n ∈ N + , the pair (I, n) is an instance of the corresponding parameterized problem. The running time of an algorithm is then considered not only in terms of the input size |I | but also in terms of n. A parameterized problem is fixed-parameter tractable, that is, it belongs to the complexity class FPT, if a given instance can be solved in time O(f (n) • p(|I |)), where p is a polynomial while f is an arbitrary computable function. We then also say that the algorithm runs in FPT-time.

Let P and P ′ be two parameterized problems. A parameterized reduction from P to P ′ is an algorithm running in FPT-time that maps an instance (I, n) of P to an equivalent instance (I ′ , n ′ ) of P ′ such that the parameter n ′ depends only on the value of n (and not on |I |). Note that an (hypothetical) FPT-algorithm for P ′ would also yield an FPT-algorithm for P via this reduction. Hence, considering their parameterized complexity, P is at most as hard as P ′ , which we denote by P ≤ F P T P ′ . If conversely P ′ ≤ F P T P also holds, we say that P and P ′ are FPT-equivalent.

The parameterized reduction leads to a hierarchy of complexity classes, the so-called W -hierarchy, by specifying a complete problem for each class. To define the desired family of problems, we employ Boolean formulas in propositional logic. Let ϕ be such a formula. A satisfying truth assignment for ϕ has Hamming weight n if exactly n variables are set to true in this assignment; we also call the set of these n variables a solution for ϕ. The formula ϕ is t-normalized if it can be written as a conjunction of disjunctions of conjunctions of disjunctions (and so on) of literals with t -1 alternations between conjunction and disjunction. Observe that a Boolean formula is 2-normalized if it is in conjunctive normal form (CNF) and 3-normalized if it is a conjunction of subformulas in disjunctive normal form (DNF).

The problem WEIGHTED T-NORMALIZED SATISFIABILITY is to decide for a given t-normalized formula ϕ and a positive integer n whether ϕ has a weight n satisfying assignment; here n serves as the parameter. For any t ≥ 1, a parameterized problem P is said to be in the complexity class W [t] in case P ≤ F P T WEIGHTED T-NORMALIZED SATISFIABILITY.

The classes F P T ⊆ W [1] ⊆ W [2] ⊆ . . . form an ascending hierarchy and all inclusion are assumed to be proper, which is however still unproven. The higher a problem ranks in the W -hierarchy, the lower the chances are generally considered of finding an FPT-algorithm to solve it.

We are now in a position to state and prove our result about the computational complexity of the p-key discovery problem.

Theorem 11. The problem P-KEY is NP-complete, and W [2]-complete in the size of the p-key.

Proof. For the W [2]-completeness it suffices to show that (KEY, k) ≤ F P T (P-KEY, k) ≤ F P T (KEY, k), since the result follows then from the W [2]-completeness of (KEY, k) in k [START_REF] Bläsius | The parameterized complexity of dependency detection in relational databases[END_REF].

For (KEY, k) ≤ F P T (P-KEY, k) we assume an instance (r, k) of (KEY, k) is given with r being a relation over relation schema R. Now we simply transform r into a p-relation (r, Poss r ) over (R, {α 1 , α 2 }) by assigning the α 1 -degree to each tuple t ∈ r, and assigning the α 2 -degree to each tuple t / ∈ r. Consequently, a k(X) over R with |X| ≤ k is satisfied by r if and only if the p-key (k(X), β 1 ) over (R, {α 1 , α 2 }) with |X| ≤ k is satisfied by (r, Poss r ). Note that the transformation is the identity on k.

For (P-KEY, k) ≤ F P T (KEY, k) we assume an instance ((r, Poss r ), β i , k) of (P-KEY, k) is given with (r, Poss r ) being a p-relation over p-relation schema (R, {α 1 , . . . , α k+1 }) and 1 ≤ i ≤ k. Now we simply transform (r, Poss r ) into the relation r k+1-i = {t ∈ r | Poss r (t) ≤ α k+1-i } over R. Consequently, a p-key (k(X), β i ) over (R, {α 1 , . . . , α k+1 }) with |X| ≤ k is satisfied by (r, Poss r ) if and only if the key k(X) over R with |X| ≤ k is satisfied by r k+1-i . Note that the transformation is the identity on k.

The FPT-reductions show, in particular, that (KEY, k) and (P-KEY, k) are PTIME-equivalent, too. Since (KEY, k) is NP-complete [START_REF] Beeri | On the structure of Armstrong relations for functional dependencies[END_REF], it follows that (P-KEY, k) is NP-complete, too. ✷

The experimental results from Section 10 regarding the discovery of p-keys should be viewed in light of Theorem 11.

Algorithmic solution

In the relational model, a key ensures that for each pair of distinct tuples there is some attribute of the key on which the tuples have different values. A good strategy to discover all (minimal) keys is therefore to compute for all pairs of distinct tuples their disagree set, that is, the set of attributes on which they have different values, and then compute all minimal sets of attributes which intersect non-trivially with every disagree set. The latter problem is also known as the hypergraph transversal problem [START_REF] Eiter | Identifying the minimal transversals of a hypergraph and related problems[END_REF], whose exact complexity is still open. We will now adopt this strategy to the computation of all p-keys that hold on a given p-relation.

More formally, a hypergraph (V , E) consists of a vertex set V and a set E of subsets of V , called hyperedges. A set T ⊆ V is a transversal of (V , E) if for all H ∈ E, T ∩ H = ∅ holds. A transversal T of (V , E) is minimal if there is no transversal T ′ of (V , E) such that T ′ T [START_REF] Eiter | Identifying the minimal transversals of a hypergraph and related problems[END_REF]. With this terminology, we can now explain the pseudo-code of Algorithm 4, which computes a non-redundant cover for the set of p-keys that hold on the given p-relation. In lines (1-4), Algorithm 4 computes, for i = 1, . . . , k, the minimal transversals of the hypergraph that has the underlying attributes as vertex set and minimal disagree sets of tuples from world r i as hyperedges. These form a cover of the set of minimal keys that hold on r i . The marginal certainty of those keys in the given p-relation is thus at least β k+1-i . Line [START_REF] Bosc | About projection-selection-join queries addressed to possibilistic relational databases[END_REF] takes the union of the p-keys that originate from the possible worlds. Finally, Theorem 4 is used to select only those p-keys that are not implied by the other p-keys.

We illustrate Algorithm 4 on our running example.

Example 15. We apply Algorithm 4 to the p-relation from Table 1. Using the first letters of each attribute we obtain

• dis-ag(r 1 ) = {zr, tr, zt} and 1 = {(zr, β 4 ), (tr, β 4 ), (zt, β 4 )}

• dis-ag(r 2 ) = {zt, r} and 2 = {(zr, β 3 ), (tr, β 3 )} • dis-ag(r 3 ) = {t, r} and 3 = {(tr, β 2 )}, and • dis-ag(r 4 ) = {z, t, r} and 4 = {(ztr, β 1 )}.

A non-redundant cover for the p-keys that hold on the p-relation consists of (ztr, β 1 ), (tr, β 2 ), (zr, β 3 ), and (zt, β 4 ).

Algorithm 4 Discover.

Input: (r, P oss r ) over (R, {β 1 , . . . , β k+1 }) Output: Non-redundant cover of the set of p-keys that are satisfied by (r, P oss r ) 1: Proof. The soundness follows from the result that the keys of a relation are the minimal transversals of the disagree sets in the relation [START_REF] Demetrovics | Extremal combinatorial problems of database models[END_REF][START_REF] Mannila | Algorithms for inferring functional dependencies from relations[END_REF], and Theorem 4. The collection dis-ag(r i ) is computed in time O(m). The set of all minimal transversals for the simple hypergraph H i is computed in time O(n 2 ). Algorithm 4 can compute the minimal hypergraphs incrementally with additional disagree sets discovered from tuples with lower p-degrees. ✷ Subsequent sections will discuss an implementation of Algorithm 4 and results we obtained from experiments with the implementation.

for i = 1, . . . , k do 2: dis-ag(r i ) ← min{X ⊆ R | ∃t, t ′ ∈ r i ∀a ∈ R(t (a) = t ′ (a) ↔ a ∈ X)}; 3: H i ← (R, dis-ag(r i )); 4: i ← {(K, β k+1-i ) | K ∈ Tr(H i )}; 5: ← k i=1 i ; 6: ← {(K, β) ∈ | ¬∃(K ′ , β ′ ) ∈ (K ′ ⊆ K ∧ β ′ > β)};

Prototype systems for visualization and discovery

This section briefly introduces two graphical user interfaces that provide access to implementations of Algorithm 3 and Algorithm 4, respectively. Section 10 will discuss the results of various experiments with these interfaces. The following section will discuss the outcomes of detailed experimental studies with the implementations of this section. We briefly outline the steps, which are illustrated on our running example in Fig. 4. In step 1 (top left of Fig. 4), the user enters the column names of the p-relation schema, the index of the bottom c-degree, together with the column names of the c-degree of a new p-key. Pressing the 'insert' button shows in step 2 (top right of Fig. 4) the p-relation schema together with all the p-keys that have been entered so far. Pressing the 'save' button in step 2, will invoke the execution of Algorithm 3, and produce several results.

Possibilistic Armstrong relation tool

Result 3 (bottom right of Fig. 4) shows the corresponding Armstrong p-relation for the input set of p-keys from step 2. Intermediate results of the computation are shown in the bottom left of Fig. 4. These include the anti-keys (Result 1) and the agree sets (Result 2).

The bottom right of Fig. 5 shows the GUI after executing Algorithm 3 on our running example. The output shows a p-relation that is Armstrong for the input, and has the same agree sets as our p-relation from Table 1.

Possibilistic key finder tool

Fig. 5 shows the GUI of our Possibilistic Key Finder tool. It provides access for users to an implementation of Algorithm 4. The tool computes for an input p-relation r a non-redundant cover for the set of p-keys that hold on r.

The input p-relation can be supplied in the form of a csv file (left of Fig. 5), or entered manually (right of Fig. 5) in the GUI. In both cases, the input is expected to have a column called p_degree which contains the index of the p-degree for each tuple. If such a column is not present, the implementation will assume that the p-degree of each tuple is β 1 . The GUI also contains an input field called 'Maximum P Degree'. If no value is entered, then the implementation will pick the lowest p-degree (the one with the highest index) associated with any tuple in the input p-relation (and β 1 in case that no column of name p_degree exists). Using our notation from before, 'Maximum P Degree' denotes the index k. It should be noted that k can be higher than any p-degree found in the input p-relation.

The bottom of the GUI displays several results. It shows the time taken to compute (a possibly redundant) cover of the set of p-keys that hold on the input p-relation, the set of p-keys itself, the cardinality of this set, and the total number of key attributes in this set. It then shows the time taken to convert the possibly redundant cover into a non-redundant cover, the p-keys in the non-redundant cover, the cardinality of the non-redundant cover, and the total number of key attributes in the non-redundant cover.

The right of Fig. 5 shows the GUI after executing Algorithm 4 on our running example. The output shows exactly the non-redundant cover that we have worked with throughout the article.

Experimental results with visualization and discovery

This section will discuss the outcomes of detailed experimental studies we have conducted with the implementations of Algorithm 3 for the computation of Armstrong p-relations, and Algorithm 4 for the computation of the p-keys that hold on a given p-relation. They provide some insight on the actual size of Armstrong p-relations and the time it takes to compute them, as well as on the time to find the p-keys that hold on a given p-relation and the savings one can achieve by computing non-redundant covers.

Visualization

We will first explain our experiments with the computation of Armstrong p-relations using Algorithm 3. Here we distinguish between three different cases. Firstly, we will look at a worst-case in which the size of the output grows exponential in the size of the input, and thus Algorithm 3 also takes exponential time. Secondly, we will look at a good case in which the size of the output grows logarithmically in the size of the input. Finally, we will look at a random case in which the input set of p-keys is randomly generated.

Exponential case

The exponential case is taken from the proof of Theorem 10, where for positive integers n, R = {a 1 , . . . , a 2n }, S = {α 1 , α 2 } and = {({a 1 , a 2 }, β 1 ), . . . , ({a 2n-1 , a 2n }, β 1 )} forms the input of size 2 • n. The set -1 consists of the 2 n anti-keys n j =1 X j where X j ∈ {a 2j -1 , a 2j } for j = 1, . . . , n.

Fig. 6 shows the size of the resulting Armstrong p-relations the case where n = 1, . . . , 10, as well as the times (in ms) to compute them. For each the size and time, the actual experimental results are approximated (very closely) by an exponential function.

Logarithmic case

The logarithmic case is taken from the paragraph following Theorem 10, where for positive integers n, R = {a 1 , . . . , a 2n }, S = {α 1 , α 2 } and ′ = {(∪ n j =1 X j , β 1 ) | X j ∈ {a 2j -1 , a 2j }} forms the input with 2 n p-keys. The set -1 consists of the n anti-keys R -{a 2j -1 , a 2j } for j = 1, . . . , n. Fig. 7 shows the size of the resulting Armstrong p-relations for the cases where n = 1, . . . , 10, as well as the times (in ms) to compute them. For the size, the actual experimental results are approximated perfectly by a logarithmic function. For the time, the experimental results are closely approximated by a quadratic function.

Average case

The most interesting case may be the average-case behavior, that we mimicked by randomly creating for a given number n = 2, . . . , 15 of attributes and a given bottom p-degree of k + 1 = 2, . . . , 20, 500 sets of p-keys, and then taking the average size (number of tuples) and time to compute an Armstrong p-relation for by Algorithm 3. Each of the input sets contained up to n 2 p-keys with two attributes on average. All experiments were conducted on an Intel Core i7-4600U 2.10 GHz machine that has 8 GB of RAM.

We were interested in the impact of the given number of attributes as well as the given number of available pdegrees for both measures, size and time. For that purpose, we display our results in two different figures.

Fig. 8 shows the size and time in terms of the growing number of attributes, for different fixed numbers of available p-degrees. The graphs suggest that both, the size of the output and the time to compute the output, grow low-degree polynomial in the input.

Fig. 9 shows the size and time in terms of the growing number of available p-degrees, for different fixed number of given attributes. As before, the graphs suggest that both, the size of the output and the time to compute the output, grow low-degree polynomial in the input.

Discovery

We will now discuss our experiments with the possibilistic key finder tool that implemented Algorithm 4. The algorithm was applied to possibilistic variants of seven real-world data sets plus one synthetic data set, called fdreduced-30. The synthetic data set was generated with the dbtesma data generator [START_REF] Papenbrock | Functional dependency discovery: an experimental evaluation of seven algorithms[END_REF][START_REF] Papenbrock | A hybrid approach to functional dependency discovery[END_REF]. All the other data sets have been obtained from the UCI Machine Learning Repository [START_REF] Lichman | UCI Machine Learning Repository[END_REF]. Table 4 shows the basic characteristics of the various data sets. They comprise a reasonable range of column and row numbers. It should be pointed out here that big data sets, with say 50 columns and 1 million rows, resist state-of-the-art data dependency mining algorithms [START_REF] Papenbrock | Functional dependency discovery: an experimental evaluation of seven algorithms[END_REF][START_REF] Papenbrock | A hybrid approach to functional dependency discovery[END_REF]. As indicated previously, the data sets are not possibilistic, so they were made possibilistic by randomly assigning values between 1 and k for each tuple in the data set. For our experiments, k was either 1, 5, 10, or 15. All the experiments were performed on a Windows 7, 64 bit machine with four 3.30 GHz processors, 8 GB RAM, 930 GB hard disk and 64bit Java 7.0.

Apart from discussing various measures on the basis of the given data sets, we will also briefly discuss the semantics that is associated with null marker occurrences, as well as a parallel approach towards the discovery of p-keys from the data sets. Note that it is not our aim to judge the meaningfulness of the discovered keys. One cannot determine the meaningfulness of a constraint from whether it holds or does not hold on a given data set. Such judgment would require domain expertise. In the possibilistic case, it is even more difficult to comment on the meaningfulness since the concept of p-relations and p-constraints are new, so even domain expertise would not really be available. Just like previous research [START_REF] Papenbrock | Functional dependency discovery: an experimental evaluation of seven algorithms[END_REF][START_REF] Papenbrock | A hybrid approach to functional dependency discovery[END_REF] we therefore focus on the performance of our discovery algorithms.

Results of experiments with given data sets

We will now present our findings of applying Algorithm 4 to the possibilistic variants of the given data sets. Several of the data sets contained duplicate tuples, i.e. tuples which had matching values on all the underlying attributes. In such cases, no key can exist, and we therefore only kept one of the tuples for which duplicate tuples exist. The efficiency of the key finder tool is measured in terms of the computation time in seconds, the number of p-keys found, and the total number of attributes that occur in the output. We provide these measures for each data set, and each value of k = 1, 5, 10, and 15, and distinguish between the output (RC) derived directly from merging the p-keys found in each possible world, and the non-redundant cover (NRC) derived from the previous output by removing any redundant p-keys. For each data set, and for each value of k, the experiments were repeated 5 times and the averages were computed for time taken, the number of p-keys discovered, and the size of the output, for RC and NRC, respectively.

Table 5 shows all these measures for the k-values 1 and 5, and Table 6 shows the measures for the k-values of 10 and 15. The value ML refers to the event that the experiment exceeded the memory limit of 4 GB. For the non-redundant cover (RC), computation time refers to the time taken to compute the non-redundant cover (NRC) from the redundant cover (RC).

The mining work the fastest on the smallest data set, Iris, which also has the least number of p-keys found. The Abalone data set has significantly more rows than iris and breast-cancer. The values of k have limited impact on the computation times for this data set. For the breast-cancer data set the computation time is faster than for abalone. For this data set, the value of k does again not affect the computation time much. The adult data set more rows and columns than the previous data sets. In this case, the computation time is also much higher than that on the previous data sets. The value of k is seen to have a considerable effect on the efficiency. The letter data set has more columns than the above mentioned data sets, but has only 20,000 rows while adult has 48,842 rows. For this data set, p-key mining takes less time than that of the adult data set, even though there are more columns. The hepatitis data set has considerably more columns [START_REF] Green | Provenance semirings[END_REF] and few rows. In this case, the computation time increases proportionally with the increases of k. The horse data set has a high number of columns [START_REF] Hartmann | Numerical constraints on XML data[END_REF] but few rows. In this case the computation time increases substantially with increases in k. The synthetic data set fd-reduced-30 has a high number of rows and columns. In this scenario, the algorithm does not return an output as the data set does not fit into memory.

Regarding our experiments we make the following observations. The algorithm performs well on data sets which have a modest number of rows or columns. Data sets that have a larger number of columns (e.g. 30) and a larger number of rows (e.g. 250,000) are difficult to handle. The savings achieved by removing redundant p-keys can be significant (and the larger data sets are the more savings will be made in terms of the time required to validate the p-keys). In addition, the removal of redundant p-keys takes little time in comparison to the computation of the p-keys. The time taken to remove redundant p-keys increases with the value of k. This be attributed to the fact that the number of p-keys increases as the value of k grows. For k = 1, the possibilistic relation corresponds to data coming from a relational table and the p-key cover represents the minimal candidate keys of the corresponding relational table. In this case there are no redundant p-keys. For data sets with more columns and few tuples, such as horse and hepatitis, the performance degrades as the k value increases. This is attributed to the disagree sets being larger on average and hence requiring more time to compute the hypergraph transversals. Fig. 10a shows that for the hepatitis data set, hypergraph transversal consumes more time than the time taken to obtain the minimal disagree sets. For data sets with more columns and few rows, such as horse and hepatitis, the size of the cover is larger than that for data sets with few columns and more rows, such as adult and letter. This may be attributed to the fact that with fewer tuples it takes more columns to generate non-empty intersections for the participating larger disagree sets. For larger numbers of rows, for example in the letter and adult data sets, it can be seen from Fig. 10c and Fig. 10b that the main contribution to computation time comes from tuple comparisons during the computation of the disagree sets. As the value of k increases, it is expected that the number of keys increase. This behavior is attributed to the increase in possible worlds when k grows. The algorithm conforms to this behavior.

Null semantics

The basis for our experiments were data sets from the real world. It is therefore natural for null markers, denoted by null, to occur. For two tuples t and t ′ with null marker occurrences in column a, two semantics are possible: t[a] == t ′ [a] or t[a] = t ′ [a]. Since these semantics result in the discovery of different p-keys, the user can choose which semantics is adopted by the implementation of our algorithm. The semantics where null == null results in more p-keys, as shown in Fig. 11.

Parallelization

So far, our experiments have been conducted with a sequential implementation of Algorithm 4. Here, the classical key discovery algorithm is applied to each possible world, and the results are merged by assigning corresponding c-degrees, and then removing any redundant p-keys from the result. As the possible worlds are nested, all tuples of a smaller world are included in a bigger world. In particular, it is unnecessary to re-compute the disagree sets of tuples for which this has already been done beforehand. As an alternative approach, one may apply the classical key discovery algorithm to the possible worlds in parallel. The disadvantage is that for each tuple pair that is contained in several possible worlds, their disagree sets must be computed for each of these possible worlds. Table 7 shows the average number of p-keys and the size of the redundant p-key cover on several data sets. These numbers deviate slightly between the sequential and parallel approach, because of the different assignments of p-degrees to tuples. The computation time for both approaches is compared in Fig. 12.

For data sets with few rows and many columns, such as hepatitis, the computation time for the hypergraph transversal is high in comparison to the time for computing minimal disagree sets, as shown in Fig. 10a. In such cases, the time taken for redundant disagree set computations is negligible compared to the hypergraph transversal times. Hence, data sets with few rows but many columns show a better performance in the parallel approach. However, when the value of k increases, then the number of redundant disagree set computations increases as well, and will become a bottleneck in the parallel approach. Indeed, Fig. 12 shows for most data sets that the sequential approach becomes more efficient than the parallel approach from a value of k = 5 onwards.

Conclusion and future work

Possibilistic keys have been introduced to efficiently identify tuples in uncertain data. Uncertainty is modeled qualitatively by applying the AI framework of possibilistic logic to the fundamental database concept of keys. Tools were established to efficiently reason about possibilistic keys, and applications of p-keys in constraint maintenance, data cleaning, and query processing were outlined in detail. It was characterized which non-redundant families of p-keys attain maximum cardinality, a result that enables data engineers to simulate data processing under heavily

  Our possibilistic data model and possibilistic keys are formally introduced in Section 3. The use case study about web data extraction is presented in Section 4. Axiomatic and algorithmic characterizations of the associated implication problem are established in Section 5. In Section 6, applications of possibilistic keys in constraint maintenance, data cleaning, and query processing are illustrated by examples. Combinatorial results on the maximum cardinality of non-redundant families of possibilistic keys are established in Section 7. Possibilistic Armstrong relations are investigated in Section 8, where we also study the problem of discovering the set of possibilistic keys from a given possibilistic relation. The prototype systems for the computation of Armstrong relations and the discovery problem are briefly described in Section 9. Section 10 presents and discussed our experimental results related to the computation of Armstrong relations and the discovery problem. Finally, Section 11 concludes and outlines future work.

Fig. 1 .

 1 Fig. 1. Worlds of possibilistic relation and scope of keys.

Example 3 .

 3 follows that |= 2 ϕ does not hold. This completes the proof. ✷ Theorem 1 allows us to speak about the implication problem for the class of p-keys. The following example shows an instance of the implication problem on our running example. Let be as in Example 2, and ϕ = ({zone, rfid, object}, β 2 ). Then does not imply ϕ as the following p-relation witnesses:zone time rfid object p-degree Z0 10am H0 Grizzly α 1 Z0 3pm H0 Grizzly α 3

Definition 4 .

 4 Let denote a set of p-keys over p-relation schema (R, S) with |S| = k + 1, and let β ∈ S T denote a c-degree where β > β k+1 . Then β = {K | (K, β ′ ) ∈ and β ′ ≥ β} denotes the set of keys for which a p-key exists in whose c-degree is at least β. The key set β is called the β-cut of the p-key set .

Example 6 .

 6 Let ∪ {ϕ} be as in Example 3. Theorem 2 says that β 2 does not imply ({zone, rfid, object}, β 2 ). The possible world r 3 of the p-relation from Example 3:

Example 8 .Algorithm 1 Algorithm 2

 812 Let denote the p-key set from Example 2: ({zone, time, rfid}, β 1 ), ({time, rfid}, β 2 ), ({zone, rfid}, β 3 ), and ({zone, time}, β 4 ). Independent of the given we can use Theorem 4 to observe that p-keys such as ({zone, time, rfid, object}, β 1 ), ({zone}, β 5 ) or even (∅, β 5 ) are implied. The p-key ({time, rfid, object}, β 4 ) is implied by because the given p-key ({time, rfid}, β 2 ) ∈ meets the conditions of Theorem 4 that {time, rfid} ⊆ {time, rfid, object} and β 2 ≥ β 4 . In contrast, the p-key ({time, rfid, object}, β 1 ) is not implied by since β 1 = β k+1 = Implication. Input: Set ∪ {(K, β)} of p-keys over p-relation schema (R, S) with |S| = k + 1 Output: Yes, if |= (K, β), and No, otherwise 1: if K = R or β = β k+1 then 2: return true; 3: else 4: for all (K ′ , β ′ ) ∈ do 5: if K ′ ⊆ K and β ′ ≥ β then 6: Non-redundant cover. Input: Set of p-keys over p-relation schema (R, S) Output: A non-redundant cover c ⊆ 1: c ← ; 2: for all σ ∈ c do 3: if ( c -{σ }) |= σ then 4:

Corollary 5 .

 5 An instance |= ϕ of the implication problem for p-keys can be decided in time O(|| ∪ {ϕ}||) where || || denotes the total number of symbol occurrences in .

Fig. 2 .Fig. 3 .

 23 Fig. 2. Case n = 4, k = 2, ℓ = 3. (For interpretation of the colors in the figure(s), the reader is referred to the web version of this article.)

Theorem 8 .

 8 Let denote a set of p-keys, and let (r, Poss r ) denote a p-relation over (R, S) with |S| = k + 1. Then (r, Poss r ) is Armstrong for if and only if for all i = 1, . . . , k, the relation r k+1-i is Armstrong for β i . That is, for all i = 1, . . .

  zr} and -1 β 3 = {zto, ro}, and • β 4 = {tr, zr, zt} and -1 β 4 = {to, zo, ro}.

  zr} and -1 β 3 = {zto, ro}, and • 4 = {tr, zr, zt} and -1 β 4 = {to, zo, ro}.

7 :Theorem 12 .

 712 return ; Finally, we state the correctness and an upper bound of the time complexity of Algorithm 4. Algorithm 4 computes a non-redundant cover of the set of p-keys that are satisfied by the given p-relation r in time O(m + n 2 ) where m := |R| 2 × |r k | 2 × |dis-ag(r k )| and n := X∈dis-ag(r k ) |X|.

Fig. 4

 4 Fig.4shows the GUI of our Possibilistic Armstrong Relation tool. It provides access for users to an implementation of Algorithm 3. The tool computes for an input set of p-keys on a p-relation schema, an Armstrong p-relation for .We briefly outline the steps, which are illustrated on our running example in Fig.4. In step 1 (top left of Fig.4), the user enters the column names of the p-relation schema, the index of the bottom c-degree, together with the column names of the c-degree of a new p-key. Pressing the 'insert' button shows in step 2 (top right of Fig.4) the p-relation schema together with all the p-keys that have been entered so far. Pressing the 'save' button in step 2, will invoke the execution of Algorithm 3, and produce several results.Result 3 (bottom right of Fig.4) shows the corresponding Armstrong p-relation for the input set of p-keys from step 2. Intermediate results of the computation are shown in the bottom left of Fig.4. These include the anti-keys (Result 1) and the agree sets (Result 2).The bottom right of Fig.5shows the GUI after executing Algorithm 3 on our running example. The output shows a p-relation that is Armstrong for the input, and has the same agree sets as our p-relation from Table1.

Fig. 4 .

 4 Fig. 4. Graphical user interface for visualization.

Fig. 5 .

 5 Fig. 5. Possibilistic key finder tool on csv file and direct input.

Fig. 6 .

 6 Fig. 6. Size of Armstrong p-relation, and time to compute it in exponential case.

Fig. 7 .

 7 Fig. 7. Size of Armstrong p-relation, and time to compute it in logarithmic case.

Fig. 8 .

 8 Fig. 8. Average size of p-Armstrong relation with growing number of attributes and fixed p-degree.

Fig. 9 .

 9 Fig. 9. Average size of p-Armstrong relation with growing p-degree and fixed number of attributes.

Fig. 10 .

 10 Fig. 10. Comparison of minimal disagree set computation times and hypergraph transversal time for various data sets.

Table 1 A

 1 possibilistic relation and its nested chain of possible worlds.

	Possibilistic relation
	Zone Time rfid Object p-Degree
	Z0 10am H0 Grizzly	α 1
	Z1 10am H1 Grizzly	α 1
	Z1 12pm H2 Grizzly	α 1
	Z3 1pm H2 Grizzly	α 1
	Z3 1pm H3 Grizzly	α 2
	Z3 3pm H3 Grizzly	α 3
	Z4 3pm H3 Grizzly	α 4

Table 2

 2 An informative Armstrong p-relation for the book p-relation.

	Title	Author	Pages	Publisher	Price	p-Degree
	Harry Potter and the Cursed Child	J. K. Rowling	352	Little Brown	19.19	α 1
	Harry Potter and the Philosopher's Stone	J. K. Rowling	256	Bloomsbury	37.32	α 1
	Harry Potter Box Set	J. K. Rowling	3422	Bloomsbury	76.04	α 2
	Mockingjay	Suzanne Collins	448	Scholastic	8.92	α 2
	Catching Fire	Suzanne Collins	448	Scholastic	8.92	α 3
	End of Watch	Stephen King	448	Scribner	24.65	α 3
	End of Watch	Stephen King	496	Pocket Books	9.2	α 5

  Since every two-tuple p-relation over (R, S) is a finite p-relation, the following is straightforward: if |= ϕ, then |= f ϕ, and if |= f ϕ, then |= 2 ϕ. It remains to establish the opposite directions. For that purpose, it suffices to show that if |= 2 ϕ, then |= ϕ. We show the contraposition: if |= ϕ does not hold, then |= 2 ϕ does also not hold.

Theorem 1. Let ∪ {ϕ} denote a set of p-keys over p-relation schema (R, S). Then the following statements are equivalent: 1. |= ϕ, 2. |= f ϕ, and 3. |= 2 ϕ. Proof.

  . A p-relation (r, Poss r ) over (R, S) is Armstrong for a p-key set if and only if for all p-keys ϕ over (R, S), (r, Poss r ) satisfies ϕ if and only if |= ϕ. Armstrong p-relations therefore have the beautiful property that the maximum c-degree β by which a p-key (K, β) is implied by can 'simply be read-off' as the marginal certainty C

r (K) of K in any Armstrong p-relation (r, Poss r ) for .

Example 11. Let denote the p-key set from Example 2: ({zone, time, rfid}, β 1 ), ({time, rfid}, β 2 ), ({zone, rfid}, β 3 ), and ({zone, time}, β 4 ). Then the p-relation r in Table

1

is Armstrong for . For example, the key {zone, time, object} has marginal certainty C r (zone, time, object) = β 4 , since the smallest possible world that violates this key is r 2 . Indeed, β = β 4 is the largest c-degree such that the p-key ({zone, time, object}, β) is implied by .

  Poss r ) is Armstrong for if and only if for all i = 1, . . . , k, for all K ⊆ R, |= (r,Poss r ) (K, β i ) iff |= (K, β i ). However, |= (r,Poss r ) (K, β i ) iff |= r k+1-i K, and |= (K, β i ) iff β i |= K. Therefore, (r, Poss Let denote the p-key set from Example 2: ({zone, time, rfid}, β 1 ), ({time, rfid}, β 2 ), ({zone, rfid}, β 3 ), and ({zone, time}, β 4 ). Let r denote the p-relation from Table1.

r ) is Armstrong for if and only if for all i = 1, . . . , k, r k+1-i is an Armstrong relation for β i . The second statement follows straight from the well-known result that a relation r is Armstrong for a set of keys if and only if -1 ⊆ ag(r) and for all K ∈ and all X ∈ ag(r), K X

[START_REF] Demetrovics | Extremal combinatorial problems of database models[END_REF]

. ✷

We illustrate Theorem 8 on our running example. Example 13.

Table 4

 4 Basic characteristics of data sets used in discovery experiments.

	Data set	Columns (#)	Rows (#)
	iris	5	150
	Abalone	9	4,177
	Breast-Cancer	11	699
	Adult	14	48842
	Letter	17	20000
	Hepatitis	20	155
	Horse	27	368
	fd-reduced-30	30	250000

Table 6

 6 Efficiency measures for various data sets.

	Dataset		k = 10			k = 15
			time [s]	p-keys (♯)	size	time [s]	p-keys (♯)	size
	Iris	RC	0.06	15.80	50.40	0.06	25.80	76.40
		NRC	4.98	6.40	17.80	7.94	8.00	20.60
	Breast-Cancer	RC	0.54	18.00	62.80	0.55	40.40	134.80
		NRC	4.08	8.80	30.00	6.35	16.80	56.60
	Abalone	RC	55.39	329.60	1289.40	53.39	483.20	1870.20
		NRC	8.38	115.00	448.00	11.87	134.60	512.80
	Adult	RC	1814.78	43.60	310.40	1805.73	72.40	470.40
		NRC	7.08	33.20	226.80	9.80	51.60	316.60
	Letter	RC	808.21	14.80	217.20	801.67	32.80	435.40
		NRC	6.48	7.00	92.80	4.02	21.00	246.80
	Hepatitis	RC	39.31	1472.40	7164.60	43.02	2194.00	10614.60
		NRC	112.27	883.40	4501.20	190.08	1072.20	5360.80
	Horse	RC	36334.03	12138.20	64089.00	126486.77	24683.00	137663.20
		NRC	8780.14	8629.40	46550.20	26126.39	12599.40	71332.00
	fd-reduced-30	RC	ML	ML	ML	ML	ML	ML
		NRC	ML	ML	ML	ML	ML	ML

http://www.half .ebay.com /books -bestsellers.

https://www.amazon .com /best -sellers -books -Amazon /zgbs /books.

https://www.bookdepository.com /bestsellers.

http://www.barnesandnoble .com /b /books /_ /N -1fZ29Z8q8.

http://www.easons .com /shop /c -bestselling -books.

http://webscraper.io/.

Acknowledgement

The authors would like to thank a reviewer whose comments led to a clearer positioning of the contributions of the research. In particular, the model of uncertainty is primarily intended for the application areas that have been identified, including database design. We remark that the model of uncertainty is only of limited use in the area of query processing, due to its limited expressiveness.

This research is partially supported by the Marsden Fund Council (grant no 3701176) from New Zealand Government funding.

constrained databases. Tools for the visualization of abstract sets of p-keys and for the discovery of p-keys from given p-relations were established. Together, these two tools can be used by data engineers to help acquire the possibilistic keys that are semantically meaningful for a given application domain. Visualization and discovery were implemented in prototype systems, and detailed experimental results with both systems rounded off our theoretical findings on the inherent exponential complexity of these problems.

There are different directions that warrant future research. While keys constitute the simplest yet most important class of constraints, classes such as foreign keys and functional dependencies deserve particular attention as well. In fact, possibilistic functional dependencies were introduced in [START_REF] Link | Possibilistic functional dependencies and their relationship to possibility theory[END_REF] and their main application to relational database schema design discussed in [START_REF] Link | Relational database schema design for uncertain data[END_REF]. The class of foreign keys or, more generally, inclusion dependencies is an interesting next target. Since these referential constraints are defined with respect to different relation schemata, different semantics can be defined. On the basis of our algorithms for computing Armstrong p-relations and discovering p-keys, it would be interesting to conduct empirical studies about the usefulness of our acquisition framework for the identification of semantically meaningful p-keys. Another interesting application is consistent query answering [START_REF] Koutris | Consistent query answering for primary keys[END_REF]. Here, a given data set may violate a given set of constraints. Instead of repairing the data set with some minimal effort, consistent query answering only returns those answers that are present in all repairs. The possibilistic framework is interesting because consistent query answers would be answers attributed with the minimum p-degree across all repairs. Possibilistic data cleaning has already been mentioned as another application area, and first results have been announced in [START_REF] Köhler | Qualitative cleaning for uncertain data[END_REF]. It would be interesting to investigate possibilistic variants of data dependencies, in particular keys, in other data models. For example, keys in SQL [START_REF] Köhler | Possible and certain keys for SQL[END_REF][START_REF] Köhler | Possible and certain SQL keys[END_REF][START_REF] Köhler | Discovering meaningful certain keys from incomplete and inconsistent relations[END_REF] or XML [START_REF] Hartmann | Efficient reasoning about a robust XML key fragment[END_REF].