##
Bilgisayar programlamada sorgulama optimizasyonu teknikleri

Bilgisayar programlamada sorgulama optimizasyonu teknikleri

##### Dosyalar

##### Tarih

1992

##### Yazarlar

Kaptanoğlu, Çiğdem

##### Süreli Yayın başlığı

##### Süreli Yayın ISSN

##### Cilt Başlığı

##### Yayınevi

Fen Bilimleri Enstitüsü

##### Özet

Veri tabanı sisteminde sorgulama optimizasyonunu öncelikle herhangi bir verinin birden fazla kullanıcı tarafından doğrulukla kullanılabilmesi ve kısa süre içerisinde ulaşılabilmesi için incelenebilmesini gerektirir. Bunun üzerine verdiğimiz birinci örnek değişik yollar ile aynı dataya kaç erişim işlemi ile varılabileceğine dair bir örnektir.Daha sonra aşağıdan yukarıya erişim şeklinin daha kolay olduğunu, ilişkisel sorgulama ile bir sorgulama sisteminin nasıl temsil edilebileceğini tablolamanın bizim sorgulama sistemini görmemizde saglıyacağı kolaylıkları ve sorgulama sisteminin anlaşılabilirliğinin basitleştirme »iyileştirme yöntemi ile nasıl daha kolay anlaşılır hale getirilebileceğini inceledik. Bundan sonra değişik sorgulama sistemlerin erişim planlarını ve erişim planı stratejilerini gördük. İkinci ve üçüncü bölümde ise veri tabanı sistemlerinin mantık yoluyla incelenmesinin bize getirdiği avantajları anlattık. Bunu yaparken mode 1 1 eme ve çeviri yöntemlerini kullandık ve mantıksal dönüşüm yollarından çeşitli olanlarını verdiğimiz örneklerle ifade ettik. Sonuç veritabanlarını matematiksel mantık aracılığı ile inceledik. Sorgulama dillerine mantığın nasıl uygulanabileceğini, ve yeterli bilgi olmadan sorgulama sisteminin nasıl kurulabileceğini görmüş olduk. Fakat veri tabanı sistemlerinin matık aracılığı ile çözümü sona ermiş olmaktan çok uzaktadır. Halen incelenecek ve bulunacak birçok şey vardır. Ve bu problemlerin çözülebilmesi de uzun yıllar yapılması gereken çalışmaları gerektireceğe benzer.

