检索结果-内蒙古大学图书馆

Faster Property Testers in a Variation of the Bounded Degree Model

ACM TRANSACTIONS ON COMPUTATIONAL logic 2023年第3期24卷 1-24页

作者： Adler, Isolde Fahey, Polly Otto Friedrich Univ Bamberg Fak Wirtschaftsinformat & Angew Informat Lehrstuhl Algorithmen & Komplexitatstheorie D-96045 Bamberg Germany Univ Leeds Sch Comp Leeds LS2 9JT England

Property testing algorithms are highly efficient algorithms that come with probabilistic accuracy guarantees. For a property P, the goal is to distinguish inputs that have P from those that are far from having P with high probability correctly, by querying only a small number of local parts of the input. In property testing on graphs, the distance is measured by the number of edge modifications (additions or deletions) that are necessary to transform a graph into one with property P. Much research has focused on the query complexity of such algorithms, i. e., the number of queries the algorithm makes to the input, but in view of applications, the running time of the algorithm is equally relevant. In (Adler, Harwath, STACS 2018), a natural extension of the bounded degree graph model of property testing to relational databases of bounded degree was introduced, and it was shown that on databases of bounded degree and bounded tree-width, every property that is expressible in monadic second-order logic with counting (CMSO) is testable with constant query complexity and sublinear running time. It remains open whether this can be improved to constant running time. In this article we introduce a new model, which is based on the bounded degree model, but the distance measure allows both edge (tuple) modifications and vertex (element) modifications. We show that every property that is testable in the classical model is testable in our model with the same query complexity and running time, but the converse is not true. Our main theorem shows that on databases of bounded degree and bounded tree-width, every property that is expressible in CMSO is testable with constant query complexity and constant running time in the new model. Our proof methods include the semilinearity of the neighborhood histograms of databases having the property and a result by Alon (Proposition 19.10 in Lovasz, Large networks and graph limits, 2012) that states that for every bounded degree graph G there

关键词： Constant time algorithms logic and databases property testing bounded degree model

来源：评论

学校读者我要写书评

暂无评论

Property Testing for Bounded Degree databases 35

Property Testing for Bounded Degree Databases

引用

35th Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Adler, Isolde Harwath, Frederik Univ Leeds Sch Comp Leeds W Yorkshire England Goethe Univ Inst Informat D-60054 Frankfurt Germany

ISBN: (纸本)9783959770620

Aiming at extremely efficient algorithms for big data sets, we introduce property testing of relational databases of bounded degree. Our model generalises the bounded degree model for graphs (Goldreich and Ron, STOC 1997). We prove that in this model, if the databases have bounded tree-width, then every query definable in monadic second-order logic with modulo counting is testable with a constant number of oracle queries and polylogarithmic running time. This is the first logical meta-theorem in property testing of sparse models. Furthermore, we discuss conditions for the existence of uniform and non-uniform testers.

关键词： logic and databases Property Testing logical Meta-theorems Bounded Degree Model Sublinear Algorithms

来源：评论

学校读者我要写书评

暂无评论

OXDBS - Extension of a native XML Database System with Validation by Consistency Checking of OWL-DL Ontologies 10

OXDBS - Extension of a native XML Database System with Valid...

引用

14th International Database Engineering and Applications Symposium (IDEAS)

作者： Neumann, Christoph P. Fischer, Thomas Lenz, Richard Friedrich Alexander Univ Inst Comp Sci Data Management 6 Erlangen Germany

ISBN: (纸本)9781605589008

Native XML database systems provide mature technology for persisting XML data and documents. Ontologies are often represented as XML-based documents like OWL-DL ontologies which allow for semantic consistency checking by formal description logic. Artificial intelligence provides reasoners as IT-support for consistency checking. Currently there exists no native XML database system which integrates logic reasoning for semantic consistency as addition to syntactic schema validation. The OXDBS project integrates a reasoner into a native XML database system, thus, allowing to assert consistency of ontological data at the most basic tier in an application environment.

关键词： Semantic Web and databases logic and databases Medical Systems Data Quality and Semantics

来源：评论

学校读者我要写书评

暂无评论

Integrating and querying P2P deductive databases

Integrating and querying P2P deductive databases

引用

10th International Database Engineering and Applications Symposium (IDEAS 2006)

作者： Caroprese, Luciano Molinaro, Cristian Zumpano, Ester Univ Calabria Calabria Italy

ISBN: (纸本)9780769525778

The paper proposes a logic framework for modeling the interaction among deductive databases and computing consistent answers to logic queries in a P2P environment. As usual, data are exchanged among peers by using logical rules, called mapping rules. The novelty of our approach is that only data not violating integrity constraints are exchanged. The (declarative) semantics of a P2P system is defined in terms of weak models. Under this semantics only facts not making the local databases inconsistent can be imported, and the preferred weak models are the consistent scenarios in which peers import maximal sets of facts not violating integrity constraints. A characterization of the preferred weak model semantics, allowing to model a P2P system with a prioritized logic program, is provided. The proposed framework is then extended in order to also take into account P2P system in which each peer may be locally inconsistent, i.e. its data does not satisfy some of its constraints. Finally, the complexity of P2P logic queries is investigated.

