Priority fuzzy database management system implementation based on extensions to the XQuery language

Abstract

In recent years, there has been an increased interest in processing fuzzy queries over XML data that is also possibly fuzzy. Attention has been paid to various extensions of XML query languages that introduce concepts of fuzzy theory. We propose an extension of the XQuery query language in an attempt to handle flexible queries that provide priority, threshold, and fuzzy expression as well as fuzzy linguistic labels allowing users great flexibility in customizing query constraints. We give a detailed description of an advanced query processing software system developed using GPFCSP (Generalized Prioritized Fuzzy Constraint Satisfaction Problem) as the theoretical background. The software, called FXI (Fuzzy XQuery Interpreter), was developed as a web application using Java, AngularJS, and eXist-db — an open source native XML database and it incorporates various advanced features such as fuzzy ordering operations and fuzzy compatibility calculations that includes priorities. The paper presents its design, the most important considerations related to implementation, as well as testing using realistic scenarios.

Keywords

Fuzzy XQuery XQuery Interpreter XQuery XML Database

1 Introduction

In real world applications, information is often inconsistent, imprecise, vague, uncertain and ambiguous and comes in the form of imprecise or incomplete values, e.g. fast cars, tall buildings, etc. Zadeh [1] introduced the fuzzy set theory, which provides techniques for modelling imprecise and vague data in many applications. The membership function of a fuzzy set represents the degree of truth between 0 and 1.

Standard XML and XQuery language do not offer the ability to handle such information. Fuzzy sets and fuzzy logic are theories that have found their place in many similar fields where the use and processing of inaccurate and incomplete information is required. Introducing fuzzy as an extension would result in XML containing insufficiently defined, even incorrect information.

The use of fuzzy logic in defining XML ambiguity has been a field addressed in many papers in the last decade. The aim of this paper is development such an XML extension that would unify good ideas in this area and give some improvements. The extension includes fuzziness in values in XML documents, as well as in a query language that allows searching over such XML documents using fuzzy queries. We expand XQuery fuzzy with constraints that include priorities and thresholds using GPFCSP (Generalized Prioritized Fuzzy Constraint Satisfaction Problem) as a main theoretical concept behind the implementation.

It is important to note that most papers focus on theoretical settings and syntax definitions, and only a small number of paper deals with the implementation and produces complete software system. In such situations, the authors are unable to accurately review and test capabilities and limitations of their theories. Moreover, the performance and complexity of the implementation of a seemingly good syntactic solutions does not always have to be satisfactory. In this paper we present a tested system that allows storing fuzzy information in an XML database and querying using priority fuzzy logic enhanced queries. The whole system is based entirely on open source technologies - Java programming language, XML database eXist and AngularJS technology. The system is itself open source, so we give a reference to the entire source code [2].

The main contributions of this work are:

An extension of the XQuery query, that allows users to define priority, threshold and fuzzy expressions in their queries.

Fuzziness in XML documents giving an option to users to predefine linguistic labels in order to use them in queries.

An algorithm that is used to calculate the global constraint satisfaction degree by using the Generalized Prioritized Fuzzy Constraint Satisfaction Problem (GPFCSP) concept [3], fuzzy compatibility, and fuzzy ordering operations.

The implementation of an interpreter (Fuzzy XQuery Interpreter — FXI) capable of executing prioritized fuzzy XQuery queries.

This paper is organized as follows. Related work is presented in the second section. The preliminaries of PFCSP, GPFCSP and fuzzy ordering are shown in the third section. The fourth section explains the representation of fuzzy data. The fifth sections provide details of the fuzzy XQuery extension and fuzzy XQuery query processing. The sixth section contains the performance evaluation of our application. Finally, a comparison to other approaches and concluding remarks are discussed in the seventh section.

2 Related work

This section briefly describes the literature related to attempts to incorporate fuzzy logic into XML technologies. It is observed that there are two research directions: representation of fuzzy data in XML documents and fuzzyification of XML querying languages.

2.1 Representation of fuzzy data in xml documents

There have been many different approaches to represent uncertainty using fuzzy sets in XML documents. We will briefly mention a few most important directions. Üstünkaya, Yazici, and George [4] proposed fuzzy-valued attributes used to represent imprecise or vague data, and “FuzzyPredicate” attributes related to the fuzzy values with “OR”, “XOR” and “AND”. This work was followed by various attempts to define fuzzy XML structures like [5] and [6]. Finally, a notable work by Yan, Ma, and Zhang [7] presented the fuzzy constructs Val and Dist. The fuzzy construct Val is used to specify the probability of an element in the fuzzy XML document that uses a pair with a probability attribute, while the fuzzy construct Dist is used to specify the type of distribution: disjunctive or conjunctive. In a recent paper, a modular method as the theoretical basis to construct the components model in the phased mission system with probabilistic common cause failures is proposed in [8].

2.2 Fuzziness in XML querying languages

In previous work, several approaches to fuzzification of XML query languages have been investigated. There are four main categories of these approaches - XQuery-based, XPath-based, algebra-based and twig-based.

XQuery-based approaches introduce fuzziness to XQuery query language. This direction has been the most popular one and it resulted in a number of papers. The most notable attempts in this direction have been reported in [4 , 9– 16].

Several approaches have pursued flexibility using fuzzy sets in XPath, the XML Path language. Some examples are [17 –20].

Ma, Liu, and Yan [21] proposed a formal fuzzy XML query algebra for expressing fuzzy XML queries by transforming the XQuery expressions into algebraic expressions. Moreover, they introduced the fuzzy XML algebraic operations to apply the algebra to XML query processing.