Database management systems (DBMS) have become a standart tool for the computer users. They are designed to improve the productivity of data access. There have been two major areas of research in database systems. One is the analysis of data models which include the hierarchical, the network, the relational models, and the other is number of semantics-oriented models. A second area of interest is the safe and good implementation of the DBMS. Computerized data have become an important resource for many organizations. Therefore each implemantation of DBMS such as data access, recovery and reorganization should be done correctly. One major criticism of DBMS has been their lack of efficiency in handling the powerful operations. Query optimization tries to solve this problem by applying logical transformation rules to queries. Generally, different languages has been used for representing queries. This is the reason why we couldn't find a comprehesive representation for queries. Our purpose in this paper is finding a good solution for query optimization problem by using relational calculus. Relational calculus method is actually equivalent to relational algebra techniques and extendable to the network DBMSs. vi i We consider the centralized DBMS throughout this research. Centralized DBMS is not only important in many databases hut also appears in distributed systems. Also in this research we are not interested in user optimization and file structures. The first unit is organized into six sections. In section 1 we present a general rules for query optimization. In section 2 we compare queries in terms of their suitability for optimization. In section 3 we present relational calculus for query optimization. After transforming the queries by using relational calculus, in section 4 we consider such operations for low-level system of stored data. In section 5 we carry all these operations to the globally optimal access plan. Finally in section 6 we will show higher level queries, distributed queries and queries using database machines. After going through all these techniques we will finish an overwiev of logical transformation techniques and pyhsical evaluation methods for database queries by using relational calculus. Our purpose in subfield of logic as it is mostly concerned with relational type databases. the second unit is to study a applied to databases. We are the application of logic to This unit is concerned mainly a small set of facts and requires a mechanism provided by logic. Similar techniques have been adapted to databases to solve large sets of facts, negative information, open queries and other specific database topics. These techniques also have given a solution to deductive databases. van Aside from the introduction and conclusion to this unit, there are two main sections, which are devoted respectively to conventional databases and deductive databases. In the introduction, we will give information about terminology which will be used throughout this paper. After this we will be looking at concepts in relational databases, the area of mathematical logic and the basic relationships between logic and databases. Section 1 is an extended and revised version of material which shows how logic provides a formalism for databases, and how this formalism has been applied to conventional databases. In section 2 we show how logic extends relational databases to permit deduction and describe how logic provides a sound basis for a proper treatment and understanding of null values and incomplete information. In the remainder of this introduction, we first describe the main concepts of the relational data model. Following this, we specify what is meant by mathematical logic, focusing on logic relevant to databases rather than logic in general. We briefly introduce two ways in which databases can be considered from the viewpoint of logic. We need some concepts to define a relational model. These definitions will be about what is meant by domain, relation, attributes and integrity constraints. We also see that a database scheme consists of a collection of relation schemes together with a set of integrity constraints. It is also possible to use algebric language to define any database system. We use* the project and join operators for this reason. IX Mathematical logic relies upon an object language, a semantics or interpretation of formulas in that language, and a proof theory. In semantics we are concerned with interpretations, where an interpretation of a set of well formed formulas consists of the spesif ication of a nonempty set (or domain) E, from which constants and variables are given values. Each n-ary function symbol is assigned a function from E"n toE. Each n-ary predicate is assigned a relation on E'n. In interpretation, if two given clauses are satisfiable, the derived clause is satisfable too. Considering the formalization of in terms of logic, we shall mention some that govern query evaluation of databases. databases assumptions (1) The closed world assumption also called for negative information, which states that known to be true are assumed to be false. convention facts not (2) The unique name assumption, which states that individuals with different names are different. (3) The domain closure assumption, which states that there are no other individuals than those in the databases. We will use the term "mode 1-theori tic view" instead of the terms "interpretation", "model" and relational structure". A model is an interpretation that makes all axioms true. The "relational structure" view means that queries are evaluated by assuming the database entries to be true. All these terms relate to the semantis definition of truth. We are mainly concerned deductive databases in the second unit. A deductive database is a database in which new facts may be derived from facts that were explicitly introduced. We provide the background for defining deductive databases, and then treat two different kinds of deductive databases: definite and indefinite. A definite deductive databases is defined as a particular first-order theory. This theory is obtained from the theory given for conventional databases by the addition of a new class of axioms, which stand for the deductive laws, and by a reformulation of the completion axioms, which account for the presence of these new axioms. More precisely, a definite deductive database consists of the following rules: (1) The domain closure axioms, the unique name axioms, the equality axioms and the completion axioms. (2) A set of ground atomic formulas defined by clauses. (3) A set of function-free definite clauses. An indefinite deductive database differs from a definite deductive database in Axiom 3. The difference in Axiom 3, although seemingly minor, will be seen to be substantial. In conclusion we will be attempting to cover results obtained within the framework of mathematical logic applied to databases mainly through the perspective of deductive databases. We will show how logic applies to query languages, integrity modeling and maintenance, query evaluation, database design through dependencies, representation and manipulation of deduced facts, and incomplete information. However, the field of logic and databases, as it is called, is far from closed; logic provides an appropriate framework for many database problems that still need to be investigated thoroughly.