关键词： logic and databases inconsistent databases Peer-to-Peer Data Management Data Integration

来源：评论

学校读者我要写书评

暂无评论

The deductive database system LDL++

引用

THEORY AND PRACTICE OF logic PROGRAMMING 2003年第1期3卷 61-94页

作者： Arni, F Ong, KL Tsur, S Wang, HX Zaniolo, C InferData Corp Austin TX 78759 USA Trilogy Inc Austin TX 78746 USA BEA Syst San Jose CA 95131 USA IBM Corp TJ Watson Res Ctr Hawthorne NY 10532 USA Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA

This paper describes the LDL++ system and the research advances that have enabled its design and development. We begin by discussing the new nonmonotonic and nondeterministic constructs that extend the functionality of the LDL++ language, while preserving its model-theoretic and fixpoint semantics. Then, we describe the execution model and the open architecture designed to support these new constructs and to facilitate the integration with existing DBMSs and applications. Finally, we describe the lessons learned by using LDL++ on various tested applications, such as middleware and datamning.

关键词： deductive databases logic and databases Datalog nonmonotonic reasoning monotonic aggregates

来源：评论

学校读者我要写书评

暂无评论

logic modeling: A tool for management science

引用

Decision Support Systems 1988年第1期4卷 3-16页

作者： Kimbrough, Steven O. Lee, Ronald M. University of Pennsylvania Department of Decision Sciences/CC Philadelphia PA 19104 United States University of Texas-Austin Department of General Business CBA 5.202 Austin TX 78712 United States

Developments in logic and in information technology (especially the advent of logic programming) have converged to the point at which logic is, for a broad variety of problems, a useful tool to employ for modeling in areas of interest to management scientists. This paper presents the concept of logic modeling (model building with symbolic logic) and reviews several lines of research having in common a logic modeling approach to problems of interest in management scientist. © 1988.

关键词： logic logic and databases logic Programming Nonmonotonic logic Prolog

来源：评论

学校读者我要写书评

暂无评论

Security checking in relational database management systems augmented with inference engines

引用

Computers and Security 1987年第6期6卷 479-492页

作者： Thuraisingham, M.B. Honeywell Corporate Systems Development Division Golden Valley MN United States

In this paper we will discuss the notion of multilevel security and the difficulties encountered in designing an implementation scheme for a security policy for a multilevel secure database management system (MLS/DBMS). We will then describe how these difficulties may be overcome in augmenting a database with an inference engine so that it functions like a knowledge based system. © 1987.

关键词： Inference engine Knowledge based systems logic and databases Multilevel secure database management systems Multilevel security Security policy

来源：评论

学校读者我要写书评

暂无评论

A Time Bound on the Materialization of Some Recursively Defined Views

引用

ALGORITHMICA 1986年第1-4期1卷 361-385页

作者： Ioannidis, Yannis E. Univ Wisconsin Dept Comp Sci Madison WI 53706 USA

A virtual relation (or view) can be defined with a recursive Horn clause that is a function of one or more base relations. In general, the number of times such a Horn clause must be applied in order to retrieve all the tuples in the virtual relation depends on the contents of the base relations of the definition. However, there exist Horn clauses for which there is an upper bound on the number of applications necessary to form the virtual relation, independent of the contents of the base relations. Considering a restricted class of recursive Horn clauses, we give necessary and sufficient conditions for members of the class to have this bound.

关键词： logic and databases Horn clauses Recursively defined relations Uniformly bounded recursion

来源：评论

学校读者我要写书评

暂无评论

logic and databases - A DEDUCTIVE APPROACH

引用

COMPUTING SURVEYS 1984年第2期16卷 153-185页

作者： GALLAIRE, H MINKER, J NICOLAS, JM OFF NATL ETUD & RECH AEROSP CERTDEPT INFORMATTOULOUSEFRANCE UNIV MARYLAND DEPT COMP SCICOLLEGE PKMD 20742

The purpose of this paper is to show that logic provides a convenient formalism for studying classical database problems. There are two main parts to the paper, devoted respectively to conventional databases and deductive databases. In the first part, we focus on query languages, integrity modeling and maintenance, query optimization, and data dependencies. The second part deals mainly with the representation and manipulation of deduced facts and incomplete information. [ABSTRACT FROM AUTHOR]

关键词： Deductive databases Indefinite Data logic and databases Null Values Relational databases

来源：评论

学校读者我要写书评

暂无评论

ON COMPILING QUERIES IN RECURSIVE 1ST-ORDER databases

引用

JOURNAL OF THE ACM 1984年第1期31卷 47-85页

作者： HENSCHEN, LJ NAQVI, SA BELL TEL LABS INC MURRAY HILLNJ 07974

A first-order database is defined as a function-free first-order theory in which the ground units serve as the extensional database and the proper noniogical axioms serve as the intensional database. The following problem is addressed: “Given a recurswe nonlogical axiom and the form of a potential query, can one describe a set of database retrieval requests that gives the correct answers and is guaranteed to terminate.” The solution uses resolution-proof techmques over connection graphs to derive a program of relational database operations that gives all the answers to a query and has a welldefined termmatton condtion. © 1984, ACM. All rights reserved.

关键词： logic and databases logic program compilation recursively defined relations

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：