問題タブ [canonical-form]

言語の標準的な表現を持つと便利なことがよくあります (私の場合、それらは通常ドメイン固有の言語です)。ただし、関連する言語の表現力には厳密な制限があり、その言語の任意のプログラムに対して標準形式を決定および/または作成できるかどうかを決定するものだと思います。残念ながら、これについて読んだことを（漠然と）思い出した参考文献を見つけることができませんでした.

一方では、言語の正規表現を作成することは、多くのハード グラフの問題 (例: グラフ同形性) に匹敵する複雑さであると合理的に思われますが、他方では、iirc、gcc、yhc、および ghc などのコンパイラは中間表現を使用します。さまざまな形式（アセンブリ、JavaScriptなど）で出力を生成するため、これは少なくともいくつかの形式では解決済みの問題です。

特定の言語の正規形を決定/生成できるのはいつですか? (その言語はどの程度表現力があり、言語の表現力は正規形の有用性にどのように影響しますか?) 可能であれば、参照または証明を提供してください。

編集：たとえば、正規言語（例：正規表現の「純粋な」形式）は、チューリング完全言語が表現できるのと同じ多くのことを表現できません。つまり、通常の言語で Web サーバーを作成することはできませんが、ラムダ計算を使用すると作成できます)。私の質問は理論的な可能性に関するもので、複雑性理論に関連する具体的な答えがあります。別のシステムに送信する必要がある DSL がある場合、送信する前にそのコードの標準的な形式を生成すると、2 つの異なるシステムで使用される独立した表現が分離されるため、多くの場合有益です。 でも、それがP空間完全、またはチューリング完全言語を標準形式に変換するためのNP完全である場合、標準形式を構築しようとして時間を無駄にすべきではありません-それを行う別の方法を見つけるか、削減します多項式時間で正規化できる言語の複雑さ。

「最適化されたクエリジェネレーター」を作りたいとしましょう。基本的に、時間/スペースの制限に基づいて SQL サーバーに配置できるものよりもはるかに優れた SQL クエリ オプティマイザーです。クエリと DB 統計を入力として取り、ターゲット システムに合わせて調整された SQL クエリを生成し、ほぼ理想的な計画にすばやく最適化します。

どの程度の SQL をサポートする必要がありますか? ほとんどの有用なクエリを簡単に記述できるほど柔軟でありながら、完全な SQL よりも十分に小さく、切り詰める価値のある SQL のサブセットはありますか? また、「マシンの近く」に固執する必要がない場合、クエリを説明するより良い方法はありますか?

既存の SQL を処理するプログラムではなく、新しい SQL を作成するためのツールを考えています。入力言語がクエリの要件を記述できる限り、実際に SQL を入力として受け取る必要はありません。

質問の別の形式は次のようになると思います:パフォーマンスのためだけに存在し、読みやすさ/理解度を向上させることのないSQLの部分はありますか?

誰かが指摘したように、これを行うには「大量の製品固有の知識」が必要であり、それ(たとえば、ネストされたサブクエリと何でも、どの種類のインデックスを使用する必要があるか、そのようなこと) は、まさにツールがカプセル化することを意図したものです。ユーザーがその知識を学ぶ必要がないようにします。

注:実際のクエリ プランの生成には興味がありません。これは DBMS の仕事であり、とにかく SQL からは実行できないからです。特定の DBMS 用に調整する必要のない入力から、その DBMS 用の適切な SQL を作成する作業を自動化できるシステムに興味があります。

これは実際には機械学習の分類問題ですが、それを行うための完全に手っ取り早い方法があると思います。「サンフランシスコ」、「49ers」、「サンフランシスコ 49ers」、「SF フォーティーナイナーズ」などの NFL チームを表す文字列を、チームの正式な名前にマッピングしたいと考えています。(32 の NFL チームがあるため、実際には、特定の文字列を配置するために最も近い 32 のビンを見つけることを意味します。)