Database management systems (DBMS) have become a standart tool for the computer users. They are designed to improve the productivity of data access. There have been two major areas of research in database systems. One is the analysis of data models which include the hierarchical, the network, the relational models, and the other is number of semantics-oriented models. A second area of interest is the safe and good implementation of the DBMS. Computerized data have become an important resource for many organizations. Therefore each implemantation of DBMS such as data access, recovery and reorganization should be done correctly. One major criticism of DBMS has been their lack of efficiency in handling the powerful operations. Query optimization tries to solve this problem by applying logical transformation rules to queries. Generally, different languages has been used for representing queries. This is the reason why we couldn't find a comprehesive representation for queries. Our purpose in this paper is finding a good solution for query optimization problem by using relational calculus. Relational calculus method is actually equivalent to relational algebra techniques and extendable to the network DBMSs. vi i We consider the centralized DBMS throughout this research. Centralized DBMS is not only important in many databases hut also appears in distributed systems. Also in this research we are not interested in user optimization and file structures. The first unit is organized into six sections. In section 1 we present a general rules for query optimization. In section 2 we compare queries in terms of their suitability for optimization. In section 3 we present relational calculus for query optimization. After transforming the queries by using relational calculus, in section 4 we consider such operations for low-level system of stored data. In section 5 we carry all these operations to the globally optimal access plan. Finally in section 6 we will show higher level queries, distributed queries and queries using database machines. After going through all these techniques we will finish an overwiev of logical transformation techniques and pyhsical evaluation methods for database queries by using relational calculus. Our purpose in subfield of logic as it is mostly concerned with relational type databases. the second unit is to study a applied to databases. We are the application of logic to This unit is concerned mainly a small set of facts and requires a mechanism provided by logic. Similar techniques have been adapted to databases to solve large sets of facts, negative information, open queries and other specific database topics. These techniques also have given a solution to deductive databases. van Aside from the introduction and conclusion to this unit, there are two main sections, which are devoted respectively to conventional databases and deductive databases. In the introduction, we will give information about terminology which will be used throughout this paper. After this we will be looking at concepts in relational databases, the area of mathematical logic and the basic relationships between logic and databases. Section 1 is an extended and revised version of material which shows how logic provides a formalism for databases, and how this formalism has been applied to conventional databases. In section 2 we show how logic extends relational databases to permit deduction and describe how logic provides a sound basis for a proper treatment and understanding of null values and incomplete information. In the remainder of this introduction, we first describe the main concepts of the relational data model. Following this, we specify what is meant by mathematical logic, focusing on logic relevant to databases rather than logic in general. We briefly introduce two ways in which databases can be considered from the viewpoint of logic. We need some concepts to define a relational model. These definitions will be about what is meant by domain, relation, attributes and integrity constraints. We also see that a database scheme consists of a collection of relation schemes together with a set of integrity constraints. It is also possible to use algebric language to define any database system. We use* the project and join operators for this reason. IX Mathematical logic relies upon an object language, a semantics or interpretation of formulas in that language, and a proof theory. In semantics we are concerned with interpretations, where an interpretation of a set of well formed formulas consists of the spesif ication of a nonempty set (or domain) E, from which constants and variables are given values. Each n-ary function symbol is assigned a function from E"n toE. Each n-ary predicate is assigned a relation on E'n. In interpretation, if two given clauses are satisfiable, the derived clause is satisfable too. Considering the formalization of in terms of logic, we shall mention some that govern query evaluation of databases. databases assumptions (1) The closed world assumption also called for negative information, which states that known to be true are assumed to be false. convention facts not (2) The unique name assumption, which states that individuals with different names are different. (3) The domain closure assumption, which states that there are no other individuals than those in the databases. We will use the term "mode 1-theori tic view" instead of the terms "interpretation", "model" and relational structure". A model is an interpretation that makes all axioms true. The "relational structure" view means that queries are evaluated by assuming the database entries to be true. All these terms relate to the semantis definition of truth. We are mainly concerned deductive databases in the second unit. A deductive database is a database in which new facts may be derived from facts that were explicitly introduced. We provide the background for defining deductive databases, and then treat two different kinds of deductive databases: definite and indefinite. A definite deductive databases is defined as a particular first-order theory. This theory is obtained from the theory given for conventional databases by the addition of a new class of axioms, which stand for the deductive laws, and by a reformulation of the completion axioms, which account for the presence of these new axioms. More precisely, a definite deductive database consists of the following rules: (1) The domain closure axioms, the unique name axioms, the equality axioms and the completion axioms. (2) A set of ground atomic formulas defined by clauses. (3) A set of function-free definite clauses. An indefinite deductive database differs from a definite deductive database in Axiom 3. The difference in Axiom 3, although seemingly minor, will be seen to be substantial. In conclusion we will be attempting to cover results obtained within the framework of mathematical logic applied to databases mainly through the perspective of deductive databases. We will show how logic applies to query languages, integrity modeling and maintenance, query evaluation, database design through dependencies, representation and manipulation of deduced facts, and incomplete information. However, the field of logic and databases, as it is called, is far from closed; logic provides an appropriate framework for many database problems that still need to be investigated thoroughly.

##### Açıklama

Tez (Yüksek Lisans) -- İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 1992

##### Anahtar kelimeler

Bilgisayar programlama yönetimi,
Sorgulama dili,
Veri tabanı sistemleri,
Computer programming management,
Query lanquage,
Database systems