Yan et al. [7] proposed an XML query formed as a twig pattern with additionally imposed predicates on the contents or attribute values of the tree nodes. In a more recent research, Zongmin Ma et al. [22] introduced the keyword query on fuzzy XML data and described a query method AO-Twig to combine their structured query language with keyword query to obtain the results with the highest scores.

The main goal of our research was to implement a system that allows the use of priority fuzzy logic with XML databases. Using the GPFCSP concept [3], a method was found to introduce priority fuzzy queries into fuzzy XML databases, resulting in FXI. FXI is an interpreter for the XQuery query language enriched with priority fuzzy logic, as well as the ability to compare fuzzy values, querying over data in an XML database that may also contain fuzzy values. The language allows conditions in the query that are marked with different priorities. GPFCSP provides a theoretical background for implementing fuzzy priority queries. Our previous publication [23] introduced an idea of the fuzzy XQuery extensions related to GPFCSP theory for the first time. Afterwards, an overview of our approach was presented in [24]. This paper proposed particular characteristics of the interpreter and the execution process of a fuzzy XQuery implementation. Furthermore, we presented the illustrative example of the execution of fuzzy XQuery query in [25].

Our previous papers contain theoretical considerations and a prototype implementation of basic functionalities. In this paper we cover the final implementation containing stable implementation of all functionalities, including AngularJS based front-end and we test functionalities thoroughly using real-world data, both in performance and correctness. This paper presents the proof of concept and publishes the final source code [2]. The software has been developed as part of the research project “A Fuzzy XML Database System” (the final report can be found in [26]).

3 Theoretical background

In this section we will skip the details related to the classical theory of fuzzy sets. Instead, we focus on the fuzzification of constraint satisfaction problems (CSP) because it provides the basis for query fuzzification. We will show a strong parallel between conditions in a query and constraints in a CSP, allowing the use of theoretical concepts that we will introduce in our implementation. Particularly, we are interested in prioritized fuzzy constraint satisfaction problems allowing usage of both conjunction and disjunction.

3.1 PFCSP

The notion of Prioritized Fuzzy Constraint Satisfaction Problem (PFCSP) represents a generalization of the well-known concept of CSP (Constraint Satisfaction Problem). Constraints in a CSP are functions mapping the Cartesian product of the domains of variables to the {0, 1} set. However, in this case, we use the unit interval ([0, 1]) instead of the {0, 1} set, so the constraints are transformed to the membership functions of fuzzy sets and Fuzzy Constraint Satisfaction Problems (FCSP) are introduced. On top of that, Dubois et al. in [27] added priorities to constraints in Fuzzy Constraint Satisfaction Problems and defined an axiomatic framework in [28] to give the formal definition of the PFCSP concept. Takači [29] defined an alternative axiomatic framework for the PFCSP, similar to the one given in [28], but with a stricter notion of priority, that we use in this paper.

CSP systems, as described above, can be compared to the FLWOR querying expressions in XQuery — the XML query language. Let us observe an illustrative example of the XQuery query with FLWOR structure in listing 1.

Listing 1: An example of XQuery FLWOR expression.

for $x in document(student.xml)

where $x/tall >170 AND $x/age= 25

return $x

The variables after the “for” keyword can be interpreted as CSP variables, while expressions after the keyword “in” represent their domains. Similarly, “where” clause contains constraints to values of variables from “for”, connected using logical operators. We apply the same fuzzification process to XQuery queries as we did for CSPs and extend the FLWOR clause by allowing fuzzy variables and fuzzy constraints with priorities.

The PFCSP could be used as the mathematical background that defines how to calculate the fuzzy membership degrees of the result set tuples. But it has one limitation — it only allows the usage of conjunction between constraints. To calculate conjunction, or intersection of two or more fuzzy sets, we use triangular norms. The PFCSP introduces the notion of priority and describes it with certain constraints to align the mathematical definition with what we think under the term priority. It turned out that, in order to conserve this property, it was not possible to use any triangular norm. Paper [29] gives proof that Lukasiewicz t-norm, T_L, satisfies all constraints given by the PFCSP definition.

3.2 GPFCSP

Clearly, it is necessary to allow the use of negation and disjunction too, so the concept had to be generalized first. The PFCSP concept is generalized by allowing the possibilities to combine the t–norm used for conjunction with t–conorm and negation operators to connect the prioritized fuzzy constraints. The formal definition of generalized PFCSP is given in continuation. We give short explanations after the definition, but we point readers to cited references for further details.

Definition 3.1. When given ( X, D, C^f, ρ), where

X = { x_i| i = 1, 2, …, n} is a set of variables,

D = { d_i| i = 1, 2, …, n} is a finite set of domains. Each domain d_i is a finite set containing the possible values for the corresponding variable x_i in X,

C^f is a set of fuzzy constraints, that is, $\begin{matrix} C^{f} = {R_{i}^{f} | μ_{R_{i}^{f}} : d_{i 1} \times \dots \times d_{{ik}_{i}} \to [0, 1], \\ i = 1, \dots, m, 1 \leq k_{i} \leq n} \end{matrix}$

ρ : C^f → [0, ∞)

and a simultaneous valuation v_X ( x₁, …, x_n) , x_i ∈ d_i of all variables in X, shortly denoted v_X and an operator ⊕ : [0, 1] ⁿ → [0, 1], g : [0, ∞) × [0, 1] → [0, 1]. The generalized PFCSP is defined as a tuple ( X, D, C^f, ρ, g, ∧ , ∨ , ¬) which satisfies the following. An elementary formula in the GPFCSP is a pair ( x, ρ ( C_i)), where C_i ∈ C^f, x ∈ Dom ( C_i) represents the satisfaction degree of a constraint C_i and p_i = ρ ( C_i) represents its priority.

