Wyniki wyszukiwania - BazTech

1

Universal (and Existential) Nulls

Grahne Gösta, Moallemi Ali

Fundamenta Informaticae

|

2019

|

Vol. 167, nr 4

287--321

EN

Incomplete Information research is quite mature when it comes to so called existential nulls, where an existential null is a value stored in the database, representing an unknown object. For some reason universal nulls, that is, values representing all possible objects, have received almost no attention. We remedy the situation in this paper, by showing that a suitable finite representation mechanism, called Star Cylinders, handling universal nulls can be developed based on the Cylindric Set Algebra of Henkin, Monk and Tarski. We provide a finitary version of the cylindric set algebra, called Cylindric Star Algebra, and show that our star-cylinders are closed under this algebra. Moreover, we show that any First Order Relational Calculus query over databases containing universal nulls can be translated into an equivalent expression in our cylindric star-algebra, and vice versa. All cylindric star-algebra expressions can be evaluated in time polynomial in the size of the database. The representation mechanism is then extended to Naive Star Cylinders, which are star-cylinders allowing existential nulls in addition to universal nulls. For positive queries (with universal quantification), the well known naive evaluation technique can still be applied on the existential nulls, thereby allowing polynomial time evaluation of certain answers on databases containing both universal and existential nulls. If precise answers are required, certain answer evaluation with universal and existential nulls remains in coNP. Note that the problem is coNP-hard, already for positive existential queries and databases with only existential nulls. If inequalities ¬(xi ≈ x j) are allowed, reasoning over existential databases is known to be ∏2p -complete, and it remains in ∏ 2pwhen universal nulls and full first order queries are allowed.

2

Fuzzy recursive relationships in relational databases

Myszkorowski K.

Information Systems in Management

|

2018

|

Vol. 7, No. 1

35--46

EN

Recursive relationships are used for modelling problems coming from the real life, such as, for example, a relationship describing formal dependencies between employees of an enterprise, where creation of work groups and teams requires analysis of many elements. In conventional database systems, the precision of data is assumed. If our knowledge of the fragment of reality to be modelled is imperfect one should apply tools for describing uncertain or imprecise information. One of them is the fuzzy set theory. The paper deals with recursive relationships in fuzzy databases. The analysis is performed with the use of the theory of interval-valued fuzzy sets. A definition of a fuzzy interval recursive relationship has been presented. The paper defines different connections of entities which participate in such relationships. Operations of the extended relational algebra are also discussed.

3

Fuzzy querying with the use of interval-valued fuzzy sets

Myszkorowski K., Superson I.

Journal of Applied Computer Science

|

2013

|

Vol. 21, nr 1

89--105

EN

The paper deals with flexible queries in relational databases. Conditions included in queries are modeled with the use of interval-valued fuzzy sets. Each value returned by a query is associated with a subinterval of [0,1] which expresses a membership degree. The bounds of membership intervals have been determined for different operations of relational algebra and different SQL operators.

4

A new efficient and flexible algorithm for the design of testable subsystems

Ploix S., Yassine A. A., Flaus J.-M.

International Journal of Applied Mathematics and Computer Science

|

2010

|

Vol. 20, no 1

175-190

EN

In complex industrial plants, there are usually many sensors and the modeling of plants leads to lots of mathematical relations. This paper presents a general method for finding all the possible testable subsystems, i.e., sets of relations that can lead to various types of detection tests. This method, which is based on structural analysis, provides the constraints that have to be used for the design of each detection test and manages situations where constraints contain non-deductible variables and where some constraints cannot be gathered in the same test. Thanks to these results, it becomes possible to select the most interesting testable subsystems regarding detectability and diagnosability criteria. Application examples dealing with a road network, a digital counter and an electronic circuit are presented.

5

Foundations of Modal Deductive Databases

Nguyen L.A. L.A.

Fundamenta Informaticae

|

2007

|

Vol. 79, nr 1-2

85-135

EN

We give formulations for modal deductive databases and present a modal query language called MDatalog. We define modal relational algebras and give the seminaive evaluation algorithm, the top-down evaluation algorithm, and the magic-set transformation for MDatalog queries. The results of this paper like soundness and completeness of the top-down evaluation algorithm or correctness of the magic-set transformation are proved for the multimodal logics of belief KDI4s5, KDI45, KD4s5s, KD45(m), KD4Ig5a, and the class of serial context-free grammar logics. We also show that MDatalog has PTIME data complexity in the logics KDI4s5, KDI45, KD4s5s, and KD45(m).

6

Exact Computation of Minimum Feedback Vertex Sets with Relational Algebra

Berghammer R., Fronk A.

Fundamenta Informaticae

|

2006

|

Vol. 70, nr 4

301-316

EN

A feedback vertex set of a graph is a subset of vertices containing at least one vertex from every cycle of the graph. Given a directed graph by its adjacency relation, we develop a relational algorithm for computing a feedback vertex set of minimum size. In combination with a BDD-implementation of relations, it allows to exactly solve this NP-hard problem for medium-sized graphs.

7

A New Rough Sets Model Based on Database Systems

Hu X., Lin T.Y., Han J.

Fundamenta Informaticae

|

2004

|

Vol. 59, nr 2,3

135--152

EN

Rough sets theory was proposed by Pawlak in the early 1980?s and has been applied successfully in a lot of domains. One of the major limitations of the traditional rough sets model in the real applications is the inefficiency in the computation of core and reduct, because all the intensive computational operations are performed in flat files. In order to improve the efficiency of computing core attributes and reducts, many novel approaches have been developed, some of which attempt to integrate database technologies. In this paper, we propose a new rough sets model and redefine the core attributes and reducts based on relational algebra to take advantages of the very efficient set-oriented database operations. With this new model and our new definitions, we present two new algorithms to calculate core attributes and reducts for feature selections. Since relational algebra operations have been efficiently implemented in most widely-used database systems, the algorithms presented in this paper can be extensively applied to these database systems and adapted to a wide range of real-life applications with very large data sets. Compared with the traditional rough set models, our model is very efficient and scalable.

8

An extended Relational Algebra on Abstract Objects for summarizing answers to queries

Demolombe R.

Fundamenta Informaticae

|

2003

|

Vol. 57, nr 1

1--15

EN

Answers to queries in terms of abstract objects are defined in the logical framework of first order predicate calculus. A partial algebraic characterisation of the supremum and of the infimum of abstract answers is given in an extended Relational Algebra of the Cylindric Algebra kind. Then, the form of queries is restricted in order to be able to compute answers without the cylindrification operator. For these restricted queries we give a technique to compute an upper bound and a lower bound of abstract answers using only the operators of the standard Relational Algebra.