入力文字列は実際には完全に恣意的なものではありません (これらは次のような構造化データ ソースからのものです: http://www.repole.com/sun4cast/stats/nfl2008lines.csv ) 。上記の49ersの例。

また、マネーライン ベガス オッズと過去数年間の NFL ゲームの実際のゲーム結果の両方を含むデータ ソースを誰かが知っている場合は、これを行う必要がなくなることも付け加えておく必要があります。正規化が必要な理由は、これらの 2 つの異なるデータ セット (1 つはオッズ、もう 1 つは結果) を一致させるためです。

• http://www.footballlocks.com/nfl_odds.shtml
• http://www.repole.com/sun4cast/freepick.shtml

より優れた、より解析可能なデータソースのアイデアは大歓迎です!

追加: 部分文字列一致のアイデアは、このデータには十分かもしれません。ありがとう！レーベンシュタイン距離が最も近いチーム名を選択することで、もう少し堅牢にすることはできますか?

クラスの非メンバー非友人のインターフェースをできるだけ多くするのは良い考えだと知っています。そして、私の3Dベクトルクラス「Vector3」では、+=を移動できることに気づきました。 -=など、クラス外の演算子。コンストラクターとコピー代入演算子のみを残します。

問題は、この演算子はどのように見えるべきかということです。私は他の多くの演算子の標準形を見てきましたし、彼らのアドバイスに従いましたが、これらの演算子の標準形を見たことがありません。私はそれが下にあるべきだと思うものを与えました。

二次的な質問は、これらの演算子は何と呼ばれているのかということです。算術代入演算子？

前の（関連する）コード：

これまでに変更したもの：

いくつかの xml を直接正規化すると、ハッシュ化する前に xml で同じ正規化アルゴリズムを実行するデジタル署名を実行する場合よりも、同じ xml ドキュメントの 2 つの異なるハッシュが得られますか? デジタル署名の正規化には、正規化時に改行文字「\ n」と空白文字が含まれ、直接アルゴリズムには含まれないことがわかりました。

改行文字+スペースを含めることは、正規化仕様に含まれていませんか? 私は特にこのバージョンを見ています http://www.w3.org/TR/2001/REC-xml-c14n-20010315

誰が何が起こっているのか知っていますか？あなたが見ることができるように、私はxmlドキュメントとコードの両方の実装を含めました。

これは本当に私を困惑させています。理由を知りたいのですが、明らかな何かが欠けていますか?

直接正規化コード

xml デジタル署名コード

どんなアイデアも素晴らしいでしょう！ちなみに、これはすべて C# コードです。

前もって感謝します

ジョン

xmlseclibsを使用してSOAPドキュメントに署名しようとしていますが、署名するか検証するかによって、同じように正規化されていないようです。

例を挙げましょう。これは私が署名しようとしているXMLです：

公開鍵と秘密鍵の証明書の組み合わせを使用して署名するためにPHPで動作するコードを取得しましたが、動作しているように見えました。それはすべての適切なもので要素を追加しました<ds:Signature>、そしてそれは素晴らしく見えました。しかし、署名後すぐにxmlseclibs（および公開鍵証明書）を使用して検証を試みてテストしましたが、検証に失敗しました。したがって、まったく同じコードライブラリが署名と検証の両方を実行しますが、2つのプロセスは何らかの理由で一致しません。

xmlseclibsにデバッグコードを追加して、それが何をしているのかを調べました。署名キーと検証キーが異なる理由は、2つの状況で正規化が異なるためであることに気付きました。要素に署名するように指示すると<samlp:Response>、これは署名する標準形になります（読みやすくするためにここに改行を追加しました）。

ただし、署名を検証する場合、これは検証のために計算する標準形です（ここでも、改行を追加しました）。

ご覧のとおり、このバージョンxmlns:samlでは要素から属性が省略されていますが<samlp:Response>、最初のバージョンでは省略されていません。（これは、両方に含まれている属性とは異なることに注意してくださいxmlns:samlp。）これはxmlseclibsのバグのように見えますが、それでも、どちらの標準形が正しいかを知っていれば、自分で修正できれば幸いです。 。その属性は、排他的な正規化によって省略されるべきですか？それとも含める必要がありますか？正しい排他的な標準形はどれですか？

私は現在、自分のサイトの両方の URL を google と yahoo siteexplorer などにリストしていますが、インデックスされているページにはいくつかの違いがあります。

両方が必要ですか、それとも www で始まるものを削除して、新しい URL を使用してすべてのページを検索できるようにすることはできますか? Google で優先ドメインを設定しましたが、Yahoo でそれを行う方法がわかりません。

これは、彼らが私のサイトをどのようにインデックス化するかにも違いがありますか、それとも単に統計などにアクセスできるようにするためですか?

とにかく、私の .htaccess はすべて www を削除するように設定されています。

アドバイスをいただければ幸いです。

質問:アームストロングの公理を使ってカノニカル カバーを決定します。各ステップに到達するために使用する公理を与えてください。

R = (A, B, C, D, E, F) Fdependencies = {A -> B, A -> C, CD -> E, CD -> F, B -> E}

私はアームストロングの公理を知っています: 結合、分解、疑似推移性、再帰性、増強、推移性。また、正規のカバーが何であるかも知っています。しかし、アームストロングの公理を使用してこの特定の質問の答えに到達する方法がわかりません。通常、cc ではなく、アームストロングの公理を使用して F+ を計算すると思いました。助けてくれてありがとう。

次の関係を3NFに分解しようとしています。

そこで、標準的なカバーを取得するために冗長性を排除しました。

そして今、私はこれを3NFに分解しようとしています。

に分解する必要がありr1(A, B, C) r2(B, D), r3(C, D)ます。それでは私は何をしD -> Aますか？

私を失望させているという事実A -> B -> D -> A。