A formula in the GPFCSP is defined in the following way:

An elementary formula is a formula.

If f₁ and f₂ are formulas then also ∧ ( f₁, f₂) , ∨ ( f₁, f₂) and ¬ ( f₁) are formulas.

For each valuation v_X, a satisfaction degree α_F ( v_X) of a formula F is calculated depending on the interpretation of connectives.

A system is a GPFCSP if

Let F = ∧ _{i∈{1,…, n}} f_i be a formula in the GPFCSP where f_i, i ∈ {1, …, n} are elementary formulas and let C^f be a set of constrains that appear in the formula. If for the fuzzy constraint $R_{\max}^{f}$ we have $ρ_{\max} = ρ (R_{\max}^{f}) = max {ρ (R^{f}) ∣ R^{f} \in C^{f}},$ (1) then for each formula F we have: $μ_{R_{\max}^{f}} (v_{X}) = 0 \Rightarrow α_{F} (v_{X}) = 0 .$ (2)

If ∀ R^f ∈ C^f, ρ ( R^f) = ρ₀ ∈ [0, 1], then for each formula F the following holds: $α_{F} (v_{X}) = F_{L} (v_{X})$ (3) where $F_{L}$ is the interpretation of the logical formula F in fuzzy logic $L (\land, \lor, \neg)$ .

