Browse Prior Art Database

THE NON-AXIOMATIZABILITY OP DEPENDENCIES IN DIRECTED ACYCLIC GRAPHS

IP.com Disclosure Number: IPCOM000128351D
Original Publication Date: 1987-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 17 page(s) / 44K

Publishing Venue

Software Patent Institute

Related People

Dan Geiger: AUTHOR [+3]

Abstract

Recently, few models were proposed to capture the notion of relevance. Their main component consists of a mechanism to assign truth values to a 3-place relation I(x,z,y) where x,y,z are three non-intersecting sets of elements (e.g attributes or variables), and I(x,z,y) stands for the statement: "Knowing z renders x irrelevant to y." Among these models one can find the Probabilistic dependency model ([ 1 ]), the Undirected Graph ( Pearl & Paz [2]), Directed Acyclic Graph ( Pearl & Venna [3]) and Hybrid Acy-clic Graph ( Verma [4]). An important tool in investigating these models and their expressive power is a complete set of axioms. Such a set was found so far only for the Undirected Graph ( UG) model. In this paper, we show that there is no finite complete set of Hom axioms for the Directed Acyclic Graph ( DAG) models. Moreover, we compare our result to a similar result in the Embedded Mufti Valued Dependency (EMVD) model of relational databases established by Parker and Parsaye in 1980 ([5]), and independent-ly by Sagiv and Walecka in 1982 ([6]). We point out that a stronger version of their incompleteness theorem can be stated for EMVDs. However, a similar extension for DAGs has not been fully established so far.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 11% of the total text.

Page 1 of 17

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

THE NON-AXIOMATIZABILITY OP DEPENDENCIES IN DIRECTED ACYCLIC GRAPHS

Dan Geiger September 1987 CSD-870048

THE NON-AXIOMATI2ABILITY OF DEPENDENCIES IN DIRECTED ACYCLIC GRAPHS by Dan Geiger

1. ABSTRACT

Recently, few models were proposed to capture the notion of relevance. Their main component consists of a mechanism to assign truth values to a 3-place relation I(x,z,y) where x,y,z are three non-intersecting sets of elements (e.g attributes or variables), and I(x,z,y) stands for the statement: "Knowing z renders x irrelevant to y." Among these models one can find the Probabilistic dependency model ([ 1 ]), the Undirected Graph ( Pearl & Paz [2]), Directed Acyclic Graph ( Pearl & Venna [3]) and Hybrid Acy-clic Graph ( Verma [4]). An important tool in investigating these models and their expressive power is a complete set of axioms. Such a set was found so far only for the Undirected Graph ( UG) model. In this paper, we show that there is no finite complete set of Hom axioms for the Directed Acyclic Graph ( DAG) models. Moreover, we compare our result to a similar result in the Embedded Mufti Valued Dependency (EMVD) model of relational databases established by Parker and Parsaye in 1980 ([5]), and independent-ly by Sagiv and Walecka in 1982 ([6]). We point out that a stronger version of their incompleteness theorem can be stated for EMVDs. However, a similar extension for DAGs has not been fully established so far.

The paper is organized as follows. Section 2 reviews some previous work and the necessary ter-minology concerning dependency theory and the DAG model in particular. Section 3 presents the con-struction which shows that there is no finite complete set of Horn axioms for DAGs. Section 4 discusses extensions to the incompleteness theorem. Finally, section 5 summarizes the results and outlines the rela-tion between dependency models and relational database theory.

2. DEPENDENCY MODELS

To understand the need of dependency models it is most adequate to quote Pearl and Paz as fol-lows: "Any system that reasons about knowledge and beliefs must make use of information about relevancies. If we have acquired a body of knowledge z and now wish to asses the truth of proposition x, it is important to know whether it would be worthwhile to consult another proposition y, which is not in z. In other words before we consult y we need to know if its truth value can potentially generate new in-formation relative to x, information not available from z. In probability theory, the notion of relevance is given precise quantitative underpinning using the device of conditional independencies a variable x is said to be independent of y given the information z if

(Equation Omitted)

UCLA Page 1 Dec 31, 1987

Page 2 of 17

THE NON-AXIOMATIZABILITY OP DEPENDENCIES IN DIRECTED ACYCLIC GRAPHS

However, it is rather unreasonable to expect people or machines to resort to numerical verification of e...