For $R_{i}^{f}, R_{j}^{f} \in C^{f}$ , assume $ρ (R_{i}^{f}) \geq ρ (R_{j}^{f}), δ > 0$ and assume that there are two different valuations v_X and $v_{X}^{'}$ such that:

if $\forall R^{f} \neq R_{i}^{f}$ and $\forall R^{f} \neq R_{j}^{f}$ , then $μ_{R^{f}} (v_{X}) = μ_{R^{f}} (v_{X}^{'})$ ,

if $R^{f} = R_{i}^{f}$ , then $μ_{R^{f}} (v_{X}) = μ_{R^{f}} (v_{X}^{'}) + δ$ ,

if $R^{f} = R_{j}^{f}$ , then $μ_{R^{f}} (v_{X}^{'}) = μ_{R^{f}} (v_{X}) + δ$ .

Then, for formulas:

F = ⋀_{k = 1}^{n} (x_{k}, ρ (R_{k})), x_{k} \in Dom (R_{k})

(4) and

F = ⋁_{k = 1}^{n} (x_{k}, ρ (R_{k})), x_{k} \in Dom (R_{k})

(5) the following holds:

α_{F} (v_{X}) \geq α_{F} (v_{X}^{'}) .

(6)

Assume that two different valuations v_X and $v_{X}^{'}$ such that ∀ R^f ∈ C^f satisfy $μ_{R^{f}} (v_{X}) \geq μ_{R^{f}} (v_{X}^{'}) .$ (7)

If formula F has no negation connective, then the following holds: $α_{F} (v_{X}) \geq α_{F} (v_{X}^{'}) .$ (8)

Let there be a valuation such that ∀ R^f ∈ C^f, μ_{R
^f} ( v_X) =1 .

If F is a formula $F = ⋀_{i = 1}^{n} f_{i}$ or $F = ⋁_{i = 1}^{n} f_{i}$ , where f_i, i ∈ {1, …, n} are elementary formulas then $α_{F} (v_{X}) = 1 .$ (9)

The function ρ represents the priority of each constraint. Greater value of ρ ( R^f) means that the constraint R^f has a larger priority. The function g aggregates the priority of each constraint with the value of that constraint. These aggregated values of each constraint are then aggregated by the operator ⊕, which results in the satisfaction degree of that valuation.

The first axiom states that a zero value of the local satisfaction degree of the constraint with the maximum priority implies a zero value of the local satisfaction degree. The second axiom states that, in the case of equal priorities, the GPFCSP becomes a GFCSP — without priorities. The third axiom captures the notion of priority. If one constraint has a larger priority then the increase of the value on that constraint should result in a bigger increase of the global satisfaction degree than when the value with the smaller priority has the same increase. The fourth axiom is the monotonicity property, and finally the fifth is the upper boundary condition. A more detailed explanation of the axioms given in this definition can be found in [29]. The following theorem is the most important result that we rely on in this paper as theoretical background.

Theorem 3.1. The following system: $(X, D, C^{f}, ρ, g, \land, \lor, \neg, ◊),$ where ∧ = T_L, ∨ = S_L, ¬ =1- x and finally ◊ ( x_i, c_i) = S_P ( x_i, 1- p_i) is a GPFCSP. The global satisfaction degree of a valuation v_X for a formula F is obtained in the following way: $α_{F} (v_{X}) = F {◊ (v_{x_{i}}, \frac{ρ (R^{f})}{ρ_{\max}}) | R^{f} \in C^{f}},$ (10) where C^f is the set of constraints of formula F, ρ_max = max { ρ ( R^f) , R^f ∈ C^f} and $F$ is the interpretation of formula F in the GPFCSP.

The theorem states that if we use T_L for conjunction, S_L for disjunction and the standard negation for negation — we preserve the properties of priorities and satisfy all axioms given in the definition. The proof can be found in [30]. It is a consequence of the similar theorem given in [29] for PFCSPs and the facts that 1- x is the standard negation, T_L is a t–norm and S_L is a t–conorm dual to the T_L.

This theorem is crucial for our implementation because it gives an example of a GPFCSP that is usable in fuzzification of XQuery FLWOR queries. It shows that if we use T_L to calculate conjunction of conditions and S_L to calculate discjunction, while we use S_P to aggregate priority to a constraint, our calculations will be consistent with GPFCSP axioms describing the notion of priority.

We illustrate the process of global satisfaction degree calculation in the following example.

3.3 GPFCSP usage example

Let us observe a set of students taking the faculty entrance examination. Our task is to rank them using three criteria – the high school GPA (Grade Point Average), the test score and their age. Let us construct the variables and their domains in the following way:

X₁ represents the high school GPA, d₁ = [2, 5] ,

X₂ represents the age, d₂ = [0, 130] ,

X₃ represents the test score, d₃ = [0, 60] .

Let us also define the following constraints:

$R_{1}^{f} =$ “excellent high school GPA”,

$R_{2}^{f} =$ “about 20 years old”,

$R_{3}^{f} =$ “good test results”.

The constraints are fuzzy subsets of the corresponding domains. Let us model the first constraint as a right–shoulder ascending from 4 to 5. The second constraint is modeled as a triangle fuzzy number that has a peak in 20, with the left offset of 1 and the right offset of 6. Finally, the third constraint is a right–shoulder that ascends from 40 to 60.

Let the criterion on how to pick a candidate (formula F) be: “student has to have an excellent high school GPA ( $R_{1}^{f}$ ) or has to be about 20 years of age ( $R_{2}^{f}$ ) and has to have good test results ( $R_{3}^{f}$ )”. In addition, we define the priorities like this: $ρ (R_{1}^{f}) = 0.4$ , $ρ (R_{2}^{f}) = 0.1$ and $ρ (R_{3}^{f}) = 0.6$ . The valuation v_X given inTable 1 defines three candidates.

Table 1
Valuation v_X

Name GPA Age Test

Robert 4.5 21 50

Nicholas 4.8 19 55

Jessica 4.7 20 52

Name	GPA	Age	Test
Robert	4.5	21	50
Nicholas	4.8	19	55
Jessica	4.7	20	52

First, we calculate the constraint satisfaction degree for every constraint and every student. These degrees are obtained directly as values of the corresponding membership functions in the given points. The results are given inTable 2.

Table 2

The constraint satisfaction degrees for every constraint and every student

Name	GPA	Age	Test
Robert	0.5	0.83	0.5
Nicholas	0.8	0	0.75
Jessica	0.7	1	0.6

Now we can calculate the global constraint satisfaction degree for every student in the following way:

$\begin{matrix} α = T_{L} (S_{L} (S_{P} (μ_{R_{1}^{f}} (v), 1 - ρ (R_{1}^{f})), \\ S_{P} (μ_{R_{2}^{f}} (v), 1 - ρ (R_{2}^{f}))), \\ S_{P} (μ_{R_{3}^{f}} (v), 1 - ρ (R_{3}^{f}))) . \end{matrix}$

If we use the values for the first student, we obtain the following:

$\begin{matrix} α = T_{L} (S_{L} (S_{P} (0.5, 0.6), S_{P} (0.83, 0.9)), \\ S_{P} (0.5, 0.4)) . \end{matrix}$

Finally, we obtain the satisfaction degree for the first student: $\begin{matrix} α = (T_{L} (S_{L} (0.8, 0.983), 0.7) = \\ T_{L} (1, 0.7) = 0.7 . \end{matrix}$

The global constraint satisfaction degrees for the other students are calculated in the same way and are given inTable 3. These results are a measure of how much the students satisfy our criteria. Obviously, Nicholas is the best candidate.

Table 3

The constraint satisfaction degrees for all students

Name	α
Robert	0.7
Nicholas	0.85
Jessica	0.76

To draw a parallel between the GPFCSP and XQuery FLWOR expressions, we will now map the GPFCSP system we considered to an FXI query. A priority fuzzy logic enhanced XQuery query given at Listing 2 represents a match for the GPFCSP that we considered. The three variables, $X_{i}^{f}$ , are matched on the left side of the conditions given in the where clause. On the right side, we see the representation of the three conditions $R_{i}^{f}$ together with their priorities $ρ (R_{i}^{f})$ .

Listing 2: A FLWOR XQuery query that matches the presented GPFCSP.

for $x in document(student.xml)

where ($x/GPA = #fs(0,4,5)#) priority 0.4

OR ($x/age = #tri(19,20,26)#) priority

0.1 AND ($x/age = #fs(0,40,60)#) priority

0.6

return $x

3.4 Fuzzy ordering

When the relational operators (<,< =,>,> =) are included in the query, it is necessary to provide a means to calculate comparison values between fuzzy sets. These fuzzy relational operators are typically used for comparing two fuzzy sets, but can also be used with some aggregate functions like MIN, MAX, and SUM. A well-known ordering for real interval is:

[a, b] \leq_{I} [c, d] \Leftrightarrow a \leq c & b \leq d

The inequality a ≤ c means that no element of the set [c, d] is below the interval [a, b], while the inequality b ≤ d means that no element of [a, b] is above [c, d]. Bodenhofer [31] has introduced an ordering as given below: The height of a fuzzy set A is defined as

height (A) = \sup {A (x) | x \in X}

Definition 2. Let A be a fuzzy set of the domain X, LTR(A) (standing for Left-to-Right closure) is the smallest fuzzy superset of A that has a non-decreasing membership function (seeFigure 1a) as defined by: $LTR (A) (x) = \sup {A (y) | y \in X & y \leq x}$

Definition 3. RTL(A) (standing for Right-to-Left closure) is the smallest fuzzy superset of A that has a non-increasing membership function (seeFigure 1b) as defined by: $RTL (A) (x) = \sup {A (y) | y \in X & x \leq y}$

Fig. 1

LTR(A) and RTL(A) [31].

Definition 4. The F(X) denotes the set of all fuzzy sets of X, a fuzzy ordering on fuzzy set A and B, if A, B ∈ F(X), is defined as follows:

$\begin{matrix} A \leq_{I} B \Leftrightarrow (LTR (A) \supseteq LTR (B) & \\ RTL (A) \subseteq RTL (B)) \end{matrix}$ (11)

Considering fuzzy orderings above, the fuzzy ordering calculation [32] can be determined by considering horizontal positions of compared fuzzy sets. If both conditions in Eq. (11) are fulfilled, the fuzzy ordering value is true or 1. Otherwise, the operation returns false or 0. If only one condition is satisfied, it means that the fuzzy sets cannot be compared — incomparable case, for which the fuzzy ordering operation will return “incomparable” or 0.5.

4 Representation of fuzzy data in an XML document

Our approach allows users to label fuzzy data representing imprecise data in an XML document by using linguistic labels. The linguistic labels (or linguistic terms) are natural language expressions (such as “young age” or “tall student”) with associated degrees of membership. The system supports four types of distributions of fuzzy numbers: triangular, trapezoidal, interval, and fuzzy shoulder (left shoulder and right shoulder). The XML Schema describing rules for definition of fuzzy variables and linguistic labels can be found in [26]. Here we give an example to illustrate the possibilities. Users can define the value of each element in an XML database as a fuzzy value (see Listing 3) of one of the four types of fuzzy numbers in the following way:

Triangle fuzzy number: tri(leftOffset, maxOffset, rightOffset)

Trapezoidal fuzzy number: trap(leftLowerOffset, leftUpperOffset, rightUpperOffset, rightLowerOffset)

Interval fuzzy number: interval(leftOffset, rightOffset)

Fuzzy shoulder: fs(type of fuzzy shoulder, lowerOffset, upperOffset)

Listing 3: An example of specifying fuzzy values in an XML document.

< ?xml version="1.0" ?>

< /student>

<gpa>interval(3,4)< /gpa>

< /student>

< /student>

< /student>

< /students>

5 Fuzzy XQuery Extensions

5.1 Fuzzy XQuery EBNF grammar

In our previous publication [25], we gave the EBNF notation and described every detail of fuzzy extensions that we introduced to XQuery. The standard XQuery’s WHERE-clause of the FLWOR (For-Let-Where-Order by-Return) statement is extended with the options of threshold, priority, and fuzzy Expressions.

To illustrate the features of the fuzzy XQuery, we give four query examples. The first query (Listing 4) retrieves the students who are taller than 180 cm and their age is about 20 years.

Listing 4: A fuzzy XQuery with fuzzy constants.

for $x in document(student.xml)

where $x/height>180 AND $x/age= #fs(0,20,30)#

return $x

The # symbol is chosen to mark fuzzy constants. If we defined a linguistic label “young” that has value fs(0,20,30), the previous query could be simplified (Listing 5)

Listing 5: A fuzzy XQuery with a linguistic label “young”.

for $x in document(student.xml)

where $x/height>180 AND $x/age= #ling(young)#

return $x

Queries can be enriched with additional constrains. The next query (Listing 6) contains the priority clause. The priority clause specifies the importance of the corresponding constraint to the overall result. If the value of the priority clause is higher, it means that the constraint has higher importance.

Listing 6: A fuzzy XQuery with the priority clauses.

for $x in document(student.xml)

where $x/height> #tri(170,180,190)# priority

0.4 AND $x/age= #ling(young)# priority

0.6

return $x

Moreover, the query can include the threshold clause that limits the results and removes tuples with the global constraint satisfaction degree smaller than the value of threshold clause. In this example (Listing 7), the result set does not include the tuples with the global constraint satisfaction degree smaller than 0.2.

Listing 7: A fuzzy XQuery with a threshlod clause.

for $x in document(student.xml)

where $x/height> #tri(170,180,190)# priority

0.4 AND $x/age= #ling(young)# priority

0.6

threshold 0.2

return $x

5.2 Fuzzy XQuery query processing

The complex task of processing a fuzzy XQuery includes two main considerations:

transformation of fuzzy XQuery described in [26], and

the algorithm that we use to calculate the global constraint satisfaction degree of every item in the result set using GPFCSP, fuzzy compatibility and fuzzy ordering operations — described the detail in [26]. For example, the process to execute the fuzzy XQuery in Listing 7 starts from comparing two fuzzy values with the fuzzy compatibility operation or the fuzzy ordering operation. In the first constraint (height > # tri(170,180,190)#), we need to compare “height” with the fuzzy number “tri(170,180,190)” by using the fuzzy ordering operation and height might be defined as fuzzy data (as in Listing 3). The second constraint (age =#ling(young)#) is used fuzzy compatibility operation because of the operator “=”. Afterwards, S_P is used to aggregate the priority value with each constraint. Lastly, the global constraint satisfaction degrees obtain from further aggregated AND operator with two constraints by using T_L.

Implementation of the FXI — fuzzy XQuery interpreter as web application has been done using only free and open-source software components. Java programming language was used as the middleware for main components and AngularJS as the front-end. We used an XML native database written in Java — eXist-db version 2.0, capable of executing XQuery queries, as back-end. An overview of the FXI architecture is presented inFig. 2. The client side is AngularJS-Bootstrap based web tier connecting to middle tier using RESTful web services. Middle tier includes the core of the system — implementation of query processing using Java and ANTLR [33] framework for parsing. The middle tier connects to the XML native database in the back-end using standard XML:DB API.

Fig. 2

Component diagram of FXI application.

6 Performance evaluation

The experiments were conducted to evaluate the accuracy and performance of the FXI system. Firstly, in order to prove the accuracy, the system was tested for all possible input cases to see if it will produce the correct outputs. Our tests include cases with two conditions of comparison expressions and two conjunction operators. The comparison expression consists of a variable expression, a relational operator, and a fuzzy expression. Variable expressions can take values of crisp number type or four types of fuzzy numbers: triangle, trapezoidal, interval and two kinds of fuzzy shoulders: left shoulder and right shoulder. Similarly, fuzzy expressions can be defined as values of four types of fuzzy numbers, with the possibility to use linguistic labels. Consequently, our test cases contained every possible combination of fuzzy number types. The relational operator is one of the four relational operators: =, !=, <, and >, which was varied among four cases for each condition. Furthermore, priority expressions and threshold expressions were added on top of those combinations. There were 22,400 test cases overall in our experiments and the test results were correct for every test case.

Secondly, the efficiency of FXI system was evaluated by measuring how the query execution time vary depending on the amount of fuzzy values in the query and data. The test data was created using student records from Prince of Songkla University — approximately 5,000 records as shown in Listing 8.

Listing 8: An example of the student data.

< ?xml version="1.0" ?>

<name>JIRAWAN< /name>

< /student>

< /students>

Execution times of a fuzzy XQuery with various fuzzy variables are shown inTable 4. The queries as in Listing 9 and Listing 10 were used to test one and two variables, respectively.Table 4 shows that the execution time increases with the increasing number of fuzzy variables, as expected.

Listing 9: The fuzzy XQuery with one fuzzy variable.

for $x in doc(/apps/FXIdb/studentdata.xml)

where $x/age=#trap(18,20,22,25)#

and $x/height>160

return $x

Listing 10: The fuzzy XQuery with two fuzzy variables.

for $x in doc(/apps/FXIdb/studentdata.xml)

where $x/age=#trap(18,20,22,25)#

and $x/height=#tri(100,150,200)#

return $x

Table 4
Fuzyy variable/Execution time

789 KB file size 1 variable 2 variables

Fuzzy XQuery 25 s 38 s

789 KB file size	1 variable	2 variables
Fuzzy XQuery	25 s	38 s

Table 5 displays time required to execute a query with regard to the size of fuzzy data in an XML document. We ran the query in Listing 10 randomizing fuzzy values only in the age field in three cases: 1000, 2500 and 4000 records, respectively. The result shows that the value type as a factor (crisp value or fuzzy values) does not make significant difference in the response times.

Table 5

Fuzyy data/Execution time

	crisp 5,000 records	crisp 4,000 records fuzzy data 1,000 records	crisp 2,500 records fuzzy data 2,500 records	crisp 1,000 records fuzzy data 4,000 records
Fuzzy XQuery	38 s	42 s	43 s	44 s

7 Discussion and conclusions

As presented in the related work section, the four main categories of implementing fuzziness in a query language are XQuery-based, XPath-based, algebra-based, and twig-based. As our approach is based on XQuery, this section will compare our approach only with others that are also XQuery-based in four aspects.

First, various ways to support fuzziness in XQuery are discussed. Several papers extend XQuery with the capability to declare linguistic labels, which are interpreted based on distributions of membership functions according to user’s preferences, including for example, [6 , 16] and this approach. However, our approach supports more types of membership functions than the prior approaches: triangle, trapezoidal, interval and fuzzy shoulder-left shoulder and right shoulder. In [4, 16], and this current approach, users can define threshold values in fuzzy XQuery. The threshold value is taken into account on post-processing query by using alpha-cut. In order to support fuzziness in XQuery, it is necessary to assign a satisfaction degree, which is a real number between 0 and 1, for the result tuples satisfying fuzzy conditions, as presented in [11, 16] and this work. Moreover, [16] and our work supported priority expressions specifying the importance of each fuzzy condition.

The second issue is the strategy for fuzzy query processing. Each implementation has used different mechanisms, as shown inTable 6. The most obvious method is to translate the fuzzy XQuery into a classical XQuery query. For example, [15] defined linguistic labels and used them in fuzzy XQuery instead of using Boolean conditions. The linguistic labels are referred to fuzzy membership functions. If the retrieved values in an XML data are in the fuzzy membership range, then the database will return these values in the output. That is, the results returned correspond to the fuzzy membership range. In [6] used the comparison translation rules to translate a fuzzy rule into a crisp rule. Thereafter, the outputs were retrieved from the translated query. The similarity matrix or similarity table was used in [4] to find results matching fuzzy-valued attributes. For instance, if the query is “Show all books, whose publisher is ‘McGraw-Hill’and the subject is ‘Mathematics’with threshold value 0.8”, firstly the system retrieves books that match the publisher criteria. Next, the books that satisfy the subject criteria are retrieved by using similarity table. In the similarity table, the books that have similarity (between ‘Mathematics’and the other domain values) greater than or equal to the threshold value in the query (in this example, the threshold value is 0.8) will be included in the result set. In [13] proposed a process to evaluate a fuzzy XQuery based on the Derivation Principle. Their approach derived a standard XQuery expression from the fuzzy XQuery by applying alpha-cut, meaning the system retrieved only the rows with satisfaction degree greater than or equal to the satisfaction threshold. Panić et al. [16] and our work apply the same GPFCSP theory to calculate the satisfaction degree with different calculation processing. Our approach translates a fuzzy XQuery in two steps. Firstly, the system transforms the fuzzy query to a standard XQuery. Next, the system gets the result set S of the standard XQuery from the database. Secondly, the system transforms the fuzzy query into the query Q that has only fuzzy conditions. Then the system calculates the satisfaction degree from query Q for all tuples of the result set S. This means that our implementation only computes the degrees for the result set S whereas Panić’s implementation computes the satisfaction degree of fuzzy conditions for the whole input data.

The third issue is the implementation. Currently, there are very few implementations of fuzzy XQuery, as shown inTable 6. However, it is noted that most implementations have used an open source programming language: Java with a choice of a native XML database, such as eXist-db, Oracle, and Tamino. Our implementation is the first web application. Our work used open source Java based on eXist-db. Moreover, the satisfaction degrees and the fuzzy ordering are calculated within the Java layer.

Table 6

Comparison table

Papers	Fuzziness in XQuery					theory	Implementation
	Fuzzy term	Priority	Threshold	Satisfaction degree	Ordering	DB	Programming language	Application base
Current	/	/	/	/	/	GPFCSP	eXist-db	JAVA	Web-based
approach
[16]	/	/	/	/	x	GPFCSP	MS SQL Server	.NET	Windows-based
[13]	/	x	/	/	x	Derivation Principle	eXist-db	JAVA	Client-Server
[15]	/	x	x	x	x	Fuzzy membership range	eXist-db	VB.NET	Unknown
[4]	x	x	/	x	x	Similarity matrix	Tamino	JAVA	Standalone application
[6]	/	x	x	x	x	Comparison Translation Rules	Oracle Berkeley DB XML	JAVA	Unknown

Our approach bears many similarities to Panić et al. [16] who also expanded XQuery syntax with fuzzy values and included priorities and thresholds in a fuzzy XQuery extension using the GPFCSP concept. There are, however, four main differences between Panić’s work and ours. First, the main algorithm was designed and implemented for calculating the global constraint satisfaction degrees by following the GPFCSP concept whereas Panić used the MATLAB module to do this. Second, Panić’s implementation used.NET Framework, MATLAB, and Microsoft SQL Server DBMS in a Windows application whereas our approach used Java to implement the new interpreter that was independent of MATLAB with eXist-db –a native XML database on a web application. Third, fuzzy ordering and fuzzy compatibility functions were developed for comparing values between two fuzzy sets while Panić did not. Lastly, the fuzzy data are represented (in an XML document) in completely different ways from Panić.

In summary, our research implemented fuzzy XQuery as an extension of standard XQuery, so it integrates priority, threshold, and fuzzy statements into regular queries. The algorithm for query processing used the GPFCSP concept to calculate the global constraint satisfaction degrees for each result set item. A major characteristic of this implementation is that it takes advantage of the Fuzzy XQuery Interpreter (FXI) programmed in Java language and has REST API as a back-end service and AngularJS as a front-end web application. Moreover, the accuracy and performance of FXI were evaluated by testing every possible type of input case.

Footnotes

Acknowledgments

This work is partially supported by the Ministry of Education and Science of the Republic of Serbia, through the project no. 174023: Intelligent techniques and their integration into the widespectrum decision support.

References

Zadeh

L.A.

,Fuzzy sets, Information and Control 8(3) (1965), 338–353.

Saeueng

, Skrbic

, Thadadech

and Kansomkeat

, Priority Fuzzy Database Management System Implementation Based on GPFCSP Extensions to the XQuery Language, 2018. doi: 10.5281/zenodo.1257218. https://doi.org/10.5281/zenodo.1257218.

Skrbic

, Rackovic

and Takaci

, Prioritized fuzzy logic based information processing in relational databases, Knowledge-Based Systems 38 (2013), 62–73, Special Issue on Advances in Fuzzy Knowledge Systems: Theory and Application, ISSN 0950-7051.

Üstünkaya

, Yazici

and George

, Fuzzy data representation and querying in XML database, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 15 (2007), 43–57.

Oliboni

and Pozzani

,Representing fuzzy information by using XML schema, in: Proceedings of the 19th International Conference on Database and Expert Systems Application, Turin, Italy, September, 683–687, 2008, pp. 1–5.

Jin

and Veerappan

A.S.

,fuzzy XML database system: Data storage and query processing, in: Proceedings of the 2010 IEEE International Conference on Information Reuse and Integration, Las Vegas, USA, August, 318–321, 2010, pp. 4–6.

Yan

, Ma

and Zhang

, Fuzzy XML data management, Springer, Heidelberg, 2014.

, Zhao

, Jiao

and Chen

, XML-based modeling method of phased-mission systems subject to probabilistic common cause failures, Journal of Intelligent and Fuzzy Systems (2018), 1–14. doi: 10.3233/JIFS-169865

, Kianmehr

, Kaya

, Özyer

and Alhajj

,Wrapping VRXQuery with self-adaptive fuzzy capabilities, in: Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence, Fremont, USA, 2007, pp. 2–5.

10.

Goncalves

and Tineo

, Un nuevo paso hacia XQuery flexible: A new step towards flexible XQuery, Revista Avances en Sistemas e Informática 4(3) (2007), 27–34.

11.

Goncalves

and Tineo

, Fuzzy XQuery, in: Soft computing in XML data management, L.Y. Z. Ma, Ed., Springer-Heidelberg, Berlin, 2010, pp. 133–163.

12.

Goncalves

and Tineo

, Derivation principle in advanced fuzzy queries, in: Handbook of Research on Innovative Database Query Processing Techniques, R. Krishnapuram and N. Pal, eds, 2005, pp. 579–584.

13.

Labbad

J.A.

, Monascal

R.R.

and Tineo

, Fuzzy XQuery A Real Implementation, in: Handbook of Research on Innovative Database Query Processing Techniques, L. Yan, ed., IGI Global, Hershey, PA, 2016, pp. 158–198.

14.

Fredrick

E.J.T.

and G.

A.G.

, Radhamani, based tool for generating XQuery and fuzzy XQuery, International Journal of Computer Applications 1(17) (2010), 1–5.

15.

Fredrick

E.J.T.

and Radhamani

, Information retrieval using XQuery processing techniques, International Journal of Database Management Systems 3(1) (2011), 50–58.

16.

Panić

, Racković

and Škrbić

, Fuzzy XML and prioritized fuzzy XQuery with implementation, Journal of Intelligent and Fuzzy Systems 26(1) (2014), 303–316.

17.

Amer-Yahia

, Lakshmanan

and Pandit

,FleXPath: Flexible structure and full-text querying for XML, in: Proceedings of the 2004 ACMSIGMOD International Conference onManagement of Data, Paris, France, June, 83–94, 2004, pp. 13–18.

18.

Campi

, Damiani

, Guinea

, Marrara

, Pasi

and Spoletini

A.P.

, fuzzy extension of the XPath query language, Journal of Intelligent Information Systems 33(3) (2009), 285–305.

19.

Campi

, Guinea

and Spoletini

,An operational semantics for XML fuzzy queries, in: Proceedings of the International Conference on Fuzzy Computation Theory and Applications, A. Dourado, J.M. Cadenas and J. Filipe, eds,Rome, Italy, October, 205–210, 2014, pp. 22–24.

20.

Almendros-Jiménez

J.M.

, Tedesqui

A.L.

and Moreno

, Fuzzy XPath through fuzzy logic programming, New Generation Computing 33(2) (2015), 173–209.

21.

Z.M.

, Liu

and Yan

, Fuzzy data modeling and algebraic operations in XML, International Journal of Intelligent Systems 25(9) (2010), 925–947.

22.

and Ma

, A structure-based approach of keyword querying for fuzzy XML data, International Journal of Knowledgebased and Intelligent Engineering Systems 22(2) (2018), 125–140. doi: 10.3233/KES-180379. https://doi.org/10.3233/KES-180379.

23.

Skrbic

, Wettayaprasit

and Saeueng

, A Priority Fuzzy Logic Extension of the XQuery Language, in: Proceedings of the International Conference on Numerical Analysis and Applied Mathematics, Vol. 1389, T.E. Simos, G. Psihoyios, C. Tsitouras and Z. Anastassi, eds, 2011, pp. 821–824.

24.

Ueng

P.S.

and Skrbic

,Fuzzy extensions using a native XML database, in: Proceedings of the 13th IEEE International Symposium on Computational Intelligence and Informatics, Budapest, Hungary, November, 305–309, 2012, pp. 20–22.

25.

Sae Ueng

, Škrbić

, Kansomkeat

and Thadadech

, A GPFCSP-Based Fuzzy XQuery Interpreter, Journal of Telecommunication, Electronic and Computer Engineering 9(2– 2) (2017), 35–40.

26.

Thadadech

, Vonghirandecha

, Kansomkeat

and Skrbić

, A Fuzzy XML Database System, Final report of collaborative research, Prince of Songkla University, Thailand, 2014.

27.

Dubois

, Helene

and Prade

, Possibility theory in constraint satisfaction problems: Handling priority, preference and uncertainty, Appliend Intelligenc 6(4) (1996), 287–309.

28.

Luo

, Lee

J.H.

, Leung

and Jennings

N.R.

, Prioritised fuzzy constraint satisfaction problems: Axioms, instantiation and validation, Fuzzy Sets and Systems 136(2) (2003), 151–188.

29.

Takaci

,Schur-concave triangular norms: Characterization and application in PFCSP, Fuzzy Sets and Systems 155(1) (2005), 50–64.

30.

Takaci

, Skrbic

and Perovic

,Generalised prioritised constraint satisfaction problem, in: Proceedings of 7th International Symposium on Intelligent Systems and Informatics, Subotica Serbia, 2009, pp. 145–148.

31.

Bodenhofer

,Orderings of fuzzy sets based on fuzzy orderings part I: The basic approach, Mathware and Soft Computing 15 (2008), 201–218.

32.

Ueng

P.S.

, Skrbic

, Kansomkeat

, Sukpisit

and Thadadech

,Fuzzy ordering implementation applied in fuzzy XQuery, in: Proceedings of the 5th International Conference on Information Society and Technology (ICIST 2015), Kopaonik, Serbia, March 8-112015, pp. 477–482.

33.

Parr

, ANTLR v3, 2018,http://www.antlr3.org.

34.

Z.M.

and Yan

, Modeling fuzzy data with XML: A survey, Fuzzy Sets and Systems 301 (2016), 146–159.

Priority fuzzy database management system implementation based on extensions to the XQuery language

Abstract

Keywords

1 Introduction

2 Related work

2.1 Representation of fuzzy data in xml documents

2.2 Fuzziness in XML querying languages

3 Theoretical background

3.1 PFCSP

3.2 GPFCSP

Table 1 Valuation v X Name GPA Age Test Robert 4.5 21 50 Nicholas 4.8 19 55 Jessica 4.7 20 52

5 Fuzzy XQuery Extensions

5.1 Fuzzy XQuery EBNF grammar

5.2 Fuzzy XQuery query processing

Table 4 Fuzyy variable/Execution time 789 KB file size 1 variable 2 variables Fuzzy XQuery 25 s 38 s

Footnotes

Acknowledgments

References

Table 1
Valuation v_X

Name GPA Age Test

Robert 4.5 21 50

Nicholas 4.8 19 55

Jessica 4.7 20 52

Table 4
Fuzyy variable/Execution time

789 KB file size 1 variable 2 variables

Fuzzy XQuery 25 s